Funções Recursivas

Hoje vou entrar num assunto que costuma espantar algumas pessoas, mas que pode ser bastante útil na criação de algoritmos para a resolução de problemas computacionais: as funções recursivas.

Funções recursivas são funções que chamam a si mesma de forma que, para resolver um problema maior, utiliza a recursão para chegar as unidades básicas do problema em questão e então calcular o resultado final.

Hmm... Ainda parece difícil de entender, certo? Bom, vamos ver como isto se aplica na prática. Voltamos ao nosso primeiro problema: a sequencia de Fibonacci. Nela nós temos dois casos base: O primeiro elemento da sequencia sempre é 1, assim como o segundo elemento da sequencia também é sempre 1.

Temos então o caso base. Para calcular os demais, utilizamos o seguinte parâmetro: o valor "i" da sequencia será o valor "i-1" da sequencia somado ao valor "i-2" da sequencia. Ou seja: fibonacci(i) = fibonacci(i - 1) + fibonacci(i - 2). Perceberam como podemos recorrer à própria funcão para calcular o valor de um elemento da sequencia? Vejamos como isto se traduz em código Python:

# coding: utf-8
# fib_recursivo.py

def fibonacci(indice):
    if indice == 1 or indice == 2:
        return 1
    return fibonacci(indice - 1) + fibonacci(i - 2)

A função agora ficou bem mais simples de entender que as versões anteriores com "for" e "while", certo? Pelo menos para mim esta forma é bem mais legível e podemos perceber diretamente como é o seu funcionamento. No entanto, as funções recursivas embutem alguns problemas. Pois é! Nem tudo é maravilhas no mundo de Alice!

A esta altura, você já sabe de algum problema que acontecerá com esta função?

Bom, o primeiro problema está na repetição do cálculo do mesmo valor. Vejamos um exemplo: calcular o quinto valor da sequencia.

1 =>                      x    =           fibonacci(5)
                                        /                 \
2 =>                      x    = fibonacci(4)    +       fibonacci(3)
                                  /       \                /        \
3 =>             x =   fibonacci(3) + fibonacci(2) + fibonacci(2) + fibonacci(1)
...
...

Perceba que, no passo 2 precisamos calcular o fibonacci(4) e o fibonacci(3). Então, no passo 3, precisamos calcular novamente o fibonacci(3) para encontrar o valor do fibonacci(4) do passo 2.

Mas existem outro problema com as funções recursivas. A pilha de chamadas não pode ser infinita, e alguns compiladores ou interpretadores limita o número máximo de chamadas a funções na pilha. Explico: Quando chamamos fibonacci(5), esta chamada irá chamar primeiramente fibonacci(4), sendo assim, a primeria chamada é colocada numa pilha e o controle passa para a segunda chamada. Então, fibonacci(4) chama fibonacci(3), sendo colocada também na pilha enquanto fibonacci(3) assume o controle. Agora imagine que você chamou fibonacci(1000). Quando a chamada chegar a fibonacci(2) serão 998 chamadas de função na pilha, sem contar que cada chamada ainda irá chamar uma segunda ramificação. Se você tentar desenhar uma árvove com as chamadas, verá que a coisa fica bem complexa.

Então meu conselho é o seguinte: use funções recursivas com cautela. Elas são ótimas para solucionar vários tipos de problemas, mas se você notar que a função está duplicando o trabalho ou que a pilha de chamadas será muito grande de acordo com o grau de recursividade, tente uma nova estratégia, como utilizar um algoritmo linear, sem recursão.

Para o exercício hoje vou fazer um pouco diferente. Vou propor um exercício simples e um desafio, um pouco mais complexo. O exercício é escrever um módulo com duas funções: a primeira calcula o fatorial de um número de forma recursiva e a segunda efetua o mesmo cálculo de forma linear, sem recursão.

O desafio é escrever um módulo que calcula a solução do problema da Torre de Hanoi. Tal solução pode ser encontrada de forma simples mas engenhosa utilizando recursão.

Para quem não conhece, a Torre de Hanoi consiste em ter 3 pinos onde no primeiro pino são postos "n" anéis de tamanhos decrescente. O problema é mover todos os "n" anéis para um pino destino, utilizando o terceiro pino como auxiliar, movendo sempre apenas um anel por vez e com a restrição de que num pino não se pode ter um anel menor abaixo de um anel maior.

É isto! Ainda nesta semana post a solução dos exercícios e do desafio. Até a próxima!