Last updated
The Fibonacci Sequence
The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... It was described by Leonardo of Pisa (Fibonacci) in his 1202 book Liber Abaci, though it was known in Indian mathematics centuries earlier.
The sequence appears throughout nature: the spiral arrangement of sunflower seeds, the branching of trees, the arrangement of leaves on a stem, and the spiral of nautilus shells all follow Fibonacci proportions. The ratio of consecutive Fibonacci numbers converges to the golden ratio φ ≈ 1.6180339887...
Implementations
// Iterative — O(n) time, O(1) space
function fibonacci(n) {
if (n <= 1) return n;
let [a, b] = [0, 1];
for (let i = 2; i <= n; i++) [a, b] = [b, a + b];
return b;
}
// Generator — yields the sequence lazily
function* fibSequence() {
let [a, b] = [0, 1];
while (true) {
yield a;
[a, b] = [b, a + b];
}
}
// Get first 10 Fibonacci numbers
const gen = fibSequence();
const first10 = Array.from({ length: 10 }, () => gen.next().value);
// [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
// Closed-form (Binet's formula) — works for small n
function fibBinet(n) {
const phi = (1 + Math.sqrt(5)) / 2;
return Math.round(Math.pow(phi, n) / Math.sqrt(5));
}Fibonacci in Computer Science
- Algorithm analysis: Naive recursive Fibonacci is the classic example of exponential time complexity O(2ⁿ) vs. memoized O(n).
- Fibonacci heap: A data structure used in Dijkstra's algorithm with amortized O(1) decrease-key operations.
- Fibonacci search: A divide-and-conquer search algorithm that uses Fibonacci numbers to divide the search space.
- Pseudorandom number generation: Lagged Fibonacci generators are used in some PRNGs.
The Golden Ratio
As n increases, F(n+1)/F(n) converges to φ = (1 + √5) / 2 ≈ 1.618. F(10)/F(9) = 55/34 ≈ 1.6176. F(20)/F(19) = 6765/4181 ≈ 1.61803. The golden ratio appears in art, architecture, and design — the Parthenon, Leonardo da Vinci's Vitruvian Man, and many modern logos use golden ratio proportions.