Recursion & Divide and Conquer

Thinking recursively: the leap of faith

Picture yourself in a dark cinema. You want to know which row you are sitting in, but it is too dark to count. So you tap the person in front of you and ask, "Which row are you in?" You do not know how they will find out; you just trust that they will answer. When they say "row 11," you add one: you are in row 12. The person in front of them did the same thing, and so on, until someone in the very front row says "row 1" without asking anyone.

That is the whole of recursion. A recursive function is a function that calls itself on a smaller version of its input. Two parts make it work:

• The base case: an input so small the answer is known directly (the front row says "1").
• The recursive case: an answer built from the answer to a smaller problem (my row is their row plus one).

The hardest mental step for beginners is the recursive leap of faith: when you write the recursive call, you assume it already works for the smaller input, and you only think about how to use its result. You do not trace all the way down in your head. This is not wishful thinking; it is mathematical induction. If the base case is correct, and if "smaller answer is correct" implies "my answer is correct," then every answer is correct.

def row_number(people_in_front: int) -> int:
    if people_in_front == 0:                      # base case: front row
        return 1
    return row_number(people_in_front - 1) + 1    # recursive case: trust, then add one

Here is the recipe you will use for every recursive function in this module:

1. Define the function in words. "total(xs) returns the sum of the list xs." Be exact about input and output.
2. Find the smallest input. The empty list sums to 0.
3. Shrink the problem. A non-empty list is its first item plus the rest.
4. Take the leap. Assume total(rest) is correct and combine: xs[0] + total(xs[1:]).

Remember: define the function precisely, handle the smallest case, and trust the recursive call on a strictly smaller input.

Base cases, recursive cases, and the classic bugs

Every recursive function must make progress: each call's input must be closer to a base case than the call that made it. "Closer" needs a measure that is a non-negative integer and strictly decreases, such as the length of a list, the value of n, or the height of a tree. If you can name that measure, the recursion terminates.

