Recalcular à toa: o Fibonacci ingênuo

A definição que engana

O Fibonacci é o exemplo que todo mundo usa para mostrar recursão, e com razão: a definição é linda de tão simples. Os dois primeiros números são dados, 0 e 1. Daí em diante, cada número é a soma dos dois que vêm antes dele. Escrever isso como função recursiva sai quase sozinho: se n é 0 ou 1, devolva o próprio n; senão, devolva fib de n menos 1 somado com fib de n menos 2. Três linhas, um caso base claro, duas chamadas que reduzem o problema. Pelo que você viu no módulo de recursão, parece o cenário ideal. E é aí que mora a armadilha.

O problema não está na resposta, que sai correta, mas no caminho até ela. Para calcular fib de 5, a função pede fib de 4 e fib de 3. Mas fib de 4, por sua vez, também pede fib de 3. Então fib de 3 é calculado duas vezes, do zero, por galhos diferentes que não conversam entre si. E fib de 2 aparece ainda mais vezes. Quanto maior o número, pior fica: a mesma conta é refeita uma montanha de vezes. A árvore de recursão, que no módulo passado mostrava o trabalho total, aqui denuncia um trabalho quase todo desperdiçado.

O desperdício em números

Dá para medir o estrago contando quantas vezes a função é chamada. Para fib de 5, a função ingênua faz quinze chamadas para achar um número que a gente calcula de cabeça. Para fib de 10, são mais de cem chamadas. Para fib de 30, são mais de um milhão. Para fib de 50, o número de chamadas passa de um bilhão, e o programa simplesmente trava. Repare que o valor final é pequeno e a definição é simples; o que explode é a quantidade de trabalho repetido. Cada valor intermediário é redescoberto vezes e vezes, porque nada é guardado entre uma chamada e outra.

funcao fib(n)
  se n <= 1 entao
    retorne n
  fim
  retorne fib(n - 1) + fib(n - 2)
fim

// para achar fib(5), esta funcao chama fib(3) duas vezes,
// fib(2) tres vezes, fib(1) cinco vezes... tudo do zero.
escreva(fib(6))

A função está correta, mas cada chamada abre duas novas, e valores como fib de 2 são recalculados várias vezes.

funcao fib(n)
  se n <= 1 entao
    retorne n
  fim
  retorne fib(n - 1) + fib(n - 2)
fim
escreva(fib(6))

O mesmo trabalho, de novo e de novo

Vale fixar a intuição, porque ela é a chave das próximas aulas. O Fibonacci ingênuo é lento não por causa da recursão em si, mas por causa da amnésia: a função esquece na hora tudo o que acabou de calcular. Cada vez que precisa de fib de 3, ela recomeça do zero, como quem soma a mesma coluna de números várias vezes sem anotar o resultado no papel. A cura, que vem na próxima aula, é ridícula de tão simples: anotar. Se a função guardasse cada resultado que já achou, nunca precisaria refazer, e o cálculo passaria de bilhões de passos para umas poucas dezenas.