Memoization, and a Taste of Dynamic Programming

Memoization already appeared once in this course's material, in the functional-patterns lesson, as a general caching technique for pure functions. This lesson is about a specific, dramatic case where memoization doesn't just make something faster — it changes the complexity class entirely, and about the small slice of dynamic programming vocabulary worth knowing because of it.

The naive version, and why it explodes

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

This looks like it should be roughly O(n) — after all, there are only n distinct Fibonacci values to compute. It is not. Trace the calls for fib(5):

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   │   ├── fib(1)
│   │   │   └── fib(0)
│   │   └── fib(1)
│   └── fib(2)          ← computed AGAIN, from scratch
│       ├── fib(1)
│       └── fib(0)
└── fib(3)               ← computed AGAIN, from scratch
    ├── fib(2)           ← and AGAIN
    │   ├── fib(1)
    │   └── fib(0)
    └── fib(1)

fib(2) gets recomputed independently three separate times in this tiny trace, and the redundancy compounds — every call branches into two more, so the total number of calls roughly doubles with every increase in n. That's O(2ⁿ), exponential — the worst complexity class this course names, and a real one: fib(40) this way takes a genuinely noticeable amount of time; fib(50) is impractical.

The fix: cache what's already been computed

function fibMemoized(n, cache = new Map()) {
  if (n <= 1) return n;
  if (cache.has(n)) return cache.get(n); // already computed — return it, no recursion
 
  const result = fibMemoized(n - 1, cache) + fibMemoized(n - 2, cache);
  cache.set(n, result); // store before returning, so future calls skip the work
  return result;
}

Same recursive structure, same base case — the only addition is: check the cache first, and populate it before returning. Now fib(2) is computed exactly once, ever, no matter how many places in the call tree ask for it; every subsequent request is an O(1) map lookup instead of a fresh recursive branch.

The complexity change is real, not cosmetic: there are only n + 1 distinct subproblems (fib(0) through fib(n)), and memoization guarantees each one does its actual work exactly once. Total work: O(n) — down from O(2ⁿ). This is the single clearest demonstration in this entire course of the opening lesson's point: the shape of an algorithm's growth, not just its constant factor, is what's on the line.

A taste of dynamic programming

What you just did has a name: dynamic programming (DP) is exactly the technique of identifying that a problem breaks down into overlapping subproblems — the same smaller question gets asked more than once — and making sure each one is solved exactly once.

Memoization (what's above) is called the top-down approach: start from the big question (fib(n)), recurse toward the base cases, caching along the way. The other standard DP approach is tabulation — bottom-up: build an array of answers starting from the base cases and working up, with an ordinary loop instead of recursion:

function fibTabulated(n) {
  if (n <= 1) return n;
  const table = [0, 1];
  for (let i = 2; i <= n; i++) {
    table[i] = table[i - 1] + table[i - 2];
  }
  return table[n];
}

Same O(n) time as the memoized version, but O(1) space is achievable here too (only the last two values are ever needed, not the whole table) — and no recursion at all, so no stack-depth risk from the previous lesson. For Fibonacci specifically, tabulation is strictly better; the value of seeing the memoized version first is that it maps directly onto the recursive structure of the problem, which is often easier to write correctly, even when tabulation would ultimately be the more efficient final form.

This course treats DP lightly and stops here deliberately — full dynamic programming (subset-sum, edit distance, knapsack-style problems) is squarely outside what a frontend interview typically probes. The genuinely useful takeaway is the pattern-recognition skill: whenever a recursive solution seems to be re-solving identical smaller problems repeatedly, memoization is the fix, and it can be the difference between exponential and linear.

What to remember

• Naive recursive Fibonacci is O(2ⁿ) because it recomputes the same subproblems repeatedly, not because there are exponentially many distinct values to compute — there are only n + 1.
• Memoization caches each distinct subproblem's result after computing it once, turning repeated recursive branches into O(1) cache hits — a real change in complexity class, not just a constant-factor speedup.
• Dynamic programming is exactly this idea applied deliberately: recognize overlapping subproblems, and guarantee each one is solved exactly once, either top-down (memoization) or bottom-up (tabulation).
• Whenever a recursive solution seems to revisit the same smaller question more than once, that's the specific signal to reach for memoization.