Ver Feed RSS

root@blog:/# chmod o+r *

Python: Brincando com Recursividade

Avalie este Post de Blog
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!

Atualizado 30-07-2009 em 17:53 por Magnun

Categorias
Dicas , Python , Dicas

Comentários

  1. Avatar de PEdroArthurJEdi
    Muito bom estar vendo Python com frequência por aqui! É uma das formar de se familiarizar com a linguagem, vê-la todo dia!

    Sem falar na curva de aprendizado... Putz... muito acentuada...

    Quando a identação, só funciona nessas caixinhas:
    Código :
    def fati(n):
        f = 1
        while n:
            f *= n
            n -= 1
        return f
     
    def fatr(n):
        if n:
            return n * fatorial(n-1)
        return 1
  2. Avatar de Magnun
    Hum... Valeu pela dica! Já arrumei!
  3. Avatar de Marcelo C
    Não é "interação" e sim "iteração"
  4. Avatar de Magnun
    Corrigido! Obrigado, culpa do corretor ortográfico automático. XD

+ Enviar Comentário



Visite: BR-Linux ·  VivaOLinux ·  Dicas-L