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.
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
editarEste exemplo apresenta um algoritmo recursivo para desenhar os triângulos ilustrados na figura ao lado.
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
editarFractais 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].
O processo de construção da curva de Koch consiste em aplicar recursivamente os seguintes passos, partindo de um segmento de recta.
- Divide-se o segmento de recta em três segmentos de igual comprimento.
- 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.
- 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
editarFaça um programa em Logo para desenhar o [Triângulo de Sierpinski].