The Fibonacci sequence starts with 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144. Each number is the sum of the two before it. It sounds like a trivial math exercise until you realize this sequence appears in sunflower seed spirals, stock market analysis, data structure design, and even the way your screen lays out content.
I want to walk through why this sequence matters beyond textbook examples and where you will actually encounter it as a developer.
The naive implementation teaches you recursion
Every CS course starts here:
function fib(n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
This is elegant and also terrible. The time complexity is O(2^n). Computing fib(40) makes over a billion function calls. Computing fib(50) will hang your browser tab. The reason is that the function recomputes the same values exponentially many times. fib(5) computes fib(3) twice. fib(6) computes fib(3) three times. By fib(40), the waste is astronomical.
Memoization turns it into O(n)
function fib(n, memo = {}) {
if (n in memo) return n;
if (n <= 1) return n;
memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
return memo[n];
}
This is the canonical introduction to dynamic programming. Store results you have already computed. Check the cache before recursing. The same principle applies to hundreds of real-world optimization problems.
The iterative approach is even better
function fib(n) {
if (n <= 1) return n;
let prev = 0, curr = 1;
for (let i = 2; i <= n; i++) {
[prev, curr] = [curr, prev + curr];
}
return curr;
}
O(n) time, O(1) space. No recursion overhead, no hash map lookups. For generating a sequence of Fibonacci numbers, this is the practical choice. It also avoids stack overflow issues that the recursive versions hit around n=10,000 in most JavaScript engines.
Where Fibonacci shows up in real software
Fibonacci heaps are a data structure used in Dijkstra's shortest path algorithm and Prim's minimum spanning tree algorithm. They achieve O(1) amortized time for insert and decrease-key operations, which makes certain graph algorithms faster.
Fibonacci hashing is a technique for hash table probe sequences that distributes keys more uniformly than linear probing. The magic constant is derived from the golden ratio (1.618...), which is the limit of consecutive Fibonacci number ratios.
Agile estimation uses Fibonacci numbers (1, 2, 3, 5, 8, 13, 21) for story points. The reasoning is that estimation uncertainty grows with task size, and Fibonacci spacing forces teams to make meaningful distinctions rather than agonizing over whether something is a 6 or a 7.
UI spacing systems sometimes use Fibonacci-based scales. Instead of arbitrary spacing tokens like 4, 8, 12, 16, 24, 32, a Fibonacci-based system uses 1, 2, 3, 5, 8, 13, 21, 34. The proportional growth between steps feels naturally harmonious because the ratio between consecutive values approaches the golden ratio.
The golden ratio connection
As n grows, the ratio fib(n) / fib(n-1) converges to the golden ratio, approximately 1.6180339887. This number appears in rectangle proportions considered aesthetically pleasing, in the spiral patterns of shells and galaxies, and in the branch angles of trees.
For closed-form computation, Binet's formula gives you the nth Fibonacci number directly:
F(n) = (phi^n - psi^n) / sqrt(5)
where phi = (1 + sqrt(5)) / 2 and psi = (1 - sqrt(5)) / 2. This runs in O(1) time but loses precision for large n due to floating-point limitations. For exact results beyond about n=70, you need arbitrary-precision arithmetic.
Generating large sequences
If you need Fibonacci numbers for testing, algorithm validation, or mathematical exploration, generating them by hand is tedious and generating them in code requires handling big integers. JavaScript's native number type loses precision after fib(78), and even BigInt calculations get slow for very large indices.
I built a Fibonacci generator at zovo.one/free-tools/fibonacci-generator that produces Fibonacci sequences up to whatever length you need, with exact values. It handles the big-number arithmetic and gives you the sequence in a format you can copy directly into your code or analysis.
I'm Michael Lip. I build free developer tools at zovo.one. 500+ tools, all private, all free.
Top comments (0)