A sequência de Fibonacci gera números que crescem muito rapidamente. Ocorre que do jeito que você está fazendo, cada chamada recursiva vai criar outras chamadas recursivas que criam outras chamadas recursivas que criam outras chamadas recursivas... até que no final de cada chamada recursiva, é produzido um resultado 0 ou 1.
Eis um exemplo do que ocorre, com fibonacci(8)
:
Nesta tabela aí em cima, a coluna da esquerda representa a primeira chamada de fibonacci(8)
. Ela se reduz a duas outras chamadas a fibonacci(7)
e a fibonacci(6)
, que estão na segunda coluna. Cada uma dessas chamadas vai se subdividir várias vezes até que no final teremos um monte de zeros e uns.
Com isso podemos formar uma árvore de chamadas. Nas folhas dessas árvores temos zeros e uns que serão retornados para as funções chamadoras e serão somados até fornecer o resultado final, que é 21.
Observe que temos o número 1 aparecendo em 21 folhas. Também temos o número 0 aparecendo em 13 folhas. 13 também é o resultado de fibonacci(7)
. No total são 34 folhas, que é o resultado de fibonacci(9)
.
Se você montar essa árvore com outros números, você verá que para qualquer número n
, o número de folhas será fibonacci(n + 1)
, o número de folhas com 1 será fibonacci(n)
e o número de folhas com 0 será fibonacci(n - 1)
.
Cada uma dessas folhas requer um processamento para ser atingida. E no final, podemos ver que estamos na verdade apenas somando os resultados de um monte de zeros e uns. Isso é um número bem grande de somas. No total a operação de soma acontece fibonacci(n + 1) - 1
vezes.
Agora, peguemos o resultado de fibonacci(80)
, que é 23.416.728.348.467.684. Isso significa que o seu programa demorará uma eternidade para ficar somando um monte de zeros e uns até chegar a esse número. É por isso que o programa é lento. Utilizando a abordagem demonstrada na resposta do Antonio Carlos, isso é solucionado. Para calcular-se fibonacci(n)
, na verdade só são necessárias apenas (n - 1)
somas. Ou seja, para calcular fibonacci(80)
só precisamos de 79 somas na verdade.
Se observarmos essa árvore aí em cima, veremos que um monte de resultados são recalculados várias e várias e várias vezes. Assim sendo, se armazenarmos resultados intermediários já obtidos anteriormente em uma tabela, podemos posteriormente consultá-los ao invés de recalculá-los, deixando o programa mais eficiente. Esse é o princípio da programação dinâmica. Para calcular o fibonacci(n)
, temos que calcular primeiro o fibonacci(n - 1)
, até aí ok. Mas ao calcular o fibonacci(n - 1)
, já teremos calculado também o fibonacci(n - 2)
. Desta forma, não precisamos recalcular o fibonacci(n - 2)
, se tivermos guardado o resultado dele ao calcular o fibonacci(n - 1)
, basta somar esse resultado já guardado, o que evita ter que recomputá-lo.
No programa da resposta do Antonio Carlos, ele utiliza apenas as variáveis a
e b
. Isso ocorre porque na verdade só precisamos dos dois resultados mais recentes da tabela, pois ao calcular fibonacci(n)
, esses dois resultados mais antigos serão o fibonacci(n - 1)
e o fibonacci(n - 2)
. Desta forma, qualquer coisa depois do fibonacci(n - 3)
pode ser esquecida porque não será mais necessária. Assim sendo, podemos manter a tabela só com os dois últimos resultados ao representá-la apenas com duas variáveis, a
e b
. A variável f
é apenas uma variável auxiliar para que nada seja perdido enquanto a tabela está sendo alterada, fato esse evidenciado se o código dele for reescrito assim:
var fibonacci = function(n) {
var a = 0, b = 1;
for (var i = 2; i <= n; i++) {
var f = a;
a = b;
b += f;
}
return b;
};