root@blog:/# chmod o+r *

Recursividade é um recurso muito legal na programação. Ela resume rotinas e torna possível códigos que antes poderiam ser muito complexo!

O Python, claro, não podia ficar de fora da brincadeira da recursividade! Vou mostrar aqui alguns exemplos de como usar a recursividade, para isso temos que ter pelo menos o conceito básico de funções.

Vamos ao exemplo básico que todo professor de faculdade usa pra explicar recursividade: Cálculo de fatorial. Por definição o fatorial de zero é 1 e pro restante dos números (positivos) o fatorial é calculado com base no produto dos numeros que o antecedem até o um.

Ex:
Fatorial de 3 é 3*2*1 = 6
Fatorial de 5 é 5*4*3*2*1 = 120

Deu pra pegar ne?! Então vamos a um exemplo, um código em python que calcula o fatorial de um número (sem o uso da recursividade):

Código :

[FONT=Courier New][COLOR=DimGray]def fatorial[/COLOR][/FONT][FONT=Courier New][COLOR=DimGray](numero):
     if numero is 0:
         return 1
     [/COLOR][/FONT][FONT=Courier New][COLOR=DimGray]fat = 1
     [/COLOR][/FONT][FONT=Courier New][COLOR=DimGray]while num is not 0
         [/COLOR][/FONT][FONT=Courier New][COLOR=DimGray]fat = fat * numero
         [/COLOR][/FONT][FONT=Courier New][COLOR=DimGray]numero = numero - 1
         [/COLOR][/FONT][FONT=Courier New][COLOR=DimGray]return fat[/COLOR][/FONT]

Nada muito complexo certo?! Tratamos a excessão do zero e fizemos um loop que decrementa o numero passado e multiplica. vamos testar:

Código :

[FONT=Courier New][COLOR=DimGray]>>> fatorial(0)
1
>>> fatorial(1)
1
>>> fatorial(2)
2
>>> fatorial(3)
6
>>> fatorial(4)
24
>>> fatorial(5)
120
>>> fatorial(15)
1307674368000L[/COLOR][/FONT]

Funcionando. Agora vamos observar um pouco mais a teoria do fatorial: fatorial(5) = 5*4*3*2*1, fatorial(4) = 4*3*2*1. Perceberam?! fatorial(5) = 5*fatorial(4). Ai entra a recursividade:

Código :

[FONT=Courier New][COLOR=DimGray]def fatorial[/COLOR][/FONT][FONT=Courier New][COLOR=DimGray]2(numero):
     [/COLOR][/FONT][FONT=Courier New][COLOR=DimGray]if numero is 0:
         [/COLOR][/FONT][FONT=Courier New][COLOR=DimGray]return 1
     [/COLOR][/FONT][FONT=Courier New][COLOR=DimGray]return numero*fatorial2(numero-1)[/COLOR][/FONT]

Ok, a primeira vista é complicado! Mas é só você observar e fará sentido. A grande jogada da recursividade é você saber definir um limite. Quando estudei estrutura de dados em C, tive que fazer uma biblioteca que representasse filas, pilhas, listas e árvores. A implementação das árvores é completamente recursiva. Já as listas utilizamos recursividade para realizar buscas binárias.

A recursividade é muito utilziada quando precisamos "vasculhar" algo que não temos idéia de como é, como por exemplo uma estrutura de arquivos.

A recursão consome um pouco mais de recursos que a iteração pois ele "mantêm" os dados de cada recursão. Fiz uma comparação, calculando 100 vezes o fatorial de 990 utilizando os dois métodos, recursão (fatorial2) e iteração (fatorial):

Código :

[FONT=Courier New][COLOR=DimGray]>>> compara(fatorial, 990, 100)
0.18700003623962402
>>> compara(fatorial2, 990, 100)
0.28099989891052246
>>>[/COLOR][/FONT]

A iteração é quase um décimo de segundo mais rápido. Agora para 1000 vezes o cálculo do fatorial;

Código :

[FONT=Courier New][COLOR=DimGray]>>> compara(fatorial, 990, 1000)
2.0729999542236328
>>> compara(fatorial2, 990, 1000)
2.9140000343322754[/COLOR][/FONT]

Podemos ver que o tempo sobe pra quase 9 décimos de segundo. Mas isso não implica que recursividade é pior. Alguns problemas só podem ser resolvidos com recursividade!