algoritmos de Fibonacci em computação
A implementação recursiva ingênua de Fibonacci custa O(2ⁿ) porque recalcula os mesmos subproblemas repetidas vezes; a iterativa custa O(n), uma única passada guardando só os dois últimos termos. Esta ferramenta usa a versão iterativa com BigInt, gerando até 500 termos, e evita de saída o erro de arredondamento que o tipo Number do JavaScript comete a partir de F(79).
A árvore de chamadas dobra de tamanho a cada nível; é por isso que a versão recursiva pura nunca é usada além de valores pequenos de n.
F(78) = 8.944.394.323.791.464 ainda é seguro; F(79) já passa de 9.007.199.254.740.991, o maior inteiro exato que Number representa.
O algoritmo iterativo desta ferramenta calcula os 500 termos permitidos numa única passada O(n), sem nenhuma chamada recursiva.
É uma sequência de números inteiros onde cada termo é a soma dos dois anteriores: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34… Ela é definida pela recorrência F(n) = F(n−1) + F(n−2), com F(0) = 0 e F(1) = 1. Foi popularizada por Leonardo de Pisa ('Fibonacci') no século XIII, num problema sobre a reprodução de coelhos.
Float64 representa inteiros exatos só até 2⁵³ − 1 = 9.007.199.254.740.991. F(79) já tem 17 algarismos e ultrapassa esse teto, então qualquer soma feita em Number a partir daí arrisca arredondar para o inteiro mais próximo representável, um erro silencioso. BigInt não tem esse teto e mantém os 500 termos gerados exatos.
As duas usam a mesma fórmula recursiva F(n) = F(n-1) + F(n-2), mas a ingênua recalcula cada subproblema do zero a cada chamada, custando O(2ⁿ); a memoização guarda cada F(k) já calculado numa tabela e o reaproveita, reduzindo o custo para O(n) às custas de O(n) de memória extra.
Porque o tamanho do número cresce junto com n: F(499) tem 104 algarismos, e cada termo além disso soma mais dígitos ao BigInt, sem ganho prático para a maioria dos usos. O limite mantém a resposta instantânea sem afetar a exatidão, que continua garantida pelo BigInt em qualquer valor dentro do intervalo permitido.
Primeiros 10 termos de Fibonacci
0112358132134Os cálculos ficam apenas no navegador. Nenhum dado é enviado ao servidor.