# Recursion

Source: https://codewiki.com/foundations/recursion/

> - **what**: Recursion lets a routine solve a problem by calling itself on smaller instances, with base cases that return directly.
> - **trap**: A recursive function can be logically correct and still exhaust the call stack when input depth is large or adversarial.
> - **fix**: Prove that every recursive edge decreases a well-founded measure, trace frames and bounds, then use an explicit stack when depth isn't safely bounded.

## What it is and why it exists

Recursion is a control technique in which a routine reaches another invocation of itself. The call may be direct, as when `walk()` calls `walk()`, or indirect, as when two routines call each other. What matters is that execution can return to an earlier routine through a cycle of calls.

A useful recursive definition has at least one base case that produces an answer without another recursive call. Its recursive case reduces the current problem to one or more smaller instances and combines their answers. Both parts are necessary: the base case supplies a stopping answer, while the reduction makes it reachable.

Recursion exists because some data and problems are recursive by shape. A directory contains entries, some of which are directories; a tree is a node attached to smaller trees; divide-and-conquer search selects a smaller interval. Code that follows that definition can expose the same boundary and reduction used in a correctness proof.

The technique also connects programs to induction. To justify a recursive algorithm, show that it works for the smallest valid inputs and that, if smaller calls are correct, the current call combines them correctly. This local argument can cover every reachable input size without tracing every concrete input.

Recursion is not automatically simpler or faster than iteration. A call consumes execution state, and the maximum simultaneous calls depend on input shape rather than only the number of elements. Use recursion when the recursive structure is clear and depth has a defensible bound; use iteration when an explicit worklist gives safer control.

You meet recursion in syntax-tree visitors, filesystem walkers, graph searches, parsing, binary search, merge sort, quicksort, backtracking, and memoized dynamic programming. Some of these algorithms branch into several calls. Others have only one recursive continuation and translate directly to a loop.

### Three questions before coding

State the contract for one call before writing the self-call. For `total_bytes(entry)`, the contract might be: return the total file bytes reachable from this entry. The recursive call then has the same contract on a child, not a vaguely related subtask.

Choose the stopping set, not just one happy-path base value. Empty collections, leaf nodes, exhausted intervals, missing solutions, and invalid inputs may each need different behavior. If the domain permits cycles, reaching a previously seen object is also a boundary condition, even though it is not a mathematical base case.

Finally, name a measure that gets smaller on every recursive edge. It might be a nonnegative count, interval width, remaining input length, tree height, or a finite set of unvisited nodes. “The input looks smaller” is not enough when the function has multiple branches or can revisit state.

## How it works

When a function calls itself, the current call pauses just as it would for any other function call. The runtime records enough state to resume it after the child call returns. That state forms a frame on the call stack.

A frame conceptually contains the call's arguments, local state, and return point. Actual frame layouts are runtime-specific, so don't build logic around their representation. The portable observation is that unfinished callers remain active until their callees finish.

For `total_bytes(directory)`, a directory frame asks for one child total at a time. A file reaches a base case and returns its own size. The directory frame resumes, incorporates that result, and eventually returns the sum to its caller.

### Calls go down; results come back up

Suppose `sum_to(3)` is defined as `3 + sum_to(2)` with `sum_to(0) == 0`. The descent creates four active calls before any addition can finish. The returns then resolve the suspended expressions in reverse order.

| Moment | Active calls, oldest first | Next action |
| --- | --- | --- |
| descend | `sum_to(3)` | call `sum_to(2)` |
| descend | `sum_to(3) → sum_to(2)` | call `sum_to(1)` |
| descend | `sum_to(3) → sum_to(2) → sum_to(1)` | call `sum_to(0)` |
| base | `sum_to(3) → sum_to(2) → sum_to(1) → sum_to(0)` | return `0` |
| unwind | `sum_to(3) → sum_to(2)` | return `1`, then `3` |
| finish | `sum_to(3)` | return `6` |

The stack is last-in, first-out: the newest frame finishes first. “Unwinding” means returning through suspended callers, whether the result is normal or an exception is propagating. It does not mean the algorithm is running backward over the input.

### Base cases and recursive cases

