Recursion and the call stack

Problem

Many problems have the shape "the answer for this input is built from the answers for smaller inputs of the same kind". A tree is a root plus smaller trees. A list is a head plus a shorter list. A grid can be cut into four smaller grids. Writing that as nested loops is awkward or impossible because you don't know in advance how deep the nesting goes; recursion lets the structure of the code mirror the structure of the data.

Intuition

Imagine asking someone to count the people in a long queue. They can't see the whole queue, so they tell the person ahead, "count everyone in front of you and tell me the number", then add one for themselves. The person at the front, with nobody ahead, just says "zero". The answer travels back down the line, one addition at a time. That is the entire idea: hand off a smaller version of the job, trust the answer, and finish your own small piece.

Three things make it work. A base case that is answered directly, a recursive case that calls on a strictly smaller input, and a combine step that turns the smaller answers into this one. Leave out the base case and the queue never ends; call on an input that is not smaller and you go around in a circle.

Repeated subtrees are the signal that memoization will help.

Mechanics

The call stack

Each call gets a frame: its own copy of the arguments and local variables, plus the place to return to. Frames are stacked. A call pushes a frame, a return pops it, and only the top frame is running. At the deepest point the stack holds one frame per nested call, which is why a recursion n levels deep costs O(n) space even if it allocates nothing else. CPython caps the depth at about 1,000 by default; exceeding it raises RecursionError.

Why it is correct

Prove a recursive function correct by induction. Base: it returns the right answer for the smallest inputs. Step: assuming it returns the right answer for every smaller input, the combine step returns the right answer for this one. The leap of faith you are asked to take while writing the code, "assume the call works", is exactly the induction hypothesis. Termination needs a measure that strictly decreases toward the base case, such as the size of a list or the height of a subtree.

Counting calls with the recursion tree

Draw one node per call and connect each call to the calls it makes. The total work is the sum of the work at each node. For fib(k) = fib(k − 1) + fib(k − 2), each node has two children, so the tree roughly doubles in size at each level and the number of calls grows exponentially (the exact count grows by a factor of about 1.618 per step). For "cut the input in half and combine in linear time", each level of the tree does n work in total and there are log₂ n levels, so the total is O(n log n).

Turning recursion into iteration

Any recursion can be rewritten with an explicit stack, using the frames you would have had as data. When the recursion is a single tail call (the function returns the result of one call on a smaller input) a plain loop suffices. When it makes more than one call, push the pending work onto a list and pop it in a loop. Do this when the depth could exceed 1,000, or when the interviewer asks you to avoid recursion.

Worked example

Compute 2¹⁰ by recursive squaring: to get b^e, compute b^⌊e/2⌋, square it, and multiply by b once more if e is odd. The table is every call and return, in the order they happen, with the stack depth (frames active) just after the event.

The answer is 1024, found with 5 calls and a stack at most 5 frames deep, where multiplying 2 by itself ten times would have taken ten steps.

Amber is a frame just pushed; green is the frame that just returned its value to the one below.

Now count the cost of getting recursion wrong. The same fib recursion, with and without a memo table that remembers each answer:

Naive calls grow by about 1.6× per step (67 at n = 8); memoized calls grow by 2 per step (15). Same code, with one cache, from exponential to linear.

Implementation

def solve(state):
    if is_base_case(state):                    # 1. answer directly
        return base_answer(state)
    parts = [solve(smaller) for smaller in shrink(state)]   # 2. strictly smaller inputs
    return combine(parts)                      # 3. build this answer from theirs


def power(base, exponent):                     # O(log exponent) time and stack
    if exponent == 0:
        return 1
    half = power(base, exponent // 2)
    return half * half * (base if exponent % 2 else 1)


from functools import cache

@cache                                         # memoization: each argument computed once
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)


def sum_list(items):                           # recursion turned into a loop (tail position)
    total = 0
    for x in items:
        total += x
    return total


def preorder(root):                            # explicit stack replaces the call stack
    out, stack = [], [root]
    while stack:
        node = stack.pop()
        if node is None:
            continue
        out.append(node.val)
        stack.append(node.right)               # pushed first, so it is visited last
        stack.append(node.left)
    return out

Variations and edge cases

• Divide and conquer. Merge sort splits a list in half, sorts each half recursively and merges them in linear time. The merge is the combine step; the base case is a list of length 0 or 1.
• Pass state down, return answers up. Extra parameters carry what the call needs from above (a running path, a bound); the return value carries what the caller needs from below. Choosing which goes where is most of the design.
• Helper functions. When the recursion needs extra parameters that the public signature doesn't have, define an inner function and recurse on that.
• Raising the limit. sys.setrecursionlimit can help for depths in the low tens of thousands but risks crashing the interpreter. Prefer the explicit stack.
• Edge cases: the empty input, a single element, a missing base case for an odd split (a size-1 half), and mutating a shared list that sibling calls also read.

Complexity and tradeoffs

• Brute-force baseline. Plain recursion usually is the brute force: it tries every choice, and the size of its call tree is the baseline cost, O(2ⁿ) for Fibonacci or subsets and O(n!) for permutations. Memoization, dynamic programming and pruning are all ways of making that tree smaller.
• Time is the number of calls times the work per call. Draw the tree, count the nodes, and multiply. Halving gives O(log n) calls; two half-size calls plus linear work give O(n log n); two calls on n − 1 give O(2ⁿ).
• Space is the maximum stack depth plus anything allocated. Depth is the height of the recursion tree, not its size: fib(5) has 15 nodes but is only 5 frames deep.
• Overhead. Function calls are slower than loop iterations in Python. When a loop expresses the same thing cleanly, the loop wins.
• When it fails. Deep recursion hits the limit; overlapping subproblems make it exponential until memoized; and mutable state shared across calls makes bugs hard to see. In those cases use an explicit stack, a memo table or a bottom-up table.

Problems

Two problems here, both divide and conquer on a structure: the grid is cut into quadrants and the array is cut in half. Many more recursive problems live on the tree and backtracking pages; the "also uses" list shows where recursion shows up elsewhere.

Medium

• 427. Construct Quad Tree NeetCode 250
  If a square is uniform it becomes a leaf; otherwise split it into four quadrants and build each one recursively.
• 912. Sort an Array NeetCode 250
  Implement merge sort, heap sort or randomized quicksort, which guarantee or expect O(n log n) where simple sorts are quadratic.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 104. Maximum Depth of Binary Tree Easy
• 206. Reverse Linked List Easy
• 24. Swap Nodes in Pairs Medium
• 50. Pow(x, n) Medium
• 148. Sort List Medium
• 394. Decode String Medium

Connections

Tree traversal, backtracking and memoized dynamic programming are all recursion with a specific shape of tree: a fixed shape given by the data (trees), a tree of choices (backtracking), or a tree of overlapping subproblems collapsed by a cache (DP).

Check yourself

References

• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms: section 2.3 (divide and conquer) and chapter 4 (recurrences and the master method).
• Sedgewick and Wayne, Algorithms: section 1.1 (recursion) and 2.2 (mergesort).
• Steven Skiena, The Algorithm Design Manual: the sections on recursion and divide and conquer.
• Python documentation: functools.cache and sys.setrecursionlimit.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.