Recursion & Recursive Algorithms

Recursion is a control-flow technique: a routine solves the current state by invoking the same contract on one or more smaller states. It is natural when the data is recursive—a list tail, a tree's children, a grammar's subexpression—or when a search state expands into similar states. The key is not the self-call itself; it is a valid descent relation and an honest account of the continuations kept while those calls return.

The four parts of a recursive design #

Every well-founded recursive routine needs four explicit ingredients.

The last distinction matters. f(0) may be a base case, but f(n) -> f(n + 1) never approaches it for positive n. Termination follows from strict descent in a well-founded relation, not from the mere presence of an if branch.

Recursive functions are not confined to direct self-calls. In mutual recursion, parse_expression may call parse_term, which calls parse_factor, which can call parse_expression again. The descent proof then applies to the cycle in the call graph, often using a lexicographic measure such as (remaining input, grammar phase).

What a call keeps alive #

Conceptually, a non-tail call creates an activation containing:

• parameter values and local variables;
• a continuation—where execution resumes after the callee returns;
• intermediate values needed by that continuation;
• implementation bookkeeping such as a return address and saved registers.

Nested calls form a last-in, first-out stack because the most recent continuation must resume first. A compiler may inline a call, keep values in registers, allocate frames differently, or eliminate a tail call, so a language-level activation is not necessarily one physical machine-stack frame. The observable rule is that unfinished work remains somewhere until the child result is consumed.

Structural recursion: follow the shape of the data #

An inductive data type comes with a termination argument. A finite binary tree is either empty or a node containing two smaller finite trees, so a function that recurses only into children is structurally decreasing.

def tree_size(node):
    if node is None:
        return 0
    return 1 + tree_size(node.left) + tree_size(node.right)

The contract is: return the number of nodes in the finite tree rooted at node.

Correctness by structural induction. The empty tree contains zero nodes, matching the base result. For a nonempty node, assume each recursive call returns the size of its child tree. The whole tree is the disjoint union of its root, left subtree, and right subtree, so 1 + left_size + right_size is its size.

Termination. Both child trees are proper structural subterms of the current tree. A finite tree has no infinite chain of proper child subtrees, so calls must reach empty children.

That argument depends on the data contract. If left or right can point back to an ancestor, the value is a graph, not a tree: the routine may loop forever. If two parents share a subtree, it terminates but counts the shared nodes twice. A recursive shape is not inferred from field names; acyclicity and ownership or sharing semantics belong in the precondition.

Proof assistants make this boundary concrete. Lean accepts structural recursion when it can identify a decreasing parameter; for definitions that are not syntactically structural, it requires or infers a well-founded measure.

Well-founded recursion: decrease a semantic measure #

Some algorithms recurse to a value that is not a literal subcomponent of the input. Euclid's algorithm is the canonical example:

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

Assume $a \ge 0$ and $b \ge 0$, with at least one argument nonzero. When $b>0$, division gives

$$0 \le a \bmod b < b.$$

Using the second argument as a natural-number measure, every recursive call strictly decreases. The identity

$$\gcd(a,b)=\gcd(b,a \bmod b)$$

preserves the result because a number divides both $a$ and $b$ exactly when it divides both $b$ and $a-qb$, with $q=\lfloor a/b\rfloor$. At b == 0, the domain assumption gives $a>0$; the positive common divisors of $a$ and zero are the divisors of $a$, so the returned $a$ is the greatest one. Descent proves termination; the divisor identity proves functional correctness.

This is the recursive form of a loop variant. The general obligation for a call from state $x$ to state $y$ is

$$y \prec x$$

where $\prec$ has no infinite descending chain. Natural numbers under <, finite structures under “proper subterm,” and lexicographic tuples of such measures are common choices. See correctness and termination for the full proof pattern.

Work is not call depth #

A recurrence describes how much total work the recursive decomposition performs. The maximum number of simultaneously active calls describes stack depth. They can differ by orders of magnitude.

Here $n$ is the input size and $\varphi=(1+\sqrt5)/2$. Space is approximately active depth times live frame size, plus heap data retained by those frames. Total call count does not determine peak stack use: a traversal may make millions of calls with depth 30, while a linear chain of only tens of thousands of calls can exhaust a bounded runtime stack.

Recurrence solving belongs with recurrences and divide and conquer. Before solving one, state what $n$ measures and whether subproblems overlap; otherwise an elegant recurrence may describe a different algorithm.

Repeated states turn a recursion tree into wasted work #

Naive Fibonacci computes fib(k) many times. The recursive specification is compact, but the execution tree forgets that identical states have identical answers.

Memoization stores the result keyed by the complete logical state. Each distinct state is then solved once, turning an overlapping recursion tree into evaluation of a dependency DAG. For Fibonacci this changes exponential work to $\Theta(n)$ work and $\Theta(n)$ stored results.