Check the base case against the call's full domain. Binary search commonly uses a half-open interval `[low, high)`. Its empty base case is `low >= high`, not merely `low == high`, because the stronger check remains safe if a future change overshoots a boundary.

The recursive case must preserve the contract. If the target is greater than the middle value, searching `[middle + 1, high)` is a smaller instance of the same problem. Searching `[middle, high)` can repeat a one-element interval forever because integer division may choose the same middle again.

Order the checks so that unsafe work cannot precede the base case. A tree walker should recognize a leaf before reading absent children. An interval search should recognize emptiness before indexing its midpoint.

### Termination as a proof obligation

A common termination proof uses a variant: a value drawn from a set that has no infinite descending chain. For a nonnegative integer measure, prove two facts:

1. Every valid call starts with a measure at least zero.
2. Every recursive call makes that measure strictly smaller.

Those facts rule out infinite descent, so a call must eventually reach a boundary. If a function makes two recursive calls, prove the decrease for both. If it sometimes retries with unchanged state, the measure does not establish termination.

Graph traversal needs more than structural intuition because a graph can contain cycles. Track visited identities and define the measure as the number of reachable, unvisited nodes. Mark a node before exploring its neighbors so a back edge cannot re-enter it first.

### Time and space are separate

Count total calls to reason about time, and maximum simultaneous calls to reason about stack space. A balanced binary-tree traversal can visit `n` nodes in `O(n)` time with `O(log n)` call depth. A chain-shaped tree still takes `O(n)` time but reaches `O(n)` call depth.

Recursive binary search makes one call on about half the interval, so both time and call depth are `O(log n)`. Naive recursive Fibonacci makes two overlapping calls for most inputs; its depth is linear, but its call count grows exponentially. Depth alone does not describe work.

Some languages or compilers eliminate certain tail calls, but Python does not promise tail-call elimination. Rewriting a Python function so its recursive call is the final expression does not make unbounded depth safe. Treat the configured recursion limit as a guard, not an input-capacity target.

### Reading a frame trace

A useful trace distinguishes entry, child call, child return, and function return. Logging only the argument at entry shows the descent but hides how partial answers combine. Logging only final results hides which frame produced each value.

Indent by current depth when you need a compact human-readable trace. Include the subproblem identity and boundary state, such as a node ID or interval bounds. Avoid dumping whole recursive objects because repeated nested representations can overwhelm the evidence you need.

For a suspicious branch, record four facts in order:

1. The current call's contract-relevant inputs.
2. Whether a base case matched and what it returned.
3. Each child input and the termination measure before the call.
4. The child result and how the current frame combines it.

A debugger presents the same information through stack frames. Stop at the deepest surprising call, then move upward to find the first caller that supplied an invalid subproblem. The topmost exception frame is often where the failure surfaced, not where the invariant was first broken.

### Choosing recursion or an explicit worklist

The two forms can implement the same traversal, but they expose different control surfaces. Recursive code delegates pending work and resume points to the language runtime. Iterative code represents them as application data.

| Requirement | Usually clearer form |
| --- | --- |
| Small, structurally bounded tree | Recursion |
| Untrusted or chain-shaped depth | Explicit stack or queue |
| Pause, serialize, or distribute pending work | Explicit worklist |
| Natural post-order combination | Recursion or explicit frames with phases |

An explicit stack is not always a performance optimization. It can allocate as much memory as recursive traversal, especially on a wide frontier. Its main benefit is control over representation, limits, scheduling, and failure behavior.

Use a queue rather than a stack when breadth-first order is part of the algorithm. This changes which nodes are processed first and usually changes peak memory from depth-related storage to frontier-width storage. Converting recursion is therefore also a traversal-order decision.

If the recursive version is already correct, preserve its observable contract during conversion. Match visitation order, error timing, duplicate handling, and partial-result policy. Tests should compare both implementations on small trees before the iterative one takes over large inputs.

Keep the recursive version as a small test oracle only when its accepted depth is tightly limited. Two implementations with the same unchecked assumptions do not provide independent evidence.

## Examples

