Recursion & Dynamic Programming: Solve It Once, Remember It

What you'll learn

• How recursion solves a problem with smaller copies of itself: the base case, the recursive case and the call stack underneath
• Why naive recursion can explode exponentially, and how to spot it in the call tree
• Memoization (top-down) and tabulation (bottom-up): two ways to solve every subproblem only once
• A five-step recipe for dynamic programming: state, transition, base case, order, answer
• The classics: Fibonacci, coin change, longest common subsequence and the 0/1 knapsack
• You will write: a minimum-coins solver, an LCS table and a knapsack packer

The staircase and the notebook

You climb a staircase of n steps, taking 1 or 2 steps at a time. In how many different ways can you reach the top?

Think about your last move. You arrived at step n either from step n - 1 (a single step) or from step n - 2 (a double step). So:

ways(n) = ways(n - 1) + ways(n - 2)        ways(1) = 1, ways(2) = 2

That is recursion: the answer for n is built from answers to smaller copies of the same question. It is also the Fibonacci sequence in disguise.

Now a friend asks for ways(40). If you follow the rule blindly, you compute ways(38) twice, ways(37) three times, ways(36) five times... and hundreds of millions of calls later you have the answer. If you keep a notebook and write down each answer the first time you find it, you need only 40 small additions.

Dynamic programming is recursion plus a notebook. The name was chosen by the mathematician Richard Bellman in the 1950s; "programming" meant planning a schedule, not writing code.

Recursion and the call stack

A recursive function calls itself on a smaller input. It always has two parts:

• Base case: an input small enough to answer directly, without another call.
• Recursive case: shrink the problem, call yourself, and combine the result.

Every call gets a frame on the call stack (its parameters and local variables). The frames pile up until a base case is reached, then they are removed in reverse order as each call returns:

fact(4)                       call stack at the deepest point:
= 4 * fact(3)                   fact(1)   <- base case, returns 1
      = 3 * fact(2)             fact(2)
            = 2 * fact(1)       fact(3)
                  = 1           fact(4)
then 2 * 1 = 2, 3 * 2 = 6, 4 * 6 = 24 as the frames pop

Trust the smaller call. When you write fact(n) = n * fact(n - 1), assume fact(n - 1) already works and only check two things: the combination is right, and every path eventually reaches a base case.

No reachable base case means infinite recursion. The stack grows until the language stops it: Python raises RecursionError (its default limit is about 1,000 nested calls, see sys.getrecursionlimit()), C and Rust programs crash with a stack overflow. Python also does not optimise tail calls, so a very deep recursion must be rewritten as a loop, with an explicit stack if needed (as with DFS in Trees & Graphs).

Halving instead of shrinking by one is where recursion shines. Computing x to the power n by multiplying n times is O(n); recursion gives O(log n):

