Mostrar código-fonte de 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''.
:<math>N! = N (N-1)!</math>
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:
<source lang=html4strict>
to fatorial :n
ifelse :n > 0 [output n * fatorial :n-1] [output 1]
end
</source>
E como alguns exemplos, podemos verificar o seu funcionamento:
<source lang=html4strict>
? 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
</source>

== Exemplo ==
Este exemplo apresenta um algoritmo recursivo para desenhar os triângulos ilustrados na figura ao lado.
[[File:Recursive Triangles.png|thumb|Recursive Triangles]]

<source lang=html4strict>
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
</source>


== 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 [[http://pt.wikipedia.org/wiki/Koch_snowflake curva de Koch]].
[[Ficheiro:Koch_snowflake0192.png|right|thumb|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.
# 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.
<source lang=html4strict>
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
</source>


== Problema ==
Faça um programa em Logo para desenhar o [[http://pt.wikipedia.org/wiki/Tri%C3%A2ngulo_de_Sierpinski Triângulo de Sierpinski]].

[[Ficheiro:SierpinskiTriangle.PNG|right|thumb|Triângulo de Sierpinski]]

[[Categoria:Programação]]