The examples use Python 3.14. They progress from structural recursion, through a traced divide-and-conquer call chain, to an iterative replacement for unsafe input depth.

### Summing a recursive directory shape

The data distinguishes file leaves from directory branches. `total_bytes()` returns directly for a file and delegates each directory child to the same contract.

<!-- quick -->

```python
# file: folder_size.py
def total_bytes(entry):
    if entry["type"] == "file":
        return entry["bytes"]

    return sum(total_bytes(child) for child in entry["children"])


project = {
    "type": "directory",
    "children": [
        {"type": "file", "bytes": 240},
        {
            "type": "directory",
            "children": [
                {"type": "file", "bytes": 760},
                {"type": "file", "bytes": 120},
            ],
        },
    ],
}

print(f"project: {total_bytes(project)} bytes")
```

```text
project: 1120 bytes
```


<!-- /quick -->

The proof follows the data. A file returns the correct total directly. Assuming each child call returns its correct total, summing those totals returns the correct directory total.

Termination requires the in-memory structure to be a finite tree. Real filesystems can expose symbolic-link cycles, permission failures, and entries that change during traversal. A production walker must define whether it follows links, how it identifies visited directories, and how errors affect the total.

### Tracing recursive binary search

This search uses half-open bounds. The printed depth makes active call creation visible; each recursive call narrows the interval before the earlier frame can return.

```python
# file: recursive_binary_search.py
def find_order(order_ids, target, low=0, high=None, depth=0):
    if high is None:
        high = len(order_ids)

    print(f"depth={depth}: search [{low}, {high})")
    if low >= high:
        return -1

    middle = (low + high) // 2
    if order_ids[middle] == target:
        return middle
    if order_ids[middle] < target:
        return find_order(order_ids, target, middle + 1, high, depth + 1)
    return find_order(order_ids, target, low, middle, depth + 1)


orders = [104, 117, 203, 258, 311, 409, 550]
position = find_order(orders, 409)
print(f"order 409 is at index {position}")
```

```text
depth=0: search [0, 7)
depth=1: search [4, 7)
order 409 is at index 5
```

The first frame chooses index `3`, whose value is `258`, then searches `[4, 7)`. The second frame chooses index `5` and returns it. That value immediately passes through the first frame because no combination work remains.

The interval width `high - low` is the termination measure. The right branch excludes `middle` with `middle + 1`; the left branch uses `middle` as its exclusive upper bound. Both widths are strictly smaller whenever the base case has not been reached.

Printing from the start of the function shows descent. Printing after each recursive call would show returns in the opposite order. In production, pass trace state only when it belongs to the API or use a debugger or structured logger rather than permanently mixing diagnostics into the algorithm.

### Replacing recursion for a deep tree

The recursive and iterative functions implement the same node-counting contract. The generated input is a 1,201-node chain, a valid tree whose depth is unsafe for Python's normal recursion guard.

```python
# file: walk_deep_tree.py
def count_nodes_recursive(node):
    return 1 + sum(count_nodes_recursive(child) for child in node["children"])


def count_nodes_iterative(root):
    count = 0
    pending = [root]
    while pending:
        node = pending.pop()
        count += 1
        pending.extend(node["children"])
    return count


root = {"children": []}
for _ in range(1_200):
    root = {"children": [root]}

try:
    print(f"recursive: {count_nodes_recursive(root)} nodes")
except RecursionError:
    print("recursive: depth limit reached")

print(f"iterative: {count_nodes_iterative(root)} nodes")
```

```text
recursive: depth limit reached
iterative: 1201 nodes
```

The list `pending` is an explicit LIFO stack. Unlike the interpreter's call stack, application code can inspect it, cap it, spill work elsewhere, or attach metadata to each pending item. Its size is still a resource cost; iteration moves control of that cost into the algorithm rather than making it disappear.

This conversion is straightforward because the recursive function has no work after visiting its children except addition. When post-order work matters, store an explicit phase with each node, such as `(node, expanded)`, and push a second entry that runs after the children. For backtracking, the explicit item may also carry the partial path or undo information.

Do not make the recursion limit the primary fix for untrusted depth. A higher setting permits more Python frames and can expose the process to a lower-level stack failure. An explicit stack plus an application limit gives a reviewable failure policy.