This is not a free decorator:

• the key must include every input that affects the result;
• mutable state and external effects can make a cached answer stale or semantically wrong;
• an “in progress” marker may be needed to detect cycles rather than waiting recursively for the same state;
• retained cache entries change memory lifetime and can dominate the algorithm's space.

When the dependency order can be enumerated directly, bottom-up dynamic programming removes both call overhead and stack depth. Top-down memoization is often easier when only a sparse subset of states is reachable.

Tail position and what it really guarantees #

A call is in tail position when its result is immediately the result of the current activation: there is no pending multiplication, addition, cleanup, or alternate return path that needs the caller's frame. For the following factorial routines, assume the input $n$ is a nonnegative integer.

# Not tail-recursive: multiplication remains after the child returns.
def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

# The recursive call is in tail position.
def factorial_tail(n, acc=1):
    if n == 0:
        return acc
    return factorial_tail(n - 1, acc * n)

In a properly tail-recursive implementation, the second form can replace the current continuation instead of stacking a new one. The Scheme R7RS report requires implementations to support an unbounded number of active tail calls and explains the reason: returning to an intermediate continuation only to return again is semantically redundant.

Tail position is a semantic opportunity, not a portable resource guarantee across languages and toolchains:

• Scheme specifies proper tail recursion.
• LLVM's ordinary tail marker is an optimization request subject to constraints; musttail requires the transformation and guarantees that a recursive call cycle does not cause unbounded stack growth, but imposes strict calling-convention and signature rules.
• Python documents a maximum interpreter recursion depth to prevent the C stack from overflowing. A tail-recursive spelling therefore gives no language-level promise of constant stack space in ordinary Python code.

The portable transformation is direct:

def factorial_loop(n):
    acc = 1
    while n != 0:
        acc *= n
        n -= 1
    return acc

The loop variables are exactly the tail function's parameters. Each iteration performs the parameter update that the recursive call would have performed.

Eliminating non-tail recursion with explicit frames #

Tail recursion needs only the next parameters. General recursion has pending work, so elimination requires an explicit stack whose records preserve that work.

For preorder traversal, no child result is needed after a child returns, so frames can be just nodes:

def preorder(root):
    if root is None:
        return []

    result = []
    stack = [root]
    while stack:
        node = stack.pop()
        result.append(node.value)

        # LIFO: push right first so left is processed first.
        if node.right is not None:
            stack.append(node.right)
        if node.left is not None:
            stack.append(node.left)
    return result

For postorder traversal, expression evaluation, or recursive descent with cleanup, a frame also needs a phase such as “left child not started,” “left result available,” or “right result available.” Omitting that continuation state is the usual reason a supposedly iterative rewrite changes output order or loses a partial result.

An explicit stack does not reduce the asymptotic $O(h)$ auxiliary space for a depth-$h$ traversal. It moves that storage to a container with controllable capacity, error handling, instrumentation, and allocation policy. It also permits changing the frontier discipline: a stack gives depth-first search; a queue gives breadth-first search; a priority queue gives best-first search. Those are algorithm changes, not mere syntax changes.

Recursion over trees is not graph traversal #

Recursive code often assumes that each state has a unique parent and that following children must terminate. Graphs violate both assumptions. A cycle causes repeated calls; converging edges cause repeated work even without a cycle.

For graph traversal, maintain explicit state such as:

• undiscovered — no call/work item has claimed the vertex;
• discovered — claimed and possibly still active;
• finished — all outgoing edges processed.

Mark a vertex discovered before descending to neighbors. Marking it after return fails on a back edge because the recursive cycle forms before either call can finish. In backtracking over reversible states, the rule may instead be “mark on entry, unmark on exit”; that solves a different problem—enumerating paths rather than visiting each vertex once—and cleanup must occur on every return and exception path.

Failure modes and diagnostics #

Choosing recursion deliberately #

Prefer direct recursion when the code mirrors a finite inductive structure, the maximum depth is safely bounded, and the recursive contract makes the implementation easier to prove. Prefer an explicit loop or stack when input depth is adversarial or unbounded, when memory exhaustion must be handled predictably, when traversal order must change dynamically, or when the runtime does not guarantee the tail behavior you need.

Before shipping a recursive algorithm, answer five questions:

1. What is the exact base domain?
2. What well-founded measure decreases on every recursive edge?
3. What is the worst-case active depth, not the average depth?
4. Do different paths reach the same state, requiring memoization or a visited set?
5. What pending work does each frame retain, and can it be represented more safely as explicit state?

Recursion is safest when its proof and its storage model tell the same story: smaller states satisfy the same contract, the descent cannot continue forever, and the runtime can hold the longest chain of unfinished continuations.