def power(x, n):
    if n == 0:
        return 1                       # base case
    half = power(x, n // 2)            # solve a problem half the size, once
    return half * half if n % 2 == 0 else half * half * x

This is divide and conquer, the same idea as merge sort: split, solve the parts, combine.

When recursion explodes, and how to stop it

Here is the call tree of the naive fib(5) (with fib(0) = 0, fib(1) = 1, and fib(n) = fib(n - 1) + fib(n - 2)):

                 fib(5)
              /          \
         fib(4)            fib(3)
        /      \          /      \
    fib(3)    fib(2)   fib(2)    fib(1)
    /    \     ...      ...
 fib(2) fib(1)
   ...

fib(3) is computed twice and fib(2) three times. The number of calls for fib(n) is exactly 2 x fib(n + 1) - 1: 177 calls for fib(10), but 2,692,537 for fib(30). Each step up multiplies the work by about 1.618 (the golden ratio): exponential time.

The waste comes from overlapping subproblems: the same smaller question is asked again and again. Dynamic programming applies when a problem has overlapping subproblems and optimal substructure (the best answer is built from the best answers to subproblems). Merge sort has no overlap (each half is different), so a notebook would not help it.

Memoization (top-down). Keep the recursive code and add a cache keyed by the arguments: look up before computing, store after computing. In Python, @functools.cache (or @functools.lru_cache(maxsize=None)) does it for you; the arguments must be hashable.

Tabulation (bottom-up). Fill an array from the base cases upwards, in an order where everything an entry needs is already filled. No recursion, so no depth limit, and you can often keep only the last row or the last two values.

Either way, time = number of states x work per state. For Fibonacci that is n states x O(1) = O(n) instead of O(1.618ⁿ).

The recipe for any DP problem:

1. State: say in one sentence what dp[i] (or dp[i][j]) means.
2. Transition: how a state is computed from smaller states.
3. Base cases: the smallest states, known directly.
4. Order: compute every state after the states it depends on.
5. Answer: which state holds the final result.

Coin change

You must pay an amount A using as few coins as possible, with unlimited coins of each given value.

Greedy is not always right. "Take the largest coin that fits" works for coins like 1, 5, 10, 25, but not for 1, 3, 4: for A = 6 greedy pays 4 + 1 + 1 (three coins) while 3 + 3 needs only two. A greedy choice can be wrong because it never reconsiders; DP considers every last coin.

The recipe:

1. State: dp[a] = the fewest coins that make exactly a (infinity if impossible).
2. Transition: the last coin is some c <= a, so dp[a] = 1 + min(dp[a - c]) over all coins.
3. Base case: dp[0] = 0.
4. Order: a = 1, 2, ..., A (every a - c is smaller).
5. Answer: dp[A], or -1 if it is still infinity.

coins {1, 3, 4}

a       0  1  2  3  4  5  6
dp[a]   0  1  2  1  1  2  2       dp[6] = 1 + min(dp[5], dp[3], dp[2]) = 1 + 1

Time O(A x k) for k coin values, memory O(A).

A close cousin: counting the ways. How many combinations of coins make A? Put the coin loop outside, so each combination is counted once, in coin order:

ways = [1] + [0] * A            # one way to make 0: no coins
for c in coins:
    for a in range(c, A + 1):
        ways[a] += ways[a - c]

Swap the two loops and you count ordered sequences instead (1 + 2 and 2 + 1 become different). Loop order is part of the state's meaning.

Longest common subsequence

A subsequence keeps the order of characters but may skip some: ACE is a subsequence of ABCDE; AEC is not. (A substring would have to be contiguous.) The longest common subsequence (LCS) of two strings is the longest string that is a subsequence of both. For ABCBDAB and BDCABA it has length 4, for example BCBA.

LCS is the heart of comparing sequences. A line-based diff shows the lines to delete and insert, and the lines it keeps are a longest common subsequence of the two files' lines (Git's default diff algorithm is Myers' algorithm, published in 1986). The same idea aligns DNA sequences.

The recipe:

1. State: dp[i][j] = LCS length of the first i characters of X and the first j characters of Y.
2. Transition: if X[i-1] == Y[j-1], that character can end the common subsequence: dp[i][j] = dp[i-1][j-1] + 1. Otherwise one of the two last characters is not used: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
3. Base cases: dp[0][j] = dp[i][0] = 0 (an empty string has nothing in common).
4. Order: row by row, left to right.
5. Answer: dp[n][m].

X = ACE, Y = ABCDE

         ""  A  B  C  D  E
    ""    0  0  0  0  0  0
    A     0  1  1  1  1  1      A = A: diagonal + 1
    C     0  1  1  2  2  2      C = C: dp[A][B] + 1 = 2
    E     0  1  1  2  2  3      E = E: dp[C][D] + 1 = 3  -> LCS length 3

Time and memory O(n x m). If you only need the length, each row depends only on the previous one, so two rows (O(m) memory) are enough. To print the subsequence itself, keep the full table and walk back from dp[n][m]: move diagonally on a match, otherwise towards the larger neighbour.

The 0/1 knapsack

A hiker can carry at most W kilograms. There are n items, each with a weight and a value, and each item can be taken at most once (that is the "0/1"). Which items give the largest total value?

Greedy by value per kilogram fails. Items (weight 1, value 6), (2, 10) and (3, 12) with W = 5: the best ratios are 6 and 5, so greedy takes the first two for 16 and has no room for the third. Taking (2, 10) and (3, 12) gives 22.

The recipe:

1. State: dp[i][c] = best value using only the first i items with capacity c.
2. Transition: skip item i, or take it if it fits: dp[i][c] = max(dp[i-1][c], dp[i-1][c - w] + v).
3. Base cases: dp[0][c] = 0 (no items, no value).
4. Order: item by item.
5. Answer: dp[n][W].

items (w, v): (1, 6)  (2, 10)  (3, 12)        W = 5

capacity c        0   1   2   3   4   5
no items          0   0   0   0   0   0
+ (1, 6)          0   6   6   6   6   6
+ (2, 10)         0   6  10  16  16  16
+ (3, 12)         0   6  10  16  18  22      dp[5] = max(16, dp_prev[2] + 12) = 22

One row is enough if you update capacities from high to low:

dp = [0] * (W + 1)
for w, v in items:
    for c in range(W, w - 1, -1):        # downwards: dp[c - w] still means "without this item"
        dp[c] = max(dp[c], dp[c - w] + v)

Going upwards would let dp[c - w] already include the same item, so it could be taken again and again: that is the unbounded knapsack, the same loop shape as coin change. The direction of one loop decides which problem you solve.

O(n x W) is called pseudo-polynomial: it grows with the numeric value of W, not with the number of digits needed to write it. The knapsack problem is NP-hard in general, so no algorithm is known that is polynomial in n and the size of the numbers; DP works well when W is moderate.

Summary

• Recursion = a base case + a recursive case on a smaller input. Each call is a frame on the call stack; without a reachable base case the stack overflows. Halving the problem (fast power, merge sort) gives logarithmic depth.
• Naive recursion explodes when it re-solves overlapping subproblems (fib(30) makes 2,692,537 calls). Memoization caches answers top-down; tabulation fills a table bottom-up. Time = number of states x work per state.
• The DP recipe: state, transition, base cases, order, answer. Say what dp[...] means in one sentence before writing any loop.
• Coin change: dp[a] = 1 + min(dp[a - c]); greedy can be wrong. Coin loop outside counts combinations.
• LCS: dp[i][j] grows along the diagonal on a match, otherwise takes the larger neighbour; O(n x m), two rows for the length alone.
• 0/1 knapsack: dp[c] = max(dp[c], dp[c - w] + v) with capacities downwards; upwards is the unbounded version.

Practice next: compute the edit distance between two words (insert, delete, replace), find the longest increasing subsequence, and count the paths through a grid with obstacles. Then continue with Heaps & Priority Queues.