## Pitfalls

### A base case that does not cover the domain

> **Pitfall:** Code handles `n == 0` but accepts negative `n`, or checks for a leaf only after reading its children. The nominal base case exists, yet some valid or admitted inputs can never reach it safely.

**Fix:** define the accepted domain and every boundary outcome before the recursive case. Reject invalid inputs at the public boundary, and place base checks before indexing or child access. Test the smallest valid value, an empty value, and one invalid value.

### A recursive edge that makes no progress

> **Pitfall:** An interval search recurses on `[middle, high)` when `middle` can equal `low`, or a parser retries without consuming a token. The same state returns, so the call chain grows until a runtime guard stops it.

**Fix:** write the termination measure beside each recursive call and verify a strict decrease. For half-open binary search, exclude the tested midpoint from the next interval. Add tests for one-element and two-element inputs because boundary arithmetic stalls there first.

### Recomputing overlapping subproblems

> **Pitfall:** A direct translation of a recurrence can branch into the same states repeatedly. Naive Fibonacci looks faithful to its definition but does exponential total work, and recursive path counting can repeat even larger subtrees.

**Fix:** draw or count calls for a small input, then identify states by their complete inputs. Cache pure subproblem results with memoization, or fill a dynamic-programming table iteratively when order and memory bounds are clearer that way. Do not cache a result whose hidden dependencies can change.

### Losing path state during backtracking

> **Pitfall:** Generated search code appends a choice to one shared list and returns early without removing it. Later branches inherit stale choices, so results depend on traversal order.

**Fix:** pair every mutation with guaranteed cleanup, often through `try`/`finally`, or pass a copied immutable path when the extra allocation is acceptable. Test a failed branch followed by a successful sibling. Keep result storage separate from the current path.

### Assuming element count bounds recursion depth

> **Pitfall:** A tree with few thousand nodes may be balanced in tests but chain-shaped in production. A cyclic object graph has no finite structural depth at all. Average shape does not protect the call stack from adversarial shape.

**Fix:** derive depth from worst-case shape and trust boundary, not only total size. Track visited identities for graph-like input, enforce an application depth or work budget, and switch to an explicit stack when the safe bound is absent. Exercise a chain and a cycle in tests.

### Raising the recursion limit as capacity planning

> **Pitfall:** Increasing Python's recursion limit can postpone `RecursionError`, but it neither proves termination nor reduces memory per frame. An excessively high limit can trade a controlled exception for process failure.

**Fix:** treat the limit as a runtime guard and keep normal input comfortably below it. Replace linear-depth recursion for large or external structures. If controlled internal code truly needs a changed limit, measure the exact environment and restore the setting after the narrow operation.

<!-- deep -->

## Termination, correctness, and resource bounds

The three main arguments answer different questions. Termination asks whether every admitted call finishes. Partial correctness asks whether a finishing call returns the right result. Resource analysis asks how many calls, frames, and stored work items the algorithm may consume.

Keeping these arguments separate exposes gaps. A recursive function can terminate and return the wrong answer. It can be correct for every finite input yet be operationally unsafe because an admitted input needs too many frames.

### A proof template

Start with a precise per-call contract. For binary search: given a sorted sequence and valid half-open bounds, return the target's index within the interval or `-1` if absent. The bounds are part of the input, so their invariant belongs in the contract.

Choose the variant `V = high - low`. When the base condition is false, `V > 0`. The left branch changes the interval to `[low, middle)`, and the right branch changes it to `[middle + 1, high)`; either new width is strictly less than `V` and stays nonnegative.

Then prove partial correctness. The empty interval contains no target, so `-1` is correct. If the midpoint equals the target, returning it is correct. Sorted order excludes one half otherwise, and the induction hypothesis says the recursive result is correct for the retained, smaller interval.

Finally, state the operational bound. Each call retains only one child call, and interval width at least halves, so total calls and maximum depth are both `O(log n)`. This last statement is not part of the termination proof; it quantifies cost.

### Branching recurrences

