Recursion, stack frames, and termination

Prerequisites: Functions, conditionals, loops, and finite lists.

Learning objectives

• Trace separate local environments for recursive calls.
• Identify base cases and a decreasing measure.
• Compare recursion with an explicit work stack.

Each call has its own unfinished computation

Recursion occurs when a function calls itself, directly or indirectly. Each call has its own parameters and local variables. A call stack records the work waiting for a result. Thinking of recursion as “jump back to the start” misses this suspended work and makes traces confusing.

Here is Euclid's algorithm for the greatest common divisor of two nonnegative integers, not both zero. The function also defines gcd(0,0) as zero by its base case, but callers may choose a narrower mathematical contract.

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

assert gcd(84, 30) == 6
assert gcd(0, 9) == 9

The first call asks for gcd(84,30), then waits for gcd(30,24), then gcd(24,6), then gcd(6,0). The last call returns 6. Each waiting call returns the same result. Correctness follows because replacing (a,b) with (b,a mod b) preserves the common divisors: if a=q*b+r, any divisor common to a and b divides r, and any divisor common to b and r divides a.

Termination uses another fact. Whenever b is positive, the new second argument a mod b is nonnegative and strictly smaller than b. A nonnegative integer cannot decrease strictly forever. This argument depends on the specified input domain; a base case without guaranteed progress toward it does not establish termination.

Not every recursive call is cheap

A recursive sum may return head + sum(tail), leaving an addition pending in each frame. An iterative version can maintain an accumulator instead. Some languages optimize certain final-position recursive calls, but Python does not generally eliminate recursive frames. Even a logically terminating recursion can exceed the runtime's recursion limit on a sufficiently large input.

Branching recursion also changes cost. A naive Fibonacci implementation computes the same subproblems repeatedly. A call tree, rather than merely its depth, reveals that duplicated work. Memoization stores results for distinct subproblems; an iterative dynamic program can organize them in dependency order.

Recursion is especially natural for data defined recursively, such as syntax trees. Still, choose it because the structure clarifies the algorithm, not because recursion is inherently more advanced. For deep inputs, an explicit stack can preserve the same traversal while making resource use visible. State the invariant connecting stack entries to remaining work, just as you would state an invariant for an ordinary loop.

Practice problem

Design a recursive function that counts integers in a nested structure whose values are either integers or finite lists of such values. Count [2,[3,[],[4]],5] as four integers. State the base cases and a termination measure. Then describe an iterative implementation using an explicit stack and explain how it handles the same input. Discuss what fails if a list contains a reference to itself, and whether a recursion depth error means the mathematical algorithm is incorrect for finite acyclic inputs.

Worked solution

An integer contributes one; a list contributes the sum of the counts of its elements, with an empty list contributing zero. For a finite acyclic structure, each recursive call descends to a strict substructure, so the number of nodes in the current subtree decreases. An iterative version starts with the input on a stack, repeatedly pops one value, increments a counter for an integer, and pushes a list's elements otherwise. Its invariant is that the counter plus the number of integers represented by pending stack entries equals the original total. A self-reference breaks the tree model and can cause either version to loop indefinitely. A recursion depth error on a very deep finite input is an implementation resource limitation, not a counterexample to the mathematical termination proof. The contract and implementation limits should both be documented.

Check your understanding

Which fact establishes termination of gcd(a,b) for nonnegative integer inputs?

• The function contains an if statement.
• The positive second argument strictly decreases and remains nonnegative.
• The result is always small.

Explanation

The remainder provides a well-founded decreasing measure; merely having a base case does not.

Why can a finite recursive traversal fail in Python even if its algorithm terminates?

• Python cannot represent trees.
• A correct recurrence guarantees infinite memory.
• Its required call depth can exceed the runtime limit.

Explanation

Mathematical termination and the resources required by a particular implementation are separate claims.

Primary reading

• Structure and Interpretation of Computer Programs: University of California, Berkeley
• The Python Tutorial: Python Software Foundation

Open the study and save your work →