Python: Brincando com Recursividade
por
em 06-03-2009 às 12:44 (9176 Visualizações)
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):
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]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]
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]>>> fatorial(0) 1 >>> fatorial(1) 1 >>> fatorial(2) 2 >>> fatorial(3) 6 >>> fatorial(4) 24 >>> fatorial(5) 120 >>> fatorial(15) 1307674368000L[/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.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]
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):
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, 100) 0.18700003623962402 >>> compara(fatorial2, 990, 100) 0.28099989891052246 >>>[/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!Código :[FONT=Courier New][COLOR=DimGray]>>> compara(fatorial, 990, 1000) 2.0729999542236328 >>> compara(fatorial2, 990, 1000) 2.9140000343322754[/COLOR][/FONT]
Comentários
+ Enviar Comentário