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.
É a sequência de inteiros em que cada termo é a soma dos dois anteriores: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34... Define-se por F(n) = F(n−1) + F(n−2), com F(0) = 0 e F(1) = 1. Leonardo de Pisa, o Fibonacci, a apresentou na Europa em 1202 no Liber Abaci, num problema sobre a reprodução de coelhos. A sequência já era conhecida na matemática indiana, em estudos de métrica poética.
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.
4181| Índice | Valor | Paridade |
|---|---|---|
| F(0) | 0 | par |
| F(1) | 1 | ímpar |
| F(2) | 1 | ímpar |
| F(3) | 2 | par |
| F(4) | 3 | ímpar |
| F(5) | 5 | ímpar |
| F(6) | 8 | par |
| F(7) | 13 | ímpar |
| F(8) | 21 | ímpar |
| F(9) | 34 | par |
| F(10) | 55 | ímpar |
| F(11) | 89 | ímpar |
| F(12) | 144 | par |
| F(13) | 233 | ímpar |
| F(14) | 377 | ímpar |
| F(15) | 610 | par |
| F(16) | 987 | ímpar |
| F(17) | 1597 | ímpar |
| F(18) | 2584 | par |
| F(19) | 4181 | ímpar |
Os cálculos ficam apenas no navegador. Nenhum dado é enviado ao servidor.