Recursão está em toda parte.
Esta na natureza. No texto há `Recursion in Nature, Mathematics and Art `_ de Anne M. Burns há
algoritmos que produzem imitações de algumas formas encontradas na natureza.
.. image:: ./imgs/Spiral_aloe_518_389.jpg
:width: 518
:height: 389
:scale: 50
:alt: By J Brew - Aloe polyphylla Schönland ex Pillans, CC BY-SA 2.0,
:align: center
:target: https://commons.wikimedia.org/w/index.php?curid=5125435
Recursão está na arte, está na matemática, está na computação.
.. image:: ./imgs/The_Artist_-Maurits_Cornelelius_Escher-_working_at_his_Atelier.jpg
:width: 712
:height: 710
:scale: 30
:alt: By Pedro Ribeiro Simões from Lisboa, Portugal - The Artist [Maurits Cornelelius Escher] working at his Atelier, CC BY 2.0
:align: center
:target: https://commons.wikimedia.org/w/index.php?curid=95553005
Neste capítulo exploraremos a essência recursiva presente em curvas bidimensionais em que as curvas maiores, aparentemente mais complexas, são formadas por várias cópias
de figuras curvas semelhantes e mais simples. Depois de desvendarmos o padrão de recursivo presente em alguma curva, faremos uma programa para desenhá-la usando como pincel |:art:|.
Os rastros feitos por tartarugas |:turtle:| que percorrerão o traçado da curva serão nosso pincel. |:face_with_raised_eyebrow:|
Essa será uma visão muito interessante e fofa de recursão visual bidimensional. |:artist_tone4:| |:woman_artist_tone1:|
..
|romanesco| image:: ./imgs/Romanesco_broccoli_500x400.*
:width: 500
:height: 400
:scale: 65
:alt: By Ivar Leidus - Own work, CC BY-SA 4.0
:align: center
:target: https://commons.wikimedia.org/w/index.php?curid=100133434
|helianthus| image:: ./imgs/Helianthus_whorl.jpg
:width: 640
:height: 480
:scale: 50
:alt: By L. Shyamal - Own work, CC BY-SA 2.5
:align: center
:target: https://commons.wikimedia.org/w/index.php?curid=895745
Destino
-------
A excursão deste capítulo nos levará a explorarmos formas que têm a caracteristica de auto-semelhança.
Essas formas serão desenhos em que os desenhos maiores são formados por cópias de desenhos menores que têm a mesma cara, o mesmo jeitão, são claramente parentes, do desenho maior.
Como na imagem da brocoli abaixo.
.. image:: ./imgs/Romanesco_broccoli_500x400.*
:width: 500
:height: 400
:scale: 65
:alt: By Ivar Leidus - Own work, CC BY-SA 4.0
:align: center
:target: https://commons.wikimedia.org/w/index.php?curid=100133434
As formas que escolhemos são as curvas de Hilbert.
Treinaremos a nossa percepção recursiva investigando o padrão presente nas curvas de Hilbert.
Depois de desvendarmos o mistério recursivo gravado nas curvas de Hilbert faremos um programa para desenhá-las.
Para fazermos os desenhos utilizaremos o módulo `Turtle Graphics
`_ do |Python|.
Esse módulo é bem simples e provavelmente já faz parte de sua instalação.
Podemos usar as tartarugas do Turtle para fazermos
desenhos como o mostrado pelo programa na janela do |Trinket|
abaixo. Como sempre, para o programa se executado, devemos clicar no
botão |Run| na janela.
.. raw:: html
Começaremos dando uma volta pela vizinhança do módulo das **curvas de Hilbert** e depois iremos para o **mundo das tartarugas** |:turtle:| do
`Turtle Graphics `_ do |Python|.
O objetivo desta jornada pelas curvas de Hilbert é treinar a nossa habilidade de procurar padrões em formas complexas de tal maneira que possam ser criadas através
da combinação de formas simples. Isso é coisa de detetive! |:female_detective:| |:detective_tone2:|
.. _my_Introducao-Hilbert:
Introdução
----------
.. index:: curvas de Hilbert
Para passaremos na vizinhança de umas tais `Curvas de Hilbert `_.
Abaixo é exibida uma dessas curvas de Hilbert. A curva é um desenho que fazemos em uma folha de papel usando um lápis, uma pena ou um pincel.
Começamos o desenho com o pincel no papel, em um **ponto inicial** do papel e, sem tirar o pincel do papel, traçamos uma linha continua até um **ponto final**.
Onde está o ponto inicial e o ponto final da curva abaixo? |:thinking:|
.. image:: ./imgs/Hilbert.*
:width: 316
:height: 316
:scale: 100
:alt: By Enormator - Own work, CC BY-SA 3.0
:align: center
:target: https://commons.wikimedia.org/w/index.php?curid=7009430
Muitas desenhos, muitas curvas que vemos parecem se feitas atrás de um certo padrão repetitivo.
Examinando a curva de Hilbert anterior parece que podemos intuir que há nela um certo padrão respetivo.
Podemos não saber qual é regra que esse padrão obedece |:thinking:|, mas podemos ter a impressão que há algum.
Neste passeio, para começar, investigaremos |:detective_tone3:| de perto, com uma lupa |:mag_right:|, as Curvas de Hilbert a procura desse padrão misterioso.
No caso, sendo um pouco *spoiler*, o padrão que estamos procurando, como veremos, obedece um regra recursiva. Legal, né?! |:cool:|
Em seguida, escreveremos um programa que produzirem essas tais curvas de Hilbert.
A seguir podemos ver o programa em ação. No caso quem faz o papel de pincel é uma tartaruga |:turtle:| que vai deixando seu rastro por onde passa.
O rastro de cada tartaruga forma uma curva de Hilbert.
No animação são formadas seis curvas de Hilbert, uma por cada uma das tartarugas.
O programa começa desenhando curvas mais simples e a cada passo desenha curvas mais complexas.
Por simples queremos dizer *menor*, mais curta, com menos segmentos retos. Por complexa entendemos *maior*, mais longa, com mais seguimentos de reta.
Notemos na animação que cada curva tem um ponto inicial e um ponto final e que do ponto inicial ao final todos os pontos por onde passa a tartaruga dona da curva é marcado como o seu rastro colorido.
.. image:: ./imgs/hilbert0.*
:width: 959
:height: 847
:scale: 50
:alt: Curvas de Hilbert
:align: center
.. _my_Hilbert:
Curvas de Hilbert
------------------
.. index:: curva de Hilbert
Como na animação da execução do programa acima, começaremos fazendo coisas mais simples.
Observaremos das curvas de Hilbert mais simples e procuraremos descobrir o papel que as formas mais
simples tem no traçado das formas mais complexas. As curvas de
Hilbert seguem um certo *padrão regular* e poderão ser desenhadas na
tela computador |:desktop:| mais facilmente sobre o controle de um programa
graças a esse padrão. Para isso precisamos antes de mais nada descobrir o padrão utilizado para desenhá-las.
.. image:: ./imgs/H1_H2.*
:width: 1057
:height: 588
:scale: 60
:alt: Curvas de Hilbert de ordem 1 e 2
:align: center
O nosso objetivo é descobrir a regra de formação, o *esquema de recursão*,
para construir tais curvas. Estes padrões serão chamados de
:math:`H_0, H_1, H_2, \ldots`. :math:`H_0` é a curva vazia, :math:`H_1` e :math:`H_2`
estão acima e :math:`H_3` logo abaixo.
Pode parecer estranho termos uma curva como :math:`H_0`.
Pode até ser estranho |:face_with_rolling_eyes:|, mas é conveniente. |:face_with_raised_eyebrow:|.
.. image:: ./imgs/H3.*
:width: 796
:height: 858
:scale: 50
:alt: Curva de Hilbert de ordem 3
:align: center
Cada curva :math:`H_i` é denominada de **curva de Hilbert** de *ordem* :math:`i`
em homenagem a seu criador, o matemático `David Hilbert `_.
Abaixo vemos a curva de Hilbert de ordem :math:`\mathtt{4}`.
.. image:: ./imgs/H4.*
:width: 904
:height: 959
:scale: 50
:alt: Curva de Hilbert de ordem 4
:align: center
Notemos as semelhanças entre as curvas e que quanto maior o índice :math:`i` do :math:`H_i` mais complexa parece a curva.
No final, após descobrirmos a regra de formação dessas curvas, as formas que são aparentemente mais complexas nos parecerão mais simples.
Estaremos interessados no seguinte problema:
**Problema (Curva de Hilbert)**: Dado um inteiro :math:`\mathtt{k}` desenhar a curva de Hilbert de ordem :math:`\mathtt{k}`.
Vamos primeiro ao caça |:bow_and_arrow:| do esquema recursivo.
Observando as curvas com atenção |:face_with_monocle:|, muita atenção |:nerd:|.
Podemos notar que a curva :math:`H_{i+1}` contém quatro
cópias de :math:`H_{i}`, uma em cada canto, ligadas por três linhas.
Por exemplo, :math:`H_{1}` é obtida a partir de quatro cópias de :math:`H_{0}`, a curva vazia, ligada por três linhas, duas horizontais e uma vertical.
A curva :math:`H_{2}` é obtida a partir de quatro cópias de :math:`H_{1}`, convenientemente rotacionadas, ligadas por três linhas.
Espere ai... |:stop_sign:| |:back_of_hand:|
Se olharmos apenas para as três linhas que ligam os :math:`H_{1}` vemos que elas formam um :math:`H_{1}`.
Na imagem abaixo as quatro copias de :math:`H_1` estão em vermelho e a três linhas ligando-as então em azul com uma flecha indicando cada uma delas.
.. image:: ./imgs/H2_de_H1s.*
:width: 758
:height: 835
:scale: 50
:alt: Curva de Hilbert de ordem 2
:align: center
Para traçarmos :math:`H_{2}` podemos, começando em um ponto inicial:
* desenhar uma curva :math:`H_{1}` com a sua *abertura para cima*;
* traçar um linha para a *esquerda*;
* desenhar uma curva :math:`H_{1}` com a sua *abertura para a direira*;
* traçar um linha para *baixo*;
* desenhar uma curva :math:`H_{1}` com a sua *abertura para a direira*;
* traçar um linha para a *direita*; e
* desenhar uma curva :math:`H_{1}` com a sua *abertura para baixo*.
A **abertura** é determinada através das posições das suas pontas inicial e final em relação ao resto da curva.
Por exemplo, na abertura para cima as pontas estão na parte superior da curva.
Chamar de abertura faz sentido, certo?! |HEIN|
Exminemos agora a curva :math:`H_{3}`. Por sua vez, :math:`H_{3}` é formado por quatro :math:`H_{2}`, convenientemente rotacionadas, ligados por três linhas.
.. image:: ./imgs/H3_de_H2s.*
:width: 755
:height: 812
:scale: 50
:alt: Curva de Hilbert de ordem 3
:align: center
De maneira semelhante ao que fizemo para traçarmos :math:`H_{2}`, para traçarmos :math:`H_3` podemos, começando em um ponto inicial:
* desenhar uma curva :math:`H_{2}` com a sua *abertura para cima*;
* traçar um linha para a *esquerda*;
* desenhar uma curva :math:`H_{2}` com a sua *abertura para a direira*;
* traçar um linha para *baixo*;
* desenhar uma curva :math:`H_{2}` com a sua *abertura para a direira*;
* traçar um linha para a *direita*; e
* desenhar uma curva :math:`H_{2}` com a sua *abertura para baixo*.
Seguindo na mesma linha de raciocínio, :math:`H_{4}` contém quatro :math:`H_{3}`, ligados por três linhas.
.. image:: ./imgs/H4_de_H3s.*
:width: 880
:height: 935
:scale: 50
:alt: Curva de Hilbert de ordem 4
:align: center
Podemos parar por aqui nossa procura por evidências e partir para uma descrição compacta das curvas.
Padrões de Hilbert
------------------
Para descrever as quatro partes de cada curva de Hilbert é conveniente
darmos nomes diferentes a cada parte dependendo que como foi
rotacionada, dependendo de onde está a sua abertura do padrão.
Usaremos as letras :math:`A`, :math:`B`, :math:`C` e :math:`D` de tal forma que:
* :math:`A_i` será o padrão de ordem :math:`i` com a *abertura* para a **direita**;
* :math:`B_i` será o padrão de ordem :math:`i` com a *abertura* para a **baixo**;
* :math:`C_i` será o padrão de ordem :math:`i` com a *abertura* para a **esquerda**; e
* :math:`D_i` será o padrão de ordem :math:`i` com a *abertura* para a **cima**.
Sobre esse ponto de vistas, daremos os seguintes apelidos para as curvas dependendo do padrão.
Vamos dar uma olhada |:eyes:| em alguns exemplos.
Padrões das curvas :math:`A_1` e :math:`A_2` com abertura para a direita.
.. image:: ./imgs/A1_e_A2.*
:width: 915
:height: 595
:scale: 50
:alt: Curvas de Hilbert com abertura para a direita
:align: center
Agora vejamos as curvas :math:`B_2` e :math:`B_3` com abertura para baixo.
.. image:: ./imgs/B2_e_B3.*
:width: 1099
:height: 736
:scale: 50
:alt: Curvas de Hilbert com abertura para baixo
:align: center
A seguir estão as curvas :math:`C_2` e :math:`C_3` com abertura para esquerda.
.. image:: ./imgs/C2_e_C3.*
:width: 1074
:height: 723
:scale: 50
:alt: Curvas de Hilbert com abertura para esquerda
:align: center
Por último, a curva :math:`D_4` com abertura para cima.
.. image:: ./imgs/D4.*
:width: 748
:height: 784
:scale: 50
:alt: Curvas de Hilbert com abertura para cima
:align: center
Dessa forma temos que :math:`H_1` é :math:`A_1`,
:math:`H_2` é :math:`A_2`,
:math:`H_3` é :math:`A_3`,... |:thinking:|
.. _my_Esquema_recursivo:
Esquema recursivo
-----------------
Agora estamos no ponto para descrever o esquema recursivo para desenhar uma curva de Hilbert de ordem :math:`k`.
Na nossa descrição teremos em mente que o desenho começa em algum canto superior direito.
Utilizaremos, símbolos:
* :math:`\rightarrow` para indicar que o pincel deve se mover para direita; |:arrow_right:|
* :math:`\uparrow` para indicar que o pincel deve se mover para cima; |:arrow_up:|
* :math:`\leftarrow` para indicar que o pincel deve se mover para esquerda; e |:arrow_left:|
* :math:`\downarrow` para indicar que o pincel deve se mover para baixo. |:arrow_down:|
Utilizando as flechas acima chegamos a seguinte descrição recursiva das curvas:
* :math:`A_k = D_{k-1} \leftarrow A_{k-1} \downarrow A_{k-1} \rightarrow B_{k-1}`
* :math:`B_k = C_{k-1} \uparrow B_{k-1} \rightarrow B_{k-1} \downarrow A_{k-1}`
* :math:`A_k = D_{k-1} \rightarrow A_{k-1} \uparrow A_{k-1} \leftarrow B_{k-1}`
* :math:`A_k = D_{k-1} \downarrow A_{k-1} \rightarrow A_{k-1} \uparrow B_{k-1}`
Tudo bem?! |HEIN|
Acabou o nosso serviço no entendimento das curvas de Hilbert e de como descrever formas complexas a partir de formais mais simples através de recursão.
Na próxima seção vamos conversar sobre as tartarugas que serão usadas pelo nosso programa para desenhar as curvas usando o esquema proposto.
Mundo das tartarugas
--------------------
.. index:: tartarugas
.. index:: Turtle Graphics
Para fazermos os desenhos utilizaremos o módulo `Turtle Graphics `_ do |Python|.
O nome ``Turtle``, tartaruga |:turtle:| vem da ideia de que para desenharmos em uma janela devemos pensar em tartarugas se movendo e deixando seus rastros.
Faz sentido? |HEIN|
Veja o pequeno exemplo na janela do |Trinket| que está a abaixo. Para executar o programa, como sempre, basta clicar em |Run|.
.. raw:: html
Inicialmente, para criarmos o mundo das tartarugas, colocar tartaurags nesse mundo e move-las, devemos carrega o módulo ``turtle`` fazendo:
.. index:: ``import turtle``
.. code-block:: python
import turtle
Criamos o mundo ou janela onde as tartarugas podemos levar as tartarugas |:turtle:| para passear deixando seus rastros escrevendo algo como:
.. code-block:: python
janela = turtle.Screen()
.. index:: ``turtle.Turtle``
No |Trinket| anterior foi criada uma tartaruga, a ``tina``.
Para **criarmos** objetos ``Turtle``, nossas tartarugas, devemos escrever ``tutle.Turtle()`` e dar nome a ela, coisas como:
.. code-block:: python
leornado = turtle.Turtle()
raphael = turtle.Turtle()
donatelo = turtle.Turtle()
michelangelo = turtle.Turtle()
Cada tartaruga é um objeto da classe ``turtle.Tutle``:
.. code-block:: python
In [1]: import turtle
In [2]: leonardo = turtle.Turtle()
In [3]: type(leonardo)
Out[3]: turtle.Turtle
Se queremos que a posição onde está o ``leonardo`` seja exibido na janela como uma tartaruga, e não como uma flexinha |:arrow_right:|, fazemos
.. code-block:: python
leonardo.shape("turtle")
No código trecho de código mais acima criamos quatro objetos ``turtle.Turtle``, os seu nomes, apelidos ou referências além de ``leonardo``, foram
``raphael``, ``donatelo`` e ``michelangelo``.
Cada objeto ``turtle.Turtle``, tartaruga |:turtle:|, tem três atributos, um diz a sua **localização** na janela, outro indica a com sua **orientação** ou **direção** e outro é o seu **pincel** que cuida de como o será exibido o seu rastro quando se mover.
O pincel de uma tartaruga tem o atributo ``color`` com a cor do seu rastro, ``pensize`` com a espessura do seu rastro e um estado ligado/desligado, ``pendown()`` para ligar e deixar rastro e
``penup()`` para desligar e não deixar rastro.
.. code-block:: python
# posição do michelangelo
x, y = michelangelo.pos()
# michelangelo se moverá sem deixar rastro
michelangelo.penup()
# michelangelo vai para a posição (10,10) sem deixar rastro
michelangelo.goto(10,10)
# define que a cor do rastro do michelangelo será laranja
michelangelo.pencolor('orange')
# michelangelo de moverá deixando rastro
michelangelo.pendown()
# defina a espessura do rastro do michelangelo
michelangelo.pensize(2)
# michelangelo vai até posicão (-10,-10) deixando rastro
michelangelo.goto(-10,-10)
Outras coisas que sabemos fazer com uma tartarura e movê-la para frente, para trás, para a esquerda ou para a direita ou mesmo se mover sobre uma
circunferência:
.. code-block:: python
# donatelo se moverá sem deixar rastro
donatelo.pendown()
# defina a espessura do rastro do donatelo
donatelo.pensize(3)
# define que a cor do rastro do donatelo será roxa
donatelo.pencolor('purple')
# donatelo da 10 passos para frente
donatelo.forward(10)
# donatelo vira 90 graus para a direita
donatelo.right(90)
# donatelo da 5 passos para trás
donatelo.backward(15)
Chega de descrever as tartarugas e passemos a brincar com elas!
Abaixo há uma outra janela em que a ``tina`` está passeando em círculos e fazendo outras artes.
Clique em |Run| e edite e brinque à vontade.
.. raw:: html
A ``tina`` tem muito mais coisas a nos ensinar.
Outros programas em que a ``tina`` aparece deixando mais rastros por ai estão na página `An Hour of Code `_ do |Trinket|. Podemos ver a ``tina`` desenhando com com o ``tommy`` em ` Turtles are objects `_.
Agora sabemos o suficiente sobre tartarugas para voltarmos às curvas de Hilbert.
Curvas como rastros
-------------------
No nosso caso utilizaremos uma tartarugas |:turtle:| do módulo Turtle como pincel para desenhar as curvas.
Para desenhar as curvas faremos várias chamada a função
.. code-block:: python
mova(pincel, direcao, comprimento)
que traça um segmento movendo um ``pincel`` da posição ``(x,y)`` em que está, em uma dada
``direcao`` por um certo ``comprimento``. O ``pincel`` é um objeto ``Turtle``, a nossa |:turtle:|
que ao se move deixa o seu rastro na tela. A direção será indicada por um dos apelidos a seguir:
.. code-block:: python
# apelidos para as direções
DIREITA = 0
ESQUERDA = 1
CIMA = 2
BAIXO = 3
O ``comprimento`` é o tamanho do segmento de reta que será desenhado. Observe que todos os segmentos básicos
das curvas de Hilbert têm o mesmo tamanho. Aqui esta a implementação da função.
.. code-block:: python
def mova(pincel, direcao, comprimento):
'''(turtle, int, int) -> None
RECEBE um pincel em uma determinada posição, um valor
direcao e um valor comprimento.
TRAÇA uma linha a partir da posição do pincel na direção dada
e do comprimento dado.
'''
# pegue a posição do pincel
x, y = pincel.pos()
# calcule nova posição
if direcao == DIREITA:
x = x + comprimento
elif direcao == ESQUERDA:
x = x - comprimento
elif direcao == CIMA:
y = y + comprimento
elif direcao == BAIXO:
y = y - comprimento
# mova a tartaruga traçando a linha.
pincel.goto(x,y)
Escreveremos funções ``a()`` que segue a descrição feita em :ref:`my_Esquema_recursivo` para desenhar a curva :math:`A_k`.
.. code-block:: python
def a(k, pincel, comprimento):
'''(int, Turtle, int) -> None
RECEBE um inteiro não negativo k, um pincel em uma determinada
posição da janela e um inteiro comprimento.
DESENHA a curva A de ordem k a partir da posição do pincel em que
comprimento é a medida dos segmentos da curva.
'''
# BASE: 'desenha' a curva vazia
if k == 0: return None
# REDUZ o desenho da curva a composição dos desenhos de curvas mais simples.
d(k-1, pincel, comprimento)
mova(pincel, ESQUERDA, comprimento)
a(k-1, pincel, comprimento)
mova(pincel, BAIXO , comprimento)
a(k-1, pincel, comprimento)
mova(pincel, DIREITA , comprimento)
b(k-1, pincel, comprimento)
As funções ``b()`` que desenha as curvas :math:`B_k`, ``c()`` que desenha as curvas :math:`C_k`,
``d()`` que desenha as curvas :math:`D_k`. São semelhantes a ``a()`` e serão deixadas como exercício.
Para nos divertirmos, no final desta seção há uma janela do |Trinket| que, depois de serem completadas as funções ``b()``, ``c()`` e ``d()``,
desenha curvas de Hilbert.
As funções a serem completadas estão no módulo ``hilbert.py``.
Nesse módulo, além das funções ``hilbert()``, ``a()``, ``b()``, ``c()`` e ``d()``, está ainda a função ``mova()``.
A seguir está a função ``hilbert()`` que é a casca, cuida de muitos preparativos para que a curva de Hilbert seja desenhada.
.. code-block:: python
def hilbert(k):
'''(int) -> None
RECEBE um inteiro k.
DESENHA a curva de Hilbert de ordem k em uma janela.
PRE-CONDIÇÃO: a funçao supõe que a janela já ter sido criada.
'''
# crie o pincel
pincel = turtle.Turtle()
# desenhe uma tartaruga
pincel.shape("turtle")
# defina a espessura do pincel
pincel.pensize(2)
# defina aleatoriamente a cor da tinta no pincel
pincel.color(random.randrange(256), random.randrange(256), random.randrange(256))
# defina velocidade do desenho: e bom ser um pouco
# lento para vermos o desenho se formando
pincel.speed(10)
# levante o pincel
pincel.penup()
# mova o pincel para a posiçao de inicio da curva
largura = LARGURA_JANELA
deslocamento = 0
for i in range(k):
largura //= 2
deslocamento += largura//2
# x, y = pincel.pos() posicao inicial e (0,0)
x = deslocamento
y = deslocamento
pincel.goto(x,y)
# abaixe o pincel
pincel.pendown()
# desenha H_k = A_k
a(k,pincel,largura)
# para fechar a janela basta clicar sobre ela
.. raw:: html
..
Sistemas-L
----------
Sistemas formais ficarão para uma próxima vez.
Paisagens vistas
----------------
O objetivo do passeio foi não apenas treinar recursão, mas principalmente incutir uma certa familiaridade e conforto em procurarmos e reconhecermos padrões recursivos.
Vimos um exemplo em que em uma figura a curva por padrões nos levou a um esquema recurvivo de construção da figura.
Esse esquema nos ensinou que curvas aparentemente complexas podem ser desenhadas através da composição dos desenhos de curvas mais simples.
A nossa função ``a()`` seguiu a risca a :ref:`my_Anatomia` de uma recursão:
::
se a instância é pequena, simples:
resolva-a diretamente e retorne
reduza a instância a instâncias menores do mesmo problema
aplique recursivamente o método de solução a cada uma das instâncias menores
combine as soluções das instâncias menores para obter um solução da instância atual e retorne
Na **base** da recursão, quando a *instância é pequena* temos que ``k == 0`` e desenhamos a curva vazia :math:`H_0`. |:dizzy_face:|
Já quando temos ``k > 0`` desenhamos :math:`H_k` *recursivamente combinando* o desenho de instâncias menores, curvas mais simples,
que são quatro cópias de :math:`H_{i-1}`.
Também passamos pelo parque e brincamos com a construção de desenhos usando as tartarugas |:turtle:| o módulo
`Turtle Graphics `_.
Tartarugas não dão a brecha para visualizarmos de outra forma a execução de um programa ou função.
Além disso, as tarturamos nos deram mais uma oportunidade de praticarmos programação orientada a objetos já que cada tartaruga é um objeto da classe
``turtle.Turtle``.
Verifique se entendeu
---------------------
#. O programa que foi dado no |Trinket| não exibe tartarugas, mostra apenas setas se movimentando.
Adapte esse programa para exibir as tartatugas como são mostradas na animação da :ref:`my_Introducao-Hilbert` deste capítulo.
#. Escreva um programa que produz o rastro de uma recursão de cauda como na animação a seguir.
.. image:: ./imgs/recursao_de_cauda.gif
:width: 962
:height: 862
:scale: 50
:alt: Recursão de cauda
:align: center
#. Escreva uma função ``alvo()`` que recebe como parâmetros uma tartaruga ``tina`` e um inteiro não negativo ``k`` e desenha um alvo com ``k`` circunferências como ilustra a imagem a seguir.
.. image:: ./imgs/alvo.png
:width: 735
:height: 737
:scale: 50
:alt: Alvo
:align: center
#. Abaixo estão imagens das *square curvas* de `Sierpiński `_ de ordem 2, 3 e 4.
Escreva um programa que recebe um inteiro ``k`` e desenha a curva de Sierpinśki de ordem ``k``.
.. image:: ./imgs/Sierpinski_curve_orders_2-4.png
:width: 1440
:height: 480
:scale: 50
:alt: By Hyacinth - Own work, Public Domain
:align: center
:target: https://commons.wikimedia.org/w/index.php?curid=76016609
#. Abaixo estão três imagens com as curvas de `Sierpiński `_.
A primeira imagem mostra a curva de Sierpiński de ordem 1. A segunda imagem exibe a curva de Sierpiński de ordem 1 e 2.
Finalmente, a terceira imagem apresenta as curvas de Sierpiński de ordem 1, 2 e 3 sobrepostas.
Escreva um programa que recebe um inteiro ``k`` e desenha a curva de Sierpinśki de ordem ``k``.
.. image:: ./imgs/Sierpinski-Curve-1.png
:width: 512
:height: 512
:scale: 40
:alt: By User:Nol Aders - Own work, CC BY-SA 3.0
:align: center
:target: https://commons.wikimedia.org/w/index.php?curid=208673
.. image:: ./imgs/Sierpinski-Curve-2.png
:width: 512
:height: 512
:scale: 40
:alt: By User:Nol Aders - Own work, CC BY-SA 3.0
:align: center
:target: https://commons.wikimedia.org/w/index.php?curid=208673
.. image:: ./imgs/Sierpinski-Curve-3.png
:width: 512
:height: 512
:scale: 40
:alt: By User:Nol Aders - Own work, CC BY-SA 3.0
:align: center
:target: https://commons.wikimedia.org/w/index.php?curid=208673
#. Escreva as funções ``b()``, ``c()`` e ``d()`` que são semelhantes à função ``a()`` e respeitam o :ref:`my_Esquema_recursivo`.
O que é ...
-----------
Aqui vai um lista de termos que usamos nesse capítulo e os seus significados. |:nerd:|
.. glossary::
Função recursiva
Função que possui chamadas diretas ou indiretas a si mesma. |:dizzy_face:|
Recursão indireta
Isso ocorre quando uma função chama outras, que por sua vez podem ou não chamar outras funções, o ponto é que em algum momento a função inicial volta a ser chamada. Por exemplo, a função ``a()`` possui chamadas diretas e indiretas, já que chama a função ``d()`` que por sua vez volta a chamar ``a()``.
Recursão direta
Ocorre quando uma função faz alguma chamada de função a si mesma. Por exemplo, a função ``fatorial()`` faz recursão direta.
Para saber mais
---------------
* `Recursion in Nature, Mathematics and Art `_ de Anne M. Burns.
* *Algoritms and Data Structures*, de Niklaus Wirth, Prentice Hall, 1986.
* `Recursão e algoritmos recursivos `_ de `Projeto de Algoritmos `_
de Paulo Feofiloff.
* `Turtle Graphics `_
* `Recursão `_ de `Resolução de Problemas com Algoritmos e Estruturas de Dados usando Python `_
de Brad Miller e David Ranum.
* `Recursão `_ de `Como Pensar Como um Cientista da Computação `_
de Brad Miller e David Ranum.
* `Recursion `_ de `Introduction to Programming in Python `_.
de Robert Sedgewick, Kevin Wayne e Robert Dondero.