Dynamic programming — from recursion to tabulation

Naive recursive Fibonacci is exponential — fib(5) calls fib(3) twice, fib(2) three times, recomputing the exact same values over and over. The recursion lesson already covered why this shape happens; dynamic programming is specifically the technique for when that repeated work is the same subproblem being solved again and again. If subproblems don't overlap (each is genuinely distinct), memoizing them buys nothing — DP only pays off when the same subproblem recurs.

This is memoization, already covered in the recursion lesson — store each subproblem's result the first time it's computed, return the cached value on every subsequent call for that same input. It turns fib's exponential blowup into O(n): each of the n distinct subproblems gets computed exactly once. This is dynamic programming — "top-down DP" is just another name for memoized recursion.

Instead of starting at fib(n) and recursing down to the base cases, tabulation starts at the base cases and builds up to fib(n) directly, in a loop — no recursion, no call stack, no risk of hitting Python's recursion limit on large n. It computes the exact same set of subproblems as the memoized version, in the reverse order: bottom-up doesn't discover which subproblems it needs by recursing into them, so it has to compute every subproblem from the base case forward, in an order where each one's dependencies are already filled in before it's needed.

The recursion lesson noted Python doesn't optimize tail calls, so deep recursion risks RecursionError — tabulation sidesteps that entirely, since it's an ordinary loop. It's also frequently more memory-efficient: fib's bottom-up version only actually needs the previous two values, not the whole table, letting it drop to O(1) space:

This space optimization — collapsing a full table down to just the entries a later step actually depends on — only works cleanly once you can see the recurrence explicitly, which is easier to reason about in the bottom-up form than by staring at recursive calls.

Skipping straight to a bottom-up table without first getting the recurrence right from the naive recursive version is where most DP mistakes actually come from — the loop version is harder to reason about directly than the recursive one, precisely because the recursive version's structure IS the recurrence relation, made visible.