Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como utilizar recursão para desenhar fractais no Python?

+2 votos
205 visitas

1 Resposta

+3 votos
respondida Mar 29, 2017 por Peng Yaohao (101 pontos)  
editado Mar 30, 2017 por Peng Yaohao

Fractais são figuras geométricas que seguem uma estrutura de auto-similaridade -- ou seja, suas partes são compostas por versões menores e semelhantes ou idênticas ao todo. Vamos ilustrar com fractal denominado "Ilhas de Koch" (conforme ilustrado na página 8 do livro The Algorithmic Beauty of Plants, de Przemyslaw Prusinkiewicz e Aristid Lindenmayer (1991)). Basicamente, começamos com uma linha reta:

A imagem será apresentada aqui.

Substituiremos esse percurso pela seguinte trajetória:

  • Avançar \(\frac{X}{4}\) unidades;
  • Virar \(90°\) para a direita;
  • Avançar \(\frac{X}{4}\) unidades;
  • Virar \(90°\) para a esquerda;
  • Avançar \(\frac{X}{4}\) unidades;
  • Virar \(90°\) para a esquerda;
  • Avançar \(\frac{X}{2}\) unidades;
  • Virar \(90°\) para a direita;
  • Avançar \(\frac{X}{4}\) unidades;
  • Virar \(90°\) para a direita;
  • Avançar \(\frac{X}{4}\) unidades;
  • Virar \(90°\) para a esquerda;
  • Avançar \(\frac{X}{4}\) unidades.

Para implementar essa recorrência, utiliza-se da recursão -- basicamente, a função chamar ela mesma até atingir um caso base, que nesse caso é um deslocamento simples (o comando "t.forward(d)" faz o objeto do desenho avançar d unidades). O código implementado em Python segue abaixo:

import turtle
def fractal(t, n, d):
    if n == 0:
        t.forward(d)
    else:
        for angulo in [-90,90,90,0,-90,-90,90,0]:
            fractal(t, n-1, d/4)
            t.left(angulo)

No primeiro nível onde \(n=1\), a função irá executar o caso em que \(n=0\) com comprimento igual a \(\frac{1}{4}\) do original, e virar o respectivo ângulo definido na lista ``angulo'' (o pacote turtle atribui valores negativos para virar ângulos para a direita). A função "fractal" irá chamar ela mesma para valores inteiros de \(n\) menores atá atingir o caso-base para \(n=0\) de um deslocamento simples. O resultado para \(n=1\) segue como abaixo:

obj= turtle.Turtle()
obj.speed(0)
fractal(obj,1,300)

A imagem será apresentada aqui.

Podemos replicar esse padrão indefinidamente! Ou seja: podemos aplicar o mesmo padrão para cada pequeno segmento de reta da imagem acima, de modo a obter uma figura com segmentos de \(\frac{X}{16}\) unidades de comprimento cada. Observe o que acontece quando rodamos para o caso \(n=2\): a função irá replicar o padrão do nível \(n=1\) para cada deslocamento simples da figura anterior, e então virar os respectivos ângulos. O nível \(n=1\) por sua vez irá chamar o nível \(n=0\), resultando em deslocamentos com
comprimentos proporcionalmente menores:

fractal(obj,2,300)

A imagem será apresentada aqui.

Para qualquer \(n\in\mathbb{N}\), podemos chamar a função para o nível \(n\), de modo que a função chamará ela mesma para o nível \(n-1\), e depois \(n-2\), e assim sucessivamente até o nível \(0\). Observe o resultado para os níveis \(n=3\) e \(n=4\).

fractal(obj,3,300)

A imagem será apresentada aqui.

fractal3(obj,4,300)

A imagem será apresentada aqui.

Para completar a figura das Ilhas de Koch, basta replicar esse padrão todo 4 vezes, virando 90 graus a cada execução para fechar um ``quadrado''. Para \(n=0\), a figura é de fato um quadrado:

obj.color('black', 'blue')
obj.begin_fill()
for i in range(4):
    fractal(obj,0,250)
    obj.right(90)
obj.end_fill()    
turtle.done()

A imagem será apresentada aqui.

Observe a recorrência do fractal para \(n=1,2,3,4\)

obj.color('black', 'blue')
obj.begin_fill()
for i in range(4):
    fractal(obj,1,250)
    obj.right(90)
obj.end_fill()    
turtle.done()

A imagem será apresentada aqui.

obj.color('black', 'blue')
obj.begin_fill()
for i in range(4):
    fractal(obj,2,250)
    obj.right(90)
obj.end_fill()    
turtle.done()

A imagem será apresentada aqui.

obj.color('black', 'blue')
obj.begin_fill()
for i in range(4):
    fractal(obj,3,550)
    obj.right(90)
obj.end_fill()    
turtle.done()

A imagem será apresentada aqui.

obj.color('black', 'blue')
obj.begin_fill()
for i in range(4):
    fractal(obj,4,750)
    obj.right(90)
obj.end_fill()    
turtle.done()

A imagem será apresentada aqui.

Note que o perímetro da figura dobra a cada nível, mas a sua área permanece constante!

comentou Abr 3, 2017 por Caue (226 pontos)  
Ficou bem legal!
comentou Mai 24, 2017 por João Gabriel Souza (81 pontos)  
O exercício ficou bem interessante. Exercício correto, bem explicado e didático, apresentado de forma simples e elucidativa. O que facilita o entendimento do assunto para quem é iniciante em programação.

Apenas faria uma sugestão de deixar mais claro que o fractal ao compor versões menores e idênticas ao todo representa um processo recursivo. Ou seja, utiliza-se da recursão por ser uma técnica para solução de problemas computacionais em que problemas grandes podem ser reduzidos a problemas menores de mesma forma.
...