Fibonacci Sequence Algorithm

The Fibonacci sequence is every programmer's first encounter with recursion — and with why naive recursion can destroy performance.

What It Is

Each number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34...

Simple definition. Deceptively expensive to compute the wrong way.

The Recursive Approach

function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(10)); // 55

Clean. Elegant. And dangerously slow.

Why It's Slow

fibonacci(5) calls fibonacci(4) and fibonacci(3). But fibonacci(4) also calls fibonacci(3). And both of those call fibonacci(2). You end up computing the same values over and over.

The call tree grows exponentially. fibonacci(40) makes over a billion function calls.

• Time: O(2^n) — exponential.
• Space: O(n) — recursion depth.

The Fix: Memoization

Cache results you've already computed.

function fibMemo(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  return memo[n];
}

console.log(fibMemo(50)); // 12586269025

• Time: O(n) — each value computed once.
• Space: O(n) — memo table + call stack.

The Fix: Iterative

Even simpler. No recursion overhead. No stack limits.

function fibIterative(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;
}

console.log(fibIterative(50)); // 12586269025

• Time: O(n).
• Space: O(1) — just two variables.

The Trade-off

The recursive version is beautiful for teaching. It maps directly to the mathematical definition. But it's unusable beyond n ≈ 40. Memoization fixes the performance while keeping the recursive structure. The iterative version is the most practical — fast, no stack overflow risk, minimal memory.

Pick the version that matches your needs. For interviews, know all three. For production, use the iterative one.