Some functions need more than one base case (Fibonacci needs fib(0) and fib(1)) or more than one recursive call (a binary tree's size is 1 + size(left) + size(right)). Functions with one recursive call are linear recursion; with two or more they are tree recursion, which can be explosively expensive, as you will soon see.

Remember: name the shrinking measure, test the smallest inputs first, and always return the recursive result.

The call stack, step by step

How does Python keep track of six unfinished copies of the same function? Every call creates a frame: a small record holding that call's local variables and the line it will resume at. Frames are kept on the call stack, a last-in-first-out stack (you met stacks in M22). Calling pushes a frame; returning pops it and hands the value to the frame below.

Step through fact(4) below. Watch the frames pile up while n counts down (the winding phase), then disappear while the multiplications happen (the unwinding phase). Each frame has its own n: they are different variables that happen to share a name.

The stack is also why a traceback from a deep recursion is long: each line of the traceback is one frame that was still waiting when the error happened. Python collapses repeated identical lines into [Previous line repeated 996 more times].

Remember: every active call is a frame on the stack with its own locals; memory use of a recursion is proportional to its maximum depth, not the total number of calls.

The recursion limit and why Python has no tail-call optimization

Frames cost memory, and an infinite recursion would eat it all. CPython therefore caps the depth of Python calls. sys.getrecursionlimit() reports the cap (1000 by default) and exceeding it raises RecursionError, a subclass of RuntimeError.

You can raise the cap with sys.setrecursionlimit(10_000), but treat it as a code smell. The limit exists to protect the interpreter's own C stack; raise it too far and the process can crash outright instead of raising a polite exception. If your recursion depth grows with the size of the input (a linked list of a million nodes), the right fix is an iterative algorithm, which you will write later in this module.

Tail calls

A tail call is a call whose result is returned directly, with no work left to do afterward: return helper(n - 1, acc * n). Some languages (Scheme, Haskell, and many C compilers) perform tail-call optimization (TCO): they reuse the current frame for the tail call, so a tail-recursive loop runs in constant stack space. Python deliberately does not. Guido van Rossum's reasons are still the official position:

• TCO deletes frames, which destroys tracebacks. Debugging a crash 5,000 calls deep with only one frame visible is miserable.
• Python names can be rebound at runtime, so the compiler cannot know a call is really "to itself."
• Python already has a clear, idiomatic way to write loops: the loop.

Remember: the default limit is about 1000 frames; recursion is great when depth is logarithmic or bounded by the data's nesting, and the wrong tool when depth grows linearly with input size.

Recursion trees: seeing the work

When a function makes more than one recursive call, the calls form a recursion tree: each node is one call, its children are the calls it makes, and leaves are base cases. The tree's depth is the stack space you need. Its number of nodes (times the work per node) is the running time. Drawing the tree is the single most useful habit for analyzing a recursive algorithm.

Fibonacci: the cautionary tale

The Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, ...: each is the sum of the two before. The definition translates directly into code:

def fib(n: int) -> int:
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Correct, and catastrophically slow. Open the tree below and count how many times fib(2) appears. Every subtree is recomputed from scratch. The number of calls grows like φⁿ (φ ≈ 1.618), so fib(40) makes over 300 million calls.

Towers of Hanoi

Move a stack of n disks from peg A to peg C, one disk at a time, never putting a larger disk on a smaller one. It looks impossible until you take the leap of faith: assume you can move n − 1 disks. Then move the top n − 1 disks to B (trusting recursion), move the biggest disk to C, and move the n − 1 disks from B onto C (trusting recursion again).

hanoi(n, source, target, spare):
    if n == 0: do nothing
    hanoi(n - 1, source, spare, target)
    move disk n from source to target
    hanoi(n - 1, spare, target, source)

Correctness (induction): moving n − 1 disks never touches disk n, and disk n is the largest, so it never sits on a smaller disk. Complexity: M(n) = 2M(n − 1) + 1 with M(0) = 0, which solves to 2ⁿ − 1 moves. The tree has 2ⁿ − 1 nodes but only depth n, so the stack use is O(n).

Permutations and the power set

Generating all arrangements (permutations) or all subsets (the power set) is the same pattern: make one choice, recurse on what is left, then undo or move on. The recursion tree is the decision tree of choices.

Permutations of n items: n! leaves, so Θ(n · n!) time to build them. Power set: 2ⁿ subsets, Θ(n · 2ⁿ). No cleverness can beat the size of the output. In real code use itertools.permutations and itertools.combinations, which generate lazily in C.

Remember: depth = stack space, node count × work per node = time. Branching factor b and depth d give up to bᵈ nodes.

Memoization with functools.cache

Fibonacci's tree is huge because it contains the same subproblems over and over. Memoization ("writing a memo to yourself") stores each answer the first time it is computed, keyed by the arguments, and returns the stored answer on every later call. Repeated subtrees collapse into a single lookup. Compare the tree below with the one you saw earlier: it is now a single spine with n + 1 distinct calls.

def fib(n: int, memo: dict[int, int] | None = None) -> int:
    if memo is None:
        memo = {}
    if n < 2:
        return n
    if n not in memo:
        memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

from functools import cache

@cache
def fib(n: int) -> int:
    return n if n < 2 else fib(n - 1) + fib(n - 2)

functools.cache (Python 3.9+) is an unbounded dictionary-backed cache. functools.lru_cache(maxsize=128) keeps only the most recently used entries, which is what you want for long-running services where unbounded memory is dangerous. Both require hashable arguments (no lists or dicts) and are only correct for pure functions: same inputs, same output, no side effects.

Remember: if a recursion tree repeats subproblems, cache them. Exponential time often becomes polynomial: fib goes from Θ(φⁿ) to Θ(n).

Converting recursion to iteration with an explicit stack

Recursion uses the call stack implicitly. Any recursive function can be rewritten to manage its own stack, a plain Python list, which has no 1000-entry limit. The conversion is mechanical:

1. Create a list holding the initial "call" (its arguments).
2. Loop while the list is non-empty: pop a work item, handle base cases, and push the smaller subproblems that the recursive version would have called.
3. Accumulate results in a variable instead of returning them up the chain.

def tree_sum(node: dict | None) -> int:
    if node is None:
        return 0
    return node["value"] + tree_sum(node["left"]) + tree_sum(node["right"])

def tree_sum(node: dict | None) -> int:
    total = 0
    stack = [node]
    while stack:
        current = stack.pop()
        if current is None:
            continue
        total += current["value"]
        stack.append(current["left"])
        stack.append(current["right"])
    return total

Things get trickier when work happens after the recursive call returns (post-order work, like n * fact(n - 1)). The standard technique pushes a marker meaning "come back to me later," for example (node, "exit") after (child, "enter"). You saw this in depth-first traversal in M26.

Remember: recursion is a stack; when depth may be large, own the stack yourself.

Divide and conquer

Divide and conquer is recursion with a strategy: divide the input into smaller pieces of the same kind (usually halves), conquer each piece recursively, and combine the partial answers. The power comes from halving: a problem of size n is only log₂ n halvings away from size 1.

Merge sort (a preview)

Intuition: sorting a deck of cards with a friend. Split the deck in half, each of you sorts a half (by doing the same thing recursively), then you merge two sorted piles by repeatedly taking the smaller top card. Merging two sorted piles is easy and linear. You will study it fully in M29 Sorting.

merge_sort(xs):
    if len(xs) <= 1: return xs
    left  = merge_sort(first half of xs)
    right = merge_sort(second half of xs)
    return merge(left, right)        # walk both, always take the smaller head

Each level of the tree does O(n) merging in total, and there are log₂ n levels, so the time is O(n log n).

Fast exponentiation

Computing xⁿ with n − 1 multiplications is slow for big n. Notice that x¹⁰⁰ = (x⁵⁰)², and x⁵⁰ = (x²⁵)², and x²⁵ = x · (x¹²)². Each step halves the exponent, so only about 2 log₂ n multiplications are needed.

power(x, n):
    if n == 0: return 1
    half = power(x, n // 2)
    if n is even: return half * half
    else:         return half * half * x

Invariant: power(x, n) returns xⁿ because x^(2k) = (x^k)² and x^(2k+1) = (x^k)²·x, and the exponent strictly decreases to 0. Complexity: O(log n) multiplications and O(log n) stack depth. Python's built-in pow(x, n, m) uses this idea (iteratively, over the bits of n) for modular exponentiation, the workhorse of cryptography.

Closest pair of points (overview)

Given n points in the plane, find the two closest. Checking every pair is O(n²). Divide and conquer sorts the points by x, splits them with a vertical line, solves each half recursively to get a best distance d, and then only needs to check points within d of the dividing line. A geometric argument shows each such point needs comparing to at most a handful of neighbors (sorted by y), so the combine step is O(n) and the whole algorithm runs in O(n log n).

Karatsuba multiplication (the idea)

School multiplication of two n-digit numbers is O(n²). In 1960 Anatoly Karatsuba noticed that splitting each number in half, x = a·10ᵐ + b and y = c·10ᵐ + d, needs only three half-size products, not four: ac, bd, and (a + b)(c + d), because ad + bc = (a + b)(c + d) − ac − bd. Three recursive calls on half-size inputs give O(n^log₂3) ≈ O(n^1.585). CPython's own big-integer multiplication switches to Karatsuba for large numbers.

When to use divide and conquer: the problem splits into independent subproblems of the same shape, and the combine step is cheaper than solving the whole thing directly. If the subproblems overlap, you want memoization or dynamic programming instead.

The master theorem, made friendly

Divide-and-conquer running times satisfy a recurrence:

T(n) = a · T(n / b) + f(n)

• a: how many recursive calls each call makes (the branching factor).
• b: how much smaller each subproblem is (b = 2 for halving).
• f(n): the work done outside the recursive calls (dividing and combining).

Picture the recursion tree. Level k has aᵏ nodes, each working on a problem of size n/bᵏ. The leaves sit at depth log_b n, and there are a^(log_b n) = n^(log_b a) of them. The critical exponent is c* = log_b a. Compare f(n) with n^c*, and whichever is bigger wins:

Worked examples

See how the cases feel by comparing the growth curves:

A ratio that settles to a constant tells you the growth rate is right. For merge sort, T / (n log n) is about constant; for Karatsuba, T / n^1.585 is.

Remember: compute c* = log_b a, compare it with the exponent of f(n), and the bigger one wins; a tie adds a log factor.

Recursion over nested data

Recursion shines brightest when the data is recursive. A JSON value is either a scalar (string, number, boolean, null) or a container (list or object) of JSON values. The definition refers to itself, so the natural function does too: one branch per kind of value.

type JSON = dict[str, JSON] | list[JSON] | str | int | float | bool | None

def count_leaves(value: JSON) -> int:
    if isinstance(value, dict):
        return sum(count_leaves(v) for v in value.values())
    if isinstance(value, list):
        return sum(count_leaves(v) for v in value)
    return 1                      # a scalar is one leaf

The same shape walks directory trees (a directory contains files and directories), HTML documents, abstract syntax trees, organization charts, and comment threads. match statements make the branches especially readable:

Remember: when the data's definition mentions itself, write one branch per kind of value and let the recursion mirror the shape of the data.

Practice

Each exercise is graded in your browser. Start each with the base case.

def digit_sum(n):
    if n < 10:
        return n
    return n % 10 + digit_sum(n // 10)

def fast_pow(x, n):
    if n == 0:
        return 1
    half = fast_pow(x, n // 2)
    result = half * half
    if n % 2:
        result *= x
    return result

from functools import cache

@cache
def grid_paths(rows, cols):
    if rows == 1 or cols == 1:
        return 1
    return grid_paths(rows - 1, cols) + grid_paths(rows, cols - 1)

flatten({"a": {"b": 1}, "c": [10, {"d": 2}]})
# {"a.b": 1, "c.0": 10, "c.1.d": 2}

def flatten(value, prefix=""):
    if isinstance(value, dict):
        items = value.items()
    elif isinstance(value, list):
        items = enumerate(value)
    else:
        return {prefix: value}
    result = {}
    for key, child in items:
        child_prefix = f"{prefix}.{key}" if prefix else str(key)
        result.update(flatten(child, child_prefix))
    return result

def max_depth(value):
    best = 0
    stack = [(value, 0)]
    while stack:
        item, depth = stack.pop()
        if isinstance(item, list):
            best = max(best, depth + 1)
            for child in item:
                stack.append((child, depth + 1))
    return best

def subsets(items):
    if not items:
        yield []
        return
    first, rest = items[0], items[1:]
    for subset in subsets(rest):
        yield subset
        yield [first] + subset

Mini-project: recursive file-tree size analyzer

pixi init treesize && cd treesize
pixi run python treesize.py ~/Downloads --top 5

from dataclasses import dataclass, field
from pathlib import Path

@dataclass
class Node:
    path: Path
    size: int = 0
    children: list["Node"] = field(default_factory=list)

def scan(path: Path) -> Node:
    """Return a Node whose size includes everything beneath path."""
    node = Node(path)
    for entry in path.iterdir():
        if entry.is_symlink():
            continue
        if entry.is_dir():
            child = scan(entry)          # leap of faith
            node.children.append(child)
            node.size += child.size
        else:
            node.size += entry.stat().st_size
    return node

Quiz

Recap

• A recursive function has a base case and a recursive case on a strictly smaller input; correctness is induction, and the leap of faith is trusting the smaller call.
• Each call is a frame on the call stack. Stack space is O(depth); the default limit is about 1000 frames and Python never eliminates tail calls.
• Recursion trees show the work: depth is space, nodes × work per node is time.
• functools.cache turns repeated subproblems into lookups, often turning exponential into polynomial time.
• Any recursion can be rewritten with an explicit stack, which is the right choice when depth grows with input size.
• Divide and conquer splits, recurses, and combines; the master theorem compares f(n) with n^(log_b a).
• Recursive data (JSON, file trees, ASTs) is best processed by functions with one branch per kind of value.

Going further

• sys.setrecursionlimit and functools.cache in the Python docs
• itertools.permutations, combinations, and product
• Guido van Rossum, "Tail Recursion Elimination" (2009)
• Next: M29 Sorting puts merge sort and quicksort under the microscope.