17. Hilbert com tartarugas

"Adoramos o caos porque amamos produzir ordem."

Maurits Cornelis Escher

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.

Recursão está na arte, está na matemática, está na computação.

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 🎨. Os rastros feitos por tartarugas 🐢 que percorrerão o traçado da curva serão nosso pincel. 🤨 Essa será uma visão muito interessante e fofa de recursão visual bidimensional. 🧑🏾‍🎨 👩🏻‍🎨

17.1. 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.

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.

Começaremos dando uma volta pela vizinhança do módulo das curvas de Hilbert e depois iremos para o mundo das tartarugas 🐢 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! 🕵️‍♀️ 🕵🏼

17.2. Introdução

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? 🤔

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 🤔, mas podemos ter a impressão que há algum.

Neste passeio, para começar, investigaremos 🕵🏽 de perto, com uma lupa 🔎, 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é?! 🆒

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 🐢 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.

17.3. Curvas 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 🖥️ 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.

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 \(H_0, H_1, H_2, \ldots\). \(H_0\) é a curva vazia, \(H_1\) e \(H_2\) estão acima e \(H_3\) logo abaixo. Pode parecer estranho termos uma curva como \(H_0\). Pode até ser estranho 🙄, mas é conveniente. 🤨.

Cada curva \(H_i\) é denominada de curva de Hilbert de ordem \(i\) em homenagem a seu criador, o matemático David Hilbert. Abaixo vemos a curva de Hilbert de ordem \(\mathtt{4}\).

