The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

Recursion and Dynamic Programming

Next ►
►

In the previous lesson we analyzed recurrences; in this one we will learn to design the algorithms that generate them. Recursion — solving a problem in terms of smaller versions of itself — is one of the most powerful design techniques there is. But it has a well-known pathology: when subproblems repeat, naive recursion repeats work until it becomes exponential. The cure is dynamic programming (DP): remembering what has already been computed, either on the fly (memoization) or by building the solution from the bottom up.

At Rutalia this topic is daily bread: the city is modeled as a grid of blocks, and many operational questions ("what is the minimum cost of crossing the downtown area?", "in how many ways can I reach the drop-off point?") have a natural recursive structure with massively overlapping subproblems.

Contents

  1. Recursion done right: base case, progress, and the call stack
  2. Divide and conquer as a general scheme
  3. The problem: overlapping subproblems
  4. Memoization (top-down)
  5. Bottom-up dynamic programming
  6. Reconstructing the solution

  1. Recursion done right: base case, progress, and the call stack

A correct recursive function needs exactly three ingredients:

  1. Base case(s): inputs so small they are solved directly, without recursion.
  2. Guaranteed progress: every recursive call is made on an input strictly closer to a base case.
  3. Correct combination: the solution to the problem is built correctly from the solutions to the subproblems (here the "recursive leap of faith" helps: assume the recursive call works and check that the combination is correct).

A minimal example with Rutalia: summing the total weight of a van's load.

def total_weight(weights):
    """Recursive sum of a list of weights (kg)."""
    if not weights:                            # base case: empty list
        return 0.0
    return weights[0] + total_weight(weights[1:])  # progress: the list shrinks by 1


print(total_weight([2.5, 1.0, 4.2]))  # 7.7

(Yes, in production this would be sum(weights) or a loop; the value of the example is seeing the three ingredients laid bare. Note also that weights[1:] copies the list: this teaching version costs Θ(n²) in time; passing indices instead of sublists brings it down to Θ(n).)

The call stack

Every pending call occupies a frame on the call stack: parameters, local variables, and the return point. This has two practical consequences:

  • Space cost: a recursion of depth d uses Θ(d) stack memory in addition to whatever it allocates explicitly. total_weight over n elements has depth n → Θ(n) space, versus the Θ(1) of the equivalent loop.
  • Python's limit: CPython cuts recursion off at ~1000 levels (RecursionError) to protect the stack. It can be raised with sys.setrecursionlimit, but that is a band-aid: if the depth grows with n, Rutalia's million orders will require an iterative version. Python also does not optimize tail recursion (unlike some other languages), so do not count on it.
flowchart TD
    A["total_weight([2.5, 1.0, 4.2])"] --> B["total_weight([1.0, 4.2])"]
    B --> C["total_weight([4.2])"]
    C --> D["total_weight([]) → 0.0"]
    D -.->|"returns 0.0"| C
    C -.->|"returns 4.2"| B
    B -.->|"returns 5.2"| A
    A -.->|"returns 7.7"| END["result: 7.7"]

  1. Divide and conquer as a general scheme

Divide and conquer (D&C) is the recursive pattern par excellence, in three steps:

  1. Divide the problem into independent subproblems (ideally of size n/b).
  2. Conquer: solve each subproblem recursively (base case when it is trivial).
  3. Combine the partial solutions into the overall solution.

Example at Rutalia: finding the heaviest and the lightest order in the van in a single pass, splitting the list in half:

def min_max_weight(weights, i, j):
    """Return (minimum, maximum) of weights[i..j], by divide and conquer."""
    if i == j:                       # base case: one element
        return weights[i], weights[i]
    m = (i + j) // 2                 # divide
    min1, max1 = min_max_weight(weights, i, m)      # conquer (left half)
    min2, max2 = min_max_weight(weights, m + 1, j)  # conquer (right half)
    return min(min1, min2), max(max1, max2)         # combine


weights = [2.5, 7.1, 0.8, 4.2, 3.3]
print(min_max_weight(weights, 0, len(weights) - 1))   # (0.8, 7.1)

Its recurrence is T(n) = 2T(n/2) + c, which by the master theorem from lesson 01-02 (case 1) gives Θ(n). The recursion depth is Θ(log n), so the stack is not a problem.

D&C works wonderfully when the subproblems are independent (they share no work). The great sorting and searching algorithms we will study in module 4 (mergesort, quicksort, binary search) are pure D&C. The trouble starts when the subproblems are not independent.

  1. The problem: overlapping subproblems

The canonical example is the Fibonacci sequence: F(0)=0, F(1)=1, F(n)=F(n−1)+F(n−2). The direct translation into code:

def fib(n):
    if n < 2:                       # base cases
        return n
    return fib(n - 1) + fib(n - 2)  # two recursive calls

It is correct… and disastrous. fib(50) takes minutes. Why? Let's draw the call tree:

flowchart TD
    A["fib(5)"] --> B["fib(4)"]
    A --> C["fib(3)"]
    B --> D["fib(3)"]
    B --> E["fib(2)"]
    C --> F["fib(2)"]
    C --> G["fib(1)"]
    D --> H["fib(2)"]
    D --> I["fib(1)"]

fib(3) is computed 2 times, fib(2) three times… and the number of repetitions grows exponentially: T(n) = T(n−1) + T(n−2) + c, which grows like Fibonacci itself → Θ(φⁿ) with φ ≈ 1.618. There are only n+1 distinct subproblems, but the tree has on the order of 2ⁿ nodes: we are solving the same subproblems over and over again. This is overlapping subproblems.

When a problem has (a) overlapping subproblems and (b) optimal substructure (the optimal solution is composed of optimal solutions to the subproblems), it is a candidate for dynamic programming. There are two strategies.

  1. Memoization (top-down)

Memoization: keep the recursion as is, but store each result the first time it is computed and reuse it afterwards. It is the lowest-effort path starting from an already-written recursion.

def fib_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n < 2:
        return n
    if n not in memo:                  # have we computed it already?
        memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

Each of the n+1 subproblems is computed exactly once, with constant work outside the calls: Θ(n) time, Θ(n) space (memo + stack). From exponential to linear just by keeping a dictionary.

Python ships memoization out of the box:

from functools import lru_cache

@lru_cache(maxsize=None)     # or @cache in Python 3.9+
def fib_cached(n):
    if n < 2:
        return n
    return fib_cached(n - 1) + fib_cached(n - 2)

Now the Rutalia problem. The downtown area is a grid of blocks; the courier enters at the northwest corner (0, 0) and must reach the drop-off point at the southeast corner (R−1, C−1), moving only south or east (one-way streets). Each cell has a cost to cross it (minutes depending on traffic, fictional data). We want the minimum cost of the trip.

Recursive definition: let mc(r, c) be the minimum cost of reaching cell (r, c). Cell (r, c) can only be reached from above or from the left, so:

  • mc(0, 0) = cost[0][0] (base case)
  • mc(r, c) = cost[r][c] + min(mc(r−1, c), mc(r, c−1)), handling the edges (first row/column) with a single predecessor.

This equation — the problem's recurrence relation — exhibits the optimal substructure: the best path to (r, c) ends in the best path to one of its two predecessors. And the subproblems overlap: reaching mc(2, 2) means asking for mc(1, 2) and mc(2, 1), and both of them ask for mc(1, 1).

from functools import lru_cache

# Minutes per block (fictional data): 4 rows x 5 columns
COST = [
    [3, 2, 4, 1, 5],
    [1, 9, 3, 2, 2],
    [4, 1, 2, 8, 1],
    [2, 3, 1, 2, 3],
]

def min_cost_td(cost):
    """Minimum cost from (0,0) to the bottom-right corner. Top-down."""
    R, C = len(cost), len(cost[0])

    @lru_cache(maxsize=None)
    def mc(r, c):
        if r == 0 and c == 0:                 # base case: the origin
            return cost[0][0]
        if r < 0 or c < 0:                    # outside the grid
            return float("inf")               # infinite cost: never chosen
        return cost[r][c] + min(mc(r - 1, c), mc(r, c - 1))

    return mc(R - 1, C - 1)


print(min_cost_td(COST))   # 17

Details worth noticing:

  • The trick of returning float("inf") outside the grid simplifies the edges: min discards those branches on its own.
  • There are R·C distinct subproblems and each is solved once with O(1) work → Θ(R·C) time, Θ(R·C) space. Without memoization, the call tree would be exponential (each cell branches into two).
  • The recursion depth is Θ(R+C); for very large grids it can brush against Python's limit. One more reason for the next strategy.

  1. Bottom-up dynamic programming

The bottom-up version eliminates the recursion: identify the order in which the subproblems are needed (from small to large) and fill in a table iteratively.

def min_cost_bu(cost):
    """Minimum cost from (0,0) to the bottom-right corner. Bottom-up."""
    R, C = len(cost), len(cost[0])
    table = [[0] * C for _ in range(R)]    # table[r][c] = mc(r, c)

    table[0][0] = cost[0][0]
    for c in range(1, C):                  # first row: only reachable from the left
        table[0][c] = table[0][c - 1] + cost[0][c]
    for r in range(1, R):                  # first column: only from above
        table[r][0] = table[r - 1][0] + cost[r][0]

    for r in range(1, R):                  # the rest: minimum of the two predecessors
        for c in range(1, C):
            table[r][c] = cost[r][c] + min(table[r - 1][c], table[r][c - 1])

    return table[R - 1][C - 1]