For a tree walker, one frame can call every child. If the input is a tree, the child subtrees are disjoint, so total calls equal the number of nodes even though the source contains a loop of recursive calls. Maximum call depth equals tree height, not node count unless the tree is a chain.

For naive Fibonacci, the two branches overlap. A call for `fib(n - 2)` repeats work already contained under `fib(n - 1)`. The recurrence for running time is roughly `T(n) = T(n - 1) + T(n - 2) + O(1)`, which is exponential even though the deepest chain has only `n` frames.

Memoization changes the state graph. Each distinct `n` is computed once and later calls become cache lookups, reducing total computation to a linear number of states. The recursive depth remains linear, so a bottom-up loop may still be safer for large `n`.

### Tail position is not a depth bound

A call is in tail position when its result becomes the caller's result without more caller-side computation. That syntactic property can enable tail-call elimination in runtimes that specify or implement it. It says nothing by itself about how many logical steps the input requires.

Python keeps ordinary recursive calls visible as frames for debugging and does not guarantee tail-call elimination. A tail-recursive countdown can therefore reach `RecursionError` just like a non-tail-recursive sum. Replacing `return countdown(n - 1)` with a `while` loop is the reliable constant-stack transformation.

Accumulator parameters can move combination work into the descent, but they do not reduce Python frame count. Use them when they clarify the state transition, not as a stack-safety claim. Confirm operational space from the language guarantee and actual implementation, not from the word “tail.”

### Cycles and identity

Recursive data definitions often assume trees, but application objects may form graphs. A parent link, symbolic link, shared dependency, or malicious self-reference breaks the assumption that following an edge always reaches a smaller structural value. Without a visited set, no height proof applies.

Use stable node identity for cycle detection. Mark the identity before traversing outgoing edges, and decide whether a repeated node should be skipped, reported as a cycle, or counted again as a shared reference. Those policies produce different correct answers, so the choice belongs in the function contract.

A visited set bounds traversal by the number of reachable identities, but it also consumes memory. For a graph with `V` reachable vertices and `E` examined edges, a standard traversal takes `O(V + E)` time and `O(V)` visited storage, plus the recursive or explicit work stack.

### Preserving order with an explicit stack

Replacing recursive depth-first traversal with a stack can silently reverse sibling order. Recursive code visits children from first to last. A LIFO stack must therefore push those children from last to first if the observable visitation order must match.

Pre-order traversal processes a node before pushing its children. Post-order traversal needs a return phase because recursive code processes the node after all child calls finish. Store frames such as `(node, next_child_index)` or push `(node, expanded=False)` followed by an expanded marker.

This explicit representation resembles what the call stack supplied: pending work, local progress, and a resume point. The advantage is policy control. You can cap pending items, serialize work, yield cooperatively, or return a domain-specific “too deep” result without relying on interpreter failure.

### Exceptions and cleanup

An exception can leave through many recursive frames. Language-level cleanup such as `finally` and context managers still runs while the exception propagates, but ordinary statements after the child call do not. Backtracking code that depends on a later `path.pop()` therefore needs guaranteed cleanup.

Avoid catching `RecursionError` deep inside the same recursive routine and then continuing with partially mutated state. The error indicates that the runtime guard was reached at an arbitrary active frame. Validate or budget depth before descent, or catch it at a boundary that can discard the entire operation safely.

<!-- /deep -->

[Checkpoint: foundations/recursion](https://codewiki.com/foundations/recursion/#checkpoint)

## Further reading

- [Python 3.14 `sys`: recursion limit](https://docs.python.org/3.14/library/sys.html#sys.getrecursionlimit) — the runtime guard and the risk of setting it too high.
- [Python 3.14 built-in exceptions: `RecursionError`](https://docs.python.org/3.14/library/exceptions.html#RecursionError) — the exception raised when maximum recursion depth is exceeded.
- [Python 3.14 tutorial: using lists as stacks](https://docs.python.org/3.14/tutorial/datastructures.html#using-lists-as-stacks) — the basic container operation used by explicit-stack traversals.
- [MIT 6.005: recursion](https://web.mit.edu/6.005/www/fa16/classes/14-recursion/) — recursive decompositions, base cases, and recursive steps.