Notemos as semelhanças entre as curvas e que quanto maior o índice \(i\) do \(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 \(\mathtt{k}\) desenhar a curva de Hilbert de ordem \(\mathtt{k}\).

Vamos primeiro ao caça 🏹 do esquema recursivo. Observando as curvas com atenção 🧐, muita atenção 🤓. Podemos notar que a curva \(H_{i+1}\) contém quatro cópias de \(H_{i}\), uma em cada canto, ligadas por três linhas.

Por exemplo, \(H_{1}\) é obtida a partir de quatro cópias de \(H_{0}\), a curva vazia, ligada por três linhas, duas horizontais e uma vertical. A curva \(H_{2}\) é obtida a partir de quatro cópias de \(H_{1}\), convenientemente rotacionadas, ligadas por três linhas. Espere ai… 🛑 🤚 Se olharmos apenas para as três linhas que ligam os \(H_{1}\) vemos que elas formam um \(H_{1}\). Na imagem abaixo as quatro copias de \(H_1\) estão em vermelho e a três linhas ligando-as então em azul com uma flecha indicando cada uma delas.

Para traçarmos \(H_{2}\) podemos, começando em um ponto inicial:

• desenhar uma curva \(H_{1}\) com a sua abertura para cima;
• traçar um linha para a esquerda;
• desenhar uma curva \(H_{1}\) com a sua abertura para a direira;
• traçar um linha para baixo;
• desenhar uma curva \(H_{1}\) com a sua abertura para a direira;
• traçar um linha para a direita; e
• desenhar uma curva \(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?! ¯\_(ツ)_/¯

Exminemos agora a curva \(H_{3}\). Por sua vez, \(H_{3}\) é formado por quatro \(H_{2}\), convenientemente rotacionadas, ligados por três linhas.

De maneira semelhante ao que fizemo para traçarmos \(H_{2}\), para traçarmos \(H_3\) podemos, começando em um ponto inicial:

• desenhar uma curva \(H_{2}\) com a sua abertura para cima;
• traçar um linha para a esquerda;
• desenhar uma curva \(H_{2}\) com a sua abertura para a direira;
• traçar um linha para baixo;
• desenhar uma curva \(H_{2}\) com a sua abertura para a direira;
• traçar um linha para a direita; e
• desenhar uma curva \(H_{2}\) com a sua abertura para baixo.

Seguindo na mesma linha de raciocínio, \(H_{4}\) contém quatro \(H_{3}\), ligados por três linhas.

Podemos parar por aqui nossa procura por evidências e partir para uma descrição compacta das curvas.

17.4. 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 \(A\), \(B\), \(C\) e \(D\) de tal forma que:

• \(A_i\) será o padrão de ordem \(i\) com a abertura para a direita;
• \(B_i\) será o padrão de ordem \(i\) com a abertura para a baixo;
• \(C_i\) será o padrão de ordem \(i\) com a abertura para a esquerda; e
• \(D_i\) será o padrão de ordem \(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 👀 em alguns exemplos. Padrões das curvas \(A_1\) e \(A_2\) com abertura para a direita.

Agora vejamos as curvas \(B_2\) e \(B_3\) com abertura para baixo.

A seguir estão as curvas \(C_2\) e \(C_3\) com abertura para esquerda.

Por último, a curva \(D_4\) com abertura para cima.

Dessa forma temos que \(H_1\) é \(A_1\), \(H_2\) é \(A_2\), \(H_3\) é \(A_3\),… 🤔

17.5. Esquema recursivo

Agora estamos no ponto para descrever o esquema recursivo para desenhar uma curva de Hilbert de ordem \(k\). Na nossa descrição teremos em mente que o desenho começa em algum canto superior direito. Utilizaremos, símbolos:

• \(\rightarrow\) para indicar que o pincel deve se mover para direita; ➡️
• \(\uparrow\) para indicar que o pincel deve se mover para cima; ⬆️
• \(\leftarrow\) para indicar que o pincel deve se mover para esquerda; e ⬅️
• \(\downarrow\) para indicar que o pincel deve se mover para baixo. ⬇️

Utilizando as flechas acima chegamos a seguinte descrição recursiva das curvas:

• \(A_k = D_{k-1} \leftarrow A_{k-1} \downarrow A_{k-1} \rightarrow B_{k-1}\)
• \(B_k = C_{k-1} \uparrow B_{k-1} \rightarrow B_{k-1} \downarrow A_{k-1}\)
• \(A_k = D_{k-1} \rightarrow A_{k-1} \uparrow A_{k-1} \leftarrow B_{k-1}\)
• \(A_k = D_{k-1} \downarrow A_{k-1} \rightarrow A_{k-1} \uparrow B_{k-1}\)

Tudo bem?! ¯\_(ツ)_/¯ 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.

17.6. Mundo das tartarugas

Para fazermos os desenhos utilizaremos o módulo Turtle Graphics do Python. O nome Turtle, tartaruga 🐢 vem da ideia de que para desenharmos em uma janela devemos pensar em tartarugas se movendo e deixando seus rastros. Faz sentido? ¯\_(ツ)_/¯ Veja o pequeno exemplo na janela do Trinket que está a abaixo. Para executar o programa, como sempre, basta clicar em Run.

Inicialmente, para criarmos o mundo das tartarugas, colocar tartaurags nesse mundo e move-las, devemos carrega o módulo turtle fazendo:

import turtle

Criamos o mundo ou janela onde as tartarugas podemos levar as tartarugas 🐢 para passear deixando seus rastros escrevendo algo como:

janela = turtle.Screen()

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:

leornado = turtle.Turtle()
raphael  = turtle.Turtle()
donatelo = turtle.Turtle()
michelangelo = turtle.Turtle()

Cada tartaruga é um objeto da classe turtle.Tutle:

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 ➡️, fazemos

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 🐢, 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.

# 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:

# 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.

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 <https://hourofpython.trinket.io/a-visual-introduction-to-python#/multiple-turtles/turtles-are-objects>`_.

Agora sabemos o suficiente sobre tartarugas para voltarmos às curvas de Hilbert.

17.7. Curvas como rastros

No nosso caso utilizaremos uma tartarugas 🐢 do módulo Turtle como pincel para desenhar as curvas.

Para desenhar as curvas faremos várias chamada a função

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 🐢 que ao se move deixa o seu rastro na tela. A direção será indicada por um dos apelidos a seguir:

# 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.

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 Esquema recursivo para desenhar a curva \(A_k\).

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 \(B_k\), c() que desenha as curvas \(C_k\), d() que desenha as curvas \(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.

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

17.8. 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 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 \(H_0\). 😵 Já quando temos k > 0 desenhamos \(H_k\) recursivamente combinando o desenho de instâncias menores, curvas mais simples, que são quatro cópias de \(H_{i-1}\).

Também passamos pelo parque e brincamos com a construção de desenhos usando as tartarugas 🐢 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.

17.9. Verifique se entendeu

1. 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 Introdução deste capítulo.

2. Escreva um programa que produz o rastro de uma recursão de cauda como na animação a seguir.

   

3. 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.

   

4. 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.

   

5. 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.

   

6. Escreva as funções b(), c() e d() que são semelhantes à função a() e respeitam o Esquema recursivo.

17.10. O que é …

Aqui vai um lista de termos que usamos nesse capítulo e os seus significados. 🤓

Função recursiva

Função que possui chamadas diretas ou indiretas a si mesma. 😵

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.

17.11. 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.