Cost of naive recursion
- Input
- F(50) recursivo
- Expected output
- ≈ 2 × 10¹⁵ chamadas
The call tree doubles in size at every level; that is why the pure recursive version is never used beyond small values of n.
Carregando ferramenta… / Loading tool…
Fibonacci algorithms in computing
The naive recursive Fibonacci implementation costs O(2ⁿ) because it recomputes the same subproblems over and over; the iterative version costs O(n), a single pass keeping only the last two terms. This tool uses the iterative BigInt version, generating up to 500 terms, and avoids from the start the rounding error JavaScript's Number type makes starting at F(79).
The call tree doubles in size at every level; that is why the pure recursive version is never used beyond small values of n.
F(78) = 8,944,394,323,791,464 is still safe; F(79) already exceeds 9,007,199,254,740,991, the largest exact integer Number can represent.
This tool's iterative algorithm computes all 500 allowed terms in a single O(n) pass, with no recursive call at all.
It is a sequence of integers where each term is the sum of the two preceding ones: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34… It is defined by the recurrence F(n) = F(n−1) + F(n−2), with F(0) = 0 and F(1) = 1. It was popularized by Leonardo of Pisa ('Fibonacci') in the 13th century, in a problem about breeding rabbits.
Float64 represents exact integers only up to 2⁵³ − 1 = 9,007,199,254,740,991. F(79) already has 17 digits and crosses that ceiling, so any Number addition from that point risks rounding to the nearest representable integer, a silent error. BigInt has no such ceiling and keeps all 500 generated terms exact.
Both use the same recursive formula F(n) = F(n-1) + F(n-2), but the naive version recomputes every subproblem from scratch on each call, costing O(2ⁿ); memoization stores each already-computed F(k) in a table and reuses it, cutting the cost to O(n) at the expense of O(n) of extra memory.
Because the number's size grows along with n: F(499) has 104 digits, and every term beyond that adds more digits to the BigInt, with no practical gain for most uses. The limit keeps the response instant without affecting exactness, which stays guaranteed by BigInt for any value within the allowed range.
First 10 Fibonacci terms
0112358132134All calculations stay in your browser. No data is sent to any server.