The Fibonacci series is usually one of the first examples used to teach recursive function calls — but it's also the classic example of how a naive recursive solution can quietly become disastrously slow. Once you understand why, you've understood one of the most useful optimization techniques in programming: memoization.

The Naive Recursive Version (Slow)

Each call to fib(n) makes two more calls, fib(n-1) and fib(n-2), and both of those branch again — the same sub-problems (like fib(5)) get recomputed over and over across different branches of the recursion tree.

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

console.log(fibNaive(10));
// Works fine for small n, but fibNaive(40) takes several seconds —
// because it makes over a billion redundant function calls.

Output:

55

This naive version runs in O(2^n) time — the number of calls roughly doubles with every increase in n, which is why it grinds to a halt once n gets into the 40s.

The Memoized Version (Fast)

Memoization means caching the result of each sub-problem the first time it's computed, so if the same input comes up again, you return the cached value instantly instead of recomputing the whole recursive branch.

function fibMemo(n, cache = new Map()) {
  if (n <= 1) return n;
  if (cache.has(n)) return cache.get(n); // already computed — reuse it

  const result = fibMemo(n - 1, cache) + fibMemo(n - 2, cache);
  cache.set(n, result);
  return result;
}

console.log(fibMemo(10));
console.log(fibMemo(50)); // instant, where the naive version would never finish

Output:

55
12586269025

With the cache in place, each value of n from 0 to the target is computed exactly once, bringing the time complexity down from O(2^n) to O(n) — at the cost of O(n) extra memory to store the cache. This same pattern — cache results keyed by input, check the cache before recomputing — generalizes to any recursive problem with overlapping sub-problems, which is the basis of dynamic programming. For even better performance on Fibonacci specifically, you could skip recursion entirely and compute it with a simple loop that tracks just the last two values, which uses O(1) extra space instead of O(n).