Fibonacci: Memo vs Tabulation

How it works, step by step

1. 1

   Notice the recursive rule: fib(n) = fib(n−1) + fib(n−2), with fib(0) = 0 and fib(1) = 1.

2. 2

   Notice the problem with it: fib(n−1) and fib(n−2) both need fib(n−3) - the same subproblems appear again and again (overlapping subproblems).

3. 3

   Fix #1 - memoization (top-down): keep the recursion, but store every result in a map the first time. Every later call is a lookup.

4. 4

   Fix #2 - tabulation (bottom-up): drop the recursion. Fill an array from fib(0) upward; each entry is one addition of two earlier entries.

5. 5

   Both do O(n) work instead of O(2ⁿ). Tabulation also shows the last trick: you only ever read the last two entries, so two variables replace the whole table - O(1) space.

6. 6

   This exact recipe - find the rule, spot the overlap, remember or tabulate, then shrink the storage - is how every DP problem in this collection is solved.

The code, in JavaScript

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

fib(10);   // 177 calls      - fine
fib(30);   // 2.7 million    - noticeable pause
fib(45);   // 3.6 billion    - go make coffee

// Why: fib(5) calls fib(4) and fib(3).
// fib(4) calls fib(3) AGAIN. Everything below repeats.

Dry run: building fib(0..12) bottom-up

The same steps the visualizer plays, written as a table. Generated by running the real algorithm - not written by hand.

• Memoization and tabulation compute the same thing in opposite directions: memo starts at the goal and recurses down; tabulation starts at the base and builds up. Interviews love asking for the conversion - practice it on this problem, where both fit on one slide.
• Recursion depth is real: memoized fib(20000) overflows JavaScript's call stack even though the math is fine. Tabulation has no such limit - one reason to learn the bottom-up form.
• fib(79) already exceeds Number.MAX_SAFE_INTEGER - the answers silently lose precision long before the algorithm slows down. Use BigInt when n is large.
• The space optimization (two variables) works because fib(i) reads only i−1 and i−2. In 2-D problems the same trick keeps one row instead of the matrix - but only when the reading pattern allows it. Check what each cell reads before shrinking.

Fibonacci: Memo vs Tabulation vs. its closest relatives