Recursion and Dynamic Programming: Two Conditions, One Filled Table

Recursion is a stack you did not declare

Every call pushes a frame holding arguments, locals and the return address. Depth \(d\) therefore costs \(\Theta(d)\) memory, and that memory is the call stack — a fixed-size region, not the heap.

A correct recursion needs base cases that are reachable (every call moves strictly towards one) and complete (they cover every way the recursion bottoms out). Miss either and Python raises RecursionError at its default limit of 1000 frames; raising that limit with sys.setrecursionlimit trades a clean exception for a possible hard crash of the C stack. CPython does no tail-call optimisation, so rewrite deep recursions iteratively.

Where the exponential comes from

def fib_naive(n):
    return n if n < 2 else fib_naive(n - 1) + fib_naive(n - 2)

The recurrence is \(T(n) = T(n-1) + T(n-2) + \Theta(1)\), so the call count grows like the Fibonacci numbers themselves: \(\Theta(\varphi^{\,n})\) with \(\varphi = (1+\sqrt5)/2 \approx 1.618\). The waste is structural — fib_naive(n-2) is computed twice, fib_naive(n-3) three times — even though there are only \(n\) distinct subproblems. That gap between distinct subproblems and evaluated subproblems is exactly what dynamic programming closes.

Memoisation and tabulation

Memoisation keeps the recursion and caches results:

from functools import cache

@cache                       # functools.cache, Python 3.9+; lru_cache(None) before that
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

print(fib(50))               # 12586269025, from 51 distinct subproblems

Each of the \(n+1\) distinct arguments is evaluated once, so the cost drops to \(\Theta(n)\) time and \(\Theta(n)\) space — but the recursion depth is still \(\Theta(n)\), so fib(5000) would blow the stack.

Tabulation fills the same table bottom-up in an order where every dependency is already computed:

def fib_table(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a                 # Theta(n) time, Theta(1) space

Same asymptotics, no stack, better constants, and — because the loop makes the dependency structure explicit — it is where space optimisation becomes visible: fib_table keeps two numbers instead of \(n\).

The two conditions

DP applies exactly when:

1. Optimal substructure. An optimal solution contains optimal solutions to subproblems. Shortest paths have it: a prefix of a shortest path is a shortest path. Longest simple paths do not, which is why there is no DP for them.
2. Overlapping subproblems. The recursion revisits the same subproblem many times. Merge sort has optimal substructure but its subproblems are disjoint, so caching buys nothing — that is divide and conquer, not DP.

Both are needed. Condition 1 makes the recurrence correct; condition 2 makes the table worth building.

Worked example: edit distance

The Levenshtein distance between strings \(s\) and \(t\) is the fewest single-character insertions, deletions and substitutions turning one into the other. Let \(D[i][j]\) be the distance between the first \(i\) characters of \(s\) and the first \(j\) of \(t\):

with \(D[i][0] = i\) and \(D[0][j] = j\) — turning a prefix into the empty string costs one deletion per character. Filled for \(s =\) kitten, \(t =\) sitting:

The answer is the bottom-right cell: 3. Read the bold diagonal backwards and you recover the operations — substitute k→s, keep itt, substitute e→i, keep n, insert g — which is kitten → sitten → sittin → sitting.

Each cell is \(O(1)\) work and there are \((m+1)(n+1)\) of them, so the algorithm is \(\Theta(mn)\) time. Each row depends only on the previous one, so space compresses from \(\Theta(mn)\) to \(\Theta(\min(m,n))\):

def edit_distance(s, t):
    """Levenshtein distance. Theta(m*n) time, Theta(min(m,n)) space."""
    if len(s) < len(t):
        s, t = t, s                        # keep the shorter string as the row
    prev = list(range(len(t) + 1))         # row 0: distance from "" to t[:j]
    for i, cs in enumerate(s, start=1):
        cur = [i] + [0] * len(t)
        for j, ct in enumerate(t, start=1):
            cur[j] = min(prev[j] + 1,              # delete cs
                         cur[j - 1] + 1,           # insert ct
                         prev[j - 1] + (cs != ct)) # match / substitute
        prev = cur
    return prev[-1]

print(edit_distance("kitten", "sitting"))   # 3
print(edit_distance("", "abc"))             # 3
print(edit_distance("abc", "abc"))          # 0

Note that recovering the path needs the full table (or a re-run), so the space compression costs you the reconstruction — a trade the interviewer will often ask about.

Spotting a DP problem

Four signals, and if three fire, build a table: the question asks for a count, minimum or maximum over exponentially many configurations; those configurations are built by a sequence of local decisions; the brute-force recursion revisits states; and the state is describable by a handful of indices.

Then work in a fixed order: state (what does \(D[\cdot]\) mean — say it in words), recurrence, base cases, evaluation order, where the answer sits. Writing the state in English first is what prevents a subtly wrong recurrence, and it is what an interviewer is listening for.

def collect(x, acc=[]):   # evaluated once, at definition time
    acc.append(x)
    return acc

collect(1)   # [1]
collect(2)   # [1, 2]  -- not [2]

References

1. Bellman, R. Dynamic Programming. Princeton University Press, 1957.
2. Wagner, R. A., & Fischer, M. J. The string-to-string correction problem. Journal of the ACM 21(1), 168–173, 1974.
3. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. Introduction to Algorithms, 4th ed. MIT Press, 2022 — ch. 14 on dynamic programming.
4. Python Software Foundation. functools.cache and lru_cache.
5. Python Software Foundation. sys.setrecursionlimit.
6. Python Software Foundation. Default argument values — the tutorial’s own warning about mutable defaults.