Introdução à Programação com o UCB Logo/Recursão

Recursividade é um processo de repetição utilizado para simplificar a resolução de um problema em subproblemas do mesmo tipo. Em programação, teremos um processo recursivo quando este for definido em função dele mesmo. Vejamos um exemplo conhecido da matemática: o cálculo do fatorial de um número. O fatorial de um número N é dado pelo produto de N com o fatorial de N-1.

$N!=N(N-1)!$

Por definição o fatorial de zero é igual a um (0!=1). Desta forma, para calcular o fatorial de um número qualquer podemos criar um algoritmo recursivo. Em Logo, podemos fazer a seguinte função para calcular o fatorial de um número:

to fatorial :n
ifelse :n > 0 [output n * fatorial :n-1] [output 1]
end

E como alguns exemplos, podemos verificar o seu funcionamento:

? print fatorial 0
1
? print fatorial 1
1
? print fatorial 2
2
? print fatorial 3
6
? print fatorial 4
24
? print fatorial 5
120
? print fatorial 6
720
? print fatorial 7
5040
? print fatorial 8
40320

Exemplo

Este exemplo apresenta um algoritmo recursivo para desenhar os triângulos ilustrados na figura ao lado.

Recursive Triangles

to triangle :x
repeat 3 [fd :x lt 120]
end

to rtriangle :x :n
triangle :x
fd :x/2 lt 60
if :n > 1 [rtriangle :x/2 :n-1]     
end

? rtriangle 200 5

Fractais

Fractais são figuras da geometria não-Euclidiana, em que as partes do todo possuem as características do todo. O termo fractal foi criado em 1975 por Benoît Mandelbrot, matemático francês nascido na Polônia, que descobriu a geometria fractal na década de 70 do século XX, a partir do adjetivo latino fractus, do verbo frangere, que significa quebrar.

Os fractais são objetos que apresentam auto-similaridade, ou recorrência. Por este motivo, é natural implementar computacionalmente o cálculo de fractais utilizando a recorrência.

Um exemplo de fractal muito conhecido é a [curva de Koch].

Construção da curva de Koch

O processo de construção da curva de Koch consiste em aplicar recursivamente os seguintes passos, partindo de um segmento de recta.

1. Divide-se o segmento de recta em três segmentos de igual comprimento.
2. Substitui-se o segmento do meio por dois lados de um triângulo equilátero (fazendo um ângulo de π/3 radianos (60 graus)), o resultado terá o formato de um chapéu.
3. O procedimento é repetido a cada um dos segmentos que constituem a nova figura.

O resultado da aplicação deste procedimento pode ser observado passo-a-passo na figura ao lado.

O exemplo abaixo é um algoritmo recursivo em Logo para construir a curva de Koch. Os parâmetros utilizados são o tamanho do segmento inicial e o número de recursões que serão realizadas.

to koch :x :n
ifelse :n = 0 [fd :x] [ koch :x/3 n-1 lt 60 koch :x/3 :n-1 rt 120 koch :x/3 :n-1 lt 60 koch :x/3 n-1 ]
end

? koch 300 5

Problema

Faça um programa em Logo para desenhar o [Triângulo de Sierpinski].

Triângulo de Sierpinski