Course contentsShow
← JavaScript
Lesson 2379 of 2,72349. Common Patterns and IdiomsFree lesson

Memoization and Recursion

Applying memoization to recursive functions like Fibonacci for dramatic gains.

Memoization and Recursion

What you'll learn: How to supercharge recursive functions like Fibonacci by caching previously computed results with memoization.

Recursive functions often recalculate the same values repeatedly, causing exponential slowdowns. The classic example is the Fibonacci sequence: computing fib(40) recalculates fib(5) millions of times. Memoization fixes this by remembering results from previous calls.

Why Recursion Needs Memoization

Consider a naive Fibonacci function:

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

// fib(40) takes SECONDS — exponential time complexity

Each call spawns two more calls, creating a massive tree of duplicate work.

Applying Memoization to Fibonacci

Wrap your recursive function with a memoization layer:

function memoize(fn) {
  const cache = new Map();
  return function(n) {
    if (cache.has(n)) return cache.get(n);
    const result = fn(n);
    cache.set(n, result);
    return result;
  };
}

const fib = memoize(function(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
});

// fib(40) now runs in MILLISECONDS — linear time!

The Dramatic Gain

Without memoization: fib(40) makes ~330 million function calls.
With memoization: fib(40) makes only 40 calls.

Each value is computed once, then retrieved from the cache. The recursive structure remains elegant, but performance transforms from exponential to linear.

When to Use This Pattern

Memoizing recursive functions is ideal when:

  • The function is pure (same input always produces same output)
  • Subproblems overlap (same inputs recur frequently)
  • The cache size is manageable

Key Takeaway: Memoization transforms slow recursive algorithms with overlapping subproblems into fast, cache-backed solutions, turning exponential complexity into linear performance.