print(min_cost_bu(COST))   # 17

Same result, same Θ(R·C) complexity, but no call stack and no per-cell function overhead. Moreover, since each row only consults the previous one, the space can be reduced to Θ(C) by keeping a single row (a common optimization when the path does not need to be reconstructed).

Comparison of the three approaches:

Approach Time Space Advantages Drawbacks
Naive recursion exponential Θ(R+C) stack immediate from the recurrence unworkable except for tiny n
Memoization (top-down) Θ(R·C) Θ(R·C) + stack written in 2 minutes from the recurrence; only computes the subproblems it needs stack limit; per-call overhead
Bottom-up DP Θ(R·C) Θ(R·C), reducible to Θ(C) no stack; faster constants; space can be optimized requires thinking out the fill order; computes all subproblems

A general recipe for setting up a DP, applicable to almost any problem:

  1. Define the subproblem precisely ("mc(r, c) = minimum cost of reaching (r, c)").
  2. Write the recurrence relating it to smaller subproblems, along with its base cases.
  3. Count: number of subproblems × work per subproblem = complexity.
  4. Choose top-down (fast to write) or bottom-up (fast to run) and, if appropriate, optimize the space.

A counting variant with the same structure: in how many different ways can the courier reach the destination? Same grid, recurrence ways(r, c) = ways(r−1, c) + ways(r, c−1) with ways(0, 0) = 1 (and 0 outside the grid). Only the base case changes, and paths are added instead of taking the minimum. We leave it as an exercise.

  1. Reconstructing the solution

Knowing that the optimal trip costs 17 minutes is nice; Rutalia's courier also needs the path. There are two techniques:

  • Store decisions: alongside each table value, record where it came from (the argmin).
  • Backtrack by comparing (the one we will use): start from the final cell and, at each step, move to the predecessor whose table value fits the equation. It requires no extra memory.
def min_cost_path(cost):
    """Return (minimum cost, list of cells along the optimal path)."""
    R, C = len(cost), len(cost[0])
    # 1) Fill the table exactly as in min_cost_bu
    table = [[0] * C for _ in range(R)]
    table[0][0] = cost[0][0]
    for c in range(1, C):
        table[0][c] = table[0][c - 1] + cost[0][c]
    for r in range(1, R):
        table[r][0] = table[r - 1][0] + cost[r][0]
    for r in range(1, R):
        for c in range(1, C):
            table[r][c] = cost[r][c] + min(table[r - 1][c], table[r][c - 1])

    # 2) Backtrack from the destination to the origin
    r, c = R - 1, C - 1
    path = [(r, c)]
    while (r, c) != (0, 0):
        if r == 0:                                   # could only have come from the left
            c -= 1
        elif c == 0:                                 # could only have come from above
            r -= 1
        elif table[r - 1][c] <= table[r][c - 1]:     # came from the cheaper predecessor
            r -= 1
        else:
            c -= 1
        path.append((r, c))
    path.reverse()                                   # from origin to destination
    return table[R - 1][C - 1], path


cost, route = min_cost_path(COST)
print(cost)    # 17
print(route)   # [(0, 0), (0, 1), (1, 1)... down to (3, 4)] — one optimal route

The reconstruction visits at most R+C−1 cells → Θ(R+C), negligible compared to filling the table. If there are ties, any of the tied options yields an optimal path (there may be several).

With this we have the complete DP cycle: recurrence → table → optimal value → reconstructed solution. This same pattern (with other recurrences) will solve combinatorial optimization problems in module 2 — that is where we will meet the knapsack problem — and will reappear in shortest paths over general graphs in module 3, where the city stops being a perfect grid.

Common Mistakes and Tips

  • Missing or unreachable base case. If some branch of the recursion never lands on a base case (for example, fib(n-2) with n=1 without handling n<2), you get a RecursionError or nonsense results. Enumerate the base cases before writing the recursive call.
  • Recursion without progress. Calling yourself with the same problem size (or larger) never terminates. Check that every path shrinks the input.
  • Mutable default parameters. def f(n, memo={}) shares the dictionary across all calls in the entire program: a Python classic that happens to produce correct results here but causes state contamination in general. Use memo=None + internal initialization, or lru_cache.
  • Memoizing functions with unhashable arguments. lru_cache requires hashable arguments: you cannot pass lists or dicts. Solution: pass indices/tuples and keep the large data in an outer variable (as we did with COST).
  • Applying DP without optimal substructure. If the globally optimal solution is not composed of optima of the subproblems (e.g., routes with constraints that couple distant decisions), the recurrence produces incorrect results no matter how well it is implemented. Verify the property before coding.
  • Forgetting the stack in the space analysis. A top-down memoization over a chain of n subproblems uses Θ(n) of stack; in Python, with n > ~1000, that is a RecursionError. If the depth scales with the input, switch to bottom-up.
  • Tip: always write the recurrence on paper first, with its base cases, and validate it by hand on a 3×3 example. 90% of DP mistakes are badly formulated recurrences, not code bugs.

Exercises

Exercise 1: Counting the courier's routes

Using the same R×C grid (moves only south/east), implement count_routes(R, C) returning in how many different ways the courier can go from (0,0) to (R−1,C−1). Do it bottom-up and state its complexity. Check: for a 3×3 grid there are 6 routes.

Exercise 2: Rest stretches

A Rutalia courier climbs a staircase of n steps up to the warehouse and can take 1 or 2 steps at a time. Write (a) the naive recursion counting in how many ways they can climb, (b) its memoized version, and (c) reason about the complexity of each. Which well-known sequence does it correspond to?

Exercise 3: Reconstruction with stored decisions

Modify min_cost_path so that, instead of backtracking by comparing values, it stores during the fill a table came_from[r][c] with "up" or "left", and reconstructs the path from it. What space cost does it add? What advantage does this variant have?

Solutions

Solution 1

def count_routes(R, C):
    table = [[0] * C for _ in range(R)]
    for c in range(C):
        table[0][c] = 1          # first row: a single way (all east)
    for r in range(R):
        table[r][0] = 1          # first column: a single way (all south)
    for r in range(1, R):
        for c in range(1, C):
            table[r][c] = table[r - 1][c] + table[r][c - 1]
    return table[R - 1][C - 1]

print(count_routes(3, 3))   # 6

Θ(R·C) time, Θ(R·C) space (reducible to Θ(C) with a single row). Same table as the minimum cost, swapping min for a sum and changing the base cases: the structure of the problem is identical.

Solution 2

(a) Naive recursion — to climb n steps, the last move was either 1 step (n−1 remained) or 2 steps (n−2 remained):

def ways(n):
    if n <= 1:
        return 1        # 0 steps: 1 way (stay put); 1 step: 1 way
    return ways(n - 1) + ways(n - 2)

(b) Memoized:

from functools import lru_cache

@lru_cache(maxsize=None)
def ways_memo(n):
    if n <= 1:
        return 1
    return ways_memo(n - 1) + ways_memo(n - 2)

(c) The naive one is exponential, Θ(φⁿ) — it is exactly the Fibonacci tree with shifted indices: ways(n) = F(n+1). The memoized one solves n+1 subproblems once each → Θ(n) time, Θ(n) space. Common mistake: making only n == 0 a base case and letting n == 1 call ways(-1).

Solution 3

    # while filling the interior:
    for r in range(1, R):
        for c in range(1, C):
            if table[r - 1][c] <= table[r][c - 1]:
                table[r][c] = cost[r][c] + table[r - 1][c]
                came_from[r][c] = "up"
            else:
                table[r][c] = cost[r][c] + table[r][c - 1]
                came_from[r][c] = "left"
    # reconstruction: follow came_from from (R-1, C-1) back to (0, 0)

(Cells in the first row carry "left" and those in the first column "up".) It adds Θ(R·C) space for came_from. Advantage: the reconstruction is direct and does not depend on re-evaluating the equation (useful when the backtracking comparison is expensive or the recurrence has many options); it is the standard technique when there are more than two possible decisions per subproblem.

Conclusion

We have traveled the full arc of recursive design: a correct recursion requires base cases, guaranteed progress, and a valid combination, and it consumes stack proportional to its depth. Divide and conquer exploits recursion when the subproblems are independent; when they overlap, naive recursion blows up exponentially (Fibonacci) and the fix is to remember: memoization if we start from the recursion (top-down), bottom-up dynamic programming if we prefer to fill the table with no stack and the option of optimizing space. With Rutalia's grid we have also seen that the optimal value is not enough: reconstruction hands us the concrete route the courier must follow.

In all of these solutions the structures that make them possible have appeared almost without being named: dictionaries that memoize in O(1), tables, lists. In the next lesson, Advanced Data Structures, we will study them rigorously — heaps, hash tables, union-find, and tries — because choosing the right structure is, just as often as choosing the algorithm, what separates seconds from hours at Rutalia.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2026. All rights reserved