4.7. Introdução: Visualizando Recursão¶

Na seção anterior, analisamos alguns problemas que eram fáceis de resolver usando recursão; no entanto, ainda pode ser difícil encontrar um modelo mental ou uma maneira de visualizar o que está acontecendo em uma função recursiva. Isso pode fazer com que recursão seja difícil para as pessoas entenderem. Nessa seção, vamos ver dois exemplos de uso de recursão para desenhar algumas figuras interessantes. Ao ver essas figuras serem construídas, você vai ganhar uma visão mais ampla sobre o processo de recursão que pode lhe ser útil na concretização do seu entendimento sobre recursão.

A ferramenta que vamos usar para criar nossas ilustrações é o módulo gráfico do Python chamado turtle (tartaruga). O módulo turtle faz parte de todas as versões do Python e é muito fácil de usar. A metáfora é bem simples. Você pode criar uma tartaruga e a tartaruga pode andar para frente (forward), para trás (backward), virar à esquerda (left), virar à direita (right), etc. A tartaruga pode mover sua cauda para cima (up) ou para baixo (down). Quando a cauda da tartaruga está para baixo e a tartaruga se move, ela desenha uma linha ao se mover. Para aumentar a qualidade dos desenhos a tartaruga você pode mudar a largura da cauda, ​​bem como a cor da tinta onde a cauda é mergulhada.

O exemplo a seguir ilustra alguns conceitos gráficos básicos para usar uma tartaruga. Usaremos o módulo turtle para desenhar uma espiral recursivamente. O ActiveCode 1 mostra como isso é feito. Depois de importar o módulo turtle criamos uma tartaruga. Quando uma tartaruga é criada, cria-se também uma janela para se desenhar. Em seguida, definimos a função drawSpiral. O caso base para esta função simples é quando o comprimento da linha que desejamos desenhar, dado pelo parâmetro lineLen, se tornar menor ou igual a zero. Se o comprimento da linha for maior que zero, instruiremos a tartaruga para avançar lineLen unidades e depois virar à direita 90 graus. O passo recursivo é quando chamamos drawSpiral novamente com um comprimento menor. No final do ActiveCode 1 você notará que chamamos a função myWin.exitonclick(). Esse é um método prático da janela que coloca a tartaruga em um modo de espera até que você clique dentro da janela, causando o término do programa.

Isso é realmente tudo que você precisa saber sobre o módulo gráfico turtle para fazer alguns desenhos bem impressionantes. Em nosso próximo programa, vamos desenhar uma árvore fractal. Fractais é um ramo da matemática que têm muito em comum com recursão. A definição de um fractal é que quando você olha para ele, o fractal mantem sua mesma forma básica não importa o quanto você a amplie. Alguns exemplos que ocorrem na natureza são as costas de continentes, flocos de neve, montanhas e até árvores ou arbustos. A natureza fractal de muitos desses fenômenos naturais permite que os programadores criem cenários muito realistas para filmes gerados por computador. No nosso próximo exemplo, vamos gerar uma árvore fractal.

Para entender como isso vai funcionar, é útil pensar em como podemos descrever uma árvore usando um vocabulário fractal. Lembre-se que dissemos acima que um fractal é algo que tem a mesma aparência em todos os diferentes níveis de ampliação. Se traduzirmos isso para árvores e arbustos, podemos dizer que mesmo um pequeno galho tem a mesma forma e características de uma árvore inteira. Usando esta ideia, poderíamos dizer que uma árvore é um tronco, com uma árvore menor indo para a direita e outra árvore menor indo para a esquerda. Se você pensar nesta definição recursivamente, significa que vamos aplicar a definição recursiva de uma árvore para ambas as árvores menores, à esquerda e à direita.

Vamos traduzir essa ideia para algum código em Python. A Listagem 1 mostra como podemos usar nossa tartaruga para gerar uma árvore fractal. Vamos olhar para o código um pouco mais de perto. Você vai ver que nas linhas 5 e 7 estamos fazendo uma chamada recursiva. Na linha 5, fazemos a chamada recursiva depois que a tartaruga vira 20 graus para a direita; esta é a árvore à direita mencionada acima. Então, na linha 7, a tartaruga faz outra chamada recursiva, mas desta vez depois de virar 40 graus à esquerda. A razão pela qual a tartaruga deve virar à esquerda em 40 graus é que ela precisa desfazer o giro inicial de 20 graus à direita e, em seguida, fazer um giro adicional de 20 graus à esquerda para desenhar a árvore da esquerda. Observe também que cada vez que fazemos uma chamada recursiva para tree subtraímos alguma quantidade do parâmetro branchLen; isso é para nos certificar de que as árvores recursivas ficam cada vez menores. Você também deve reconhecer o comando inicial if na linha 2, que verifica o caso base de branchLen ser muito pequeno.

Listagem 1

1
2
3
4
5
6
7
8
9

def tree(branchLen,t):
    if branchLen > 5:
        t.forward(branchLen)
        t.right(20)
        tree(branchLen-15,t)
        t.left(40)
        tree(branchLen-10,t)
        t.right(20)
        t.backward(branchLen)

O programa completo para este exemplo de árvore é mostrado no ActiveCode 2. Antes de executar o código, pense em como você espera ver a árvore no final. Olhe para a as chamadas recursivas e pense em como essa árvore se desdobrará. Será que vai ser desenhada simetricamente com as metades direita e esquerda da árvore se formando simultaneamente? Ou será que o lado direito será desenhado primeiro e depois o lado esquerdo?

Observe como cada ponto de ramificação na árvore corresponde a uma chamada recursiva e observe como a árvore é desenhada toda à direita, seguindo o caminho até seu galho mais curto. Você pode ver isto an Figura 1. Agora observe como o programa percorre o caminho de volta no tronco até que todo o lado da árvore é desenhado. Você pode ver a metade direita da árvore na Figura 2. Então o lado esquerdo da árvore é desenhado, mas não indo o mais longe possível para a esquerda. Em vez disso, mais uma vez todo o lado direito da árvore da esquerda é desenhado até que finalmente terminamos com o menor galho à esquerda.

Figura 1: O Início de uma Árvore Fractal¶

Figura 2: A Primeira Metade de uma Árvore¶

Este programa simples para desenhar árvores é apenas um ponto de partida. Você vai ver que a árvore não parece muito realista porque a natureza não é tão simétrica quanto um programa de computador. Os exercícios no final do capítulo fornecem algumas idéias de como explorar alguns opções interessantes para fazer sua árvore parecer mais realista.

    - Modifique a espessura dos ramos para que, quando branchLen fica menor, a linha fica mais fina.

    - Modifique a cor dos ramos para, quando branchLen ficar muito curto, ser colorido como uma folha.

    - Modifique o ângulo usado na rotação da tartaruga para que em cada ponto de ramificação o ângulo seja selecionado aleatoriamente dentro de algum intervalo. Por exemplo, escolha um ângulo entre 15 e 45 graus. Experimente vários valores para ver o que parece bom.

    - Modifique o branchLen para que, em vez de sempre subtrair a mesma quantidade, subtraia uma quantidade aleatória dentro de algum intervalo.