Recursion — Call Stack, Base Case, Worked Examples

Review boundary and corrected contracts

Naive Fibonacci makes Θ(φⁿ) calls, with O(2ⁿ) a loose bound. A cold memoised call with n ≥ 2 reaches n+1 states 0..n; n=0 or 1 reaches only its base state. Recursive list slicing costs quadratic live reference storage, and inorder concatenation can be quadratic on a skew tree. Python interpreter depth is not the same as one C-stack frame per call. The prefix-path exercise is backtracking over running counts, not memoisation.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Write recursive solutions confidently — with a real base case, a shrinking argument, and the memoisation instinct for reusing repeated states when their count and transition work are tractable.

Why this session exists

Recursion is both a supported calling pattern and a way of decomposing a problem. Once you can see a problem as the same problem on a smaller input, huge swaths of DSA collapse: trees, graphs, divide-and-conquer, dynamic programming, backtracking, parsers, and the entire functional-programming toolkit. This session gives you the mental model AND the tools for controlling work and depth: memoisation reduces repeated work, iterative rewrites avoid interpreter recursion depth, and tail-form is useful for deriving a loop rather than promising Python optimisation.

You will be able to

• State the three parts of every recursion (base case, recursive case, shrinking argument) and identify them in any code you read.

• Write factorial, Fibonacci, tree traversal, and merge-sort recursively without notes.

• Memoise Fibonacci and explain why its O(n) states and constant-count transitions give linear arithmetic-operation count, not a universal polynomial-time caching guarantee.

• Convert a recursive function into an iterative one using an explicit stack — and know when you have to.

• Diagnose RecursionError by checking termination and maximum depth; use bounded inputs or an iterative rewrite rather than raising the limit blindly.

Prerequisites

• S026 · Stacks & Queues — the call stack is a stack.
• S007 · Python Functions — recursion is a special case of function calling itself.

Pre-read · skim before the session (25 min total)

Further reading: functools.lru_cache

Further reading: Tail Call (Wikipedia)

Optional archived link: Estimation game — not verified as a Big-O lesson; the recurrence analysis here is the required practice.

(a) Intuition · 5 min

Recursion is the ‘ask a smaller version of yourself’ pattern

Real: You want to count the books on a giant shelf. You could count them all yourself (tedious). Or: you tell the person next to you ‘count the LEFT half, tell me the number; I'll count the right half; we add.’ They face the same problem — but on half the shelf — so they hand it to two more people. The shelf shrinks by half each time; eventually someone has a shelf of one book and can just answer ‘1’. That's recursion: assume you already have the answer for a smaller version of the problem, then combine it. The base case is when the problem is small enough to answer directly.

 
    A recursive function calls itself with a smaller / simpler input and combines the result. Three ingredients: base case (small enough to answer directly), recursive case (reduce to smaller problem + combine), and a shrinking argument (why we always get closer to the base case).
    Miss the base case → infinite recursion → RecursionError. Miss the shrinking argument → same crash. Miss the recursive case → not recursion.
  

The three-part recipe

Every correct recursion has these three parts

• Base case — the smallest input(s) where you can answer directly, no further recursion. Usually 0, 1, empty list, single node.

• Recursive case — assume the function works on smaller inputs; call it and combine the results.

• Termination measure — prove that every call decreases a well-founded measure until a base case is reached. This need not be the raw numeric argument: a remaining interval or unvisited-node count can decrease. Graph cycles need visited state; merely following an edge is not a smaller-problem proof.

Python limits interpreter depth; inspect the configured value

sys.getrecursionlimit() reports a configurable limit, commonly 1,000 on CPython, not an exact number of recursive calls available to your function. Existing caller depth, wrappers and runtime version matter. Python does not generally eliminate tail recursion, but since CPython 3.11 most Python-to-Python calls do not consume another C-stack frame. Python frames/state and interpreter limits still exist; native extension calls can have different stack behaviour.

A normal depth-limit failure raises RecursionError. Raising the limit is platform-dependent and can cause a crash or excessive memory use; it does not fix nontermination. Do not assume universal frame counts for Java/C or that only a short list of languages can optimise tail calls. Prefer an iterative algorithm when depth can scale with untrusted input, and cap total work as well as depth.

Timeline — why recursion is everywhere

Lisp and ALGOL helped establish recursion as a programming technique; they did not invent the mathematical idea. Divide-and-conquer uses independent smaller inputs, while dynamic programming reuses overlapping states. The distinction between a recursive definition and the process it generates, associated with SICP teaching, is useful: a tail-form computation can use constant stack only if its implementation eliminates tail calls, or if we write a loop explicitly.

Python decorators can wrap a function with a cache, but lru_cache was added in Python 3.2, not with the first decorator syntax. React Fiber's explicit work representation is about scheduling retained continuations, not the introduction of Hooks. These are conceptual links, not unverified priority or textbook-publication dates.

Optional archived videos

Retained pointers: recursion intuition and the archived dynamic-programming video. The latter URL appeared twice under incompatible MIT and freeCodeCamp labels in the original; that attribution is unresolved, so neither label/duration is certified here. Playback is unverified. Use the worked code and official Python references as the governing material.

(b) From waiting calls to repeated subproblems · 15 min

The base case tells us when recursion stops; the call structure tells us what it costs. Factorial exposes the memory held by waiting calls. Fibonacci then shows how branching can repeat work even when every branch eventually stops.

factorial(4) — trace the call stack

Follow the calls until factorial(1) supplies the base-case value. Each earlier invocation is still waiting to multiply that answer by its own argument; the return-value nodes show those pending multiplications completing.

The first chain creates waiting frames; after the base case, the result chain shows them completing in reverse call order. Read the labels rather than the direction of the arrows: this layout draws both chains downward. The stack is at most O(n) deep — this is where memory dies for deep recursion.

Naive Fibonacci is EXPONENTIAL — see it

Factorial has only one smaller call at each step. Fibonacci branches into two, and the repeated labels below reveal a different cost: separate invocations solve the same smaller problem again.

Look at how many times fib(3) and fib(2) are recomputed. With T(0)=T(1)=1 and T(n)=1+T(n−1)+T(n−2), the exact total is T(n)=2F(n+1)−1. Thus fib(50) would make 40,730,022,147 calls—not 600 million. Compute that count from the recurrence; do not execute the huge naive example. The diagram shows only the upper levels, not every leaf. Memoisation stores completed results and reduces a cold single-threaded fib(n) run to O(n) arithmetic operations.

The two traces separate maximum stack depth from total calls. When recognising a recursive pattern, ask both how many children a call creates and whether different branches repeat the same input.

The four shapes of recursion

Linear recursion

Desc: One recursive call per invocation. factorial, list-length, linked-list reverse.

Binary / tree recursion

Desc: Two recursive calls per invocation. Naive Fibonacci, tree traversals, mergesort.

Mutual recursion

Desc: Function A calls B, B calls A. Common in parsers (expression/term/factor).

Recursive descent with backtracking

Desc: Explore a choice and undo branch-local shared mutation before the next choice, including after a successful counted branch. N-queens, sudoku and permutations illustrate this pattern.

Recursion vs iteration — pick your side

Name: Recursion wins

Tagline: The natural shape

• Tree / graph traversals

• Divide-and-conquer (mergesort, quicksort, FFT)

• Backtracking (permutations, N-queens)

• Grammar parsers

Name: Iteration wins

Tagline: The safe shape

• Very deep or unbounded recursion

• Linear scans (loops are just clearer)

• Hot performance paths (Python overhead per call)

• Anywhere you need pausable execution

Name: Memoisation wins

Tagline: The DP trick

• Overlapping subproblems (Fibonacci, edit distance)

• Pure function of its arguments

• @lru_cache can reuse deterministic results for hashable arguments; it does not solve cycles or unbounded state spaces

• Fibonacci: O(n) states with O(1) arithmetic operations per transition; other recurrences have their own state/transition costs

Name: Explicit stack wins

Tagline: The escape hatch

• Depth may exceed the available interpreter/runtime stack; no universal cross-language frame threshold

• Need to pause/resume/cancel work

• Explicit continuations; generators/coroutines are other ways to retain resumable state

• ‘Iterative DFS’ = recursion with your own stack

The debug trick that saves recursive functions

For a small nonnegative integer, print entry and exit around the recursive call. This complete trace makes the waiting multiplication visible without approaching the recursion limit:

def traced_factorial(n, depth=0):
    if type(n) is not int or n < 0:
        raise ValueError("n must be a nonnegative integer")
    print(f"{' ' * depth}enter factorial({n})")
    result = 1 if n <= 1 else n * traced_factorial(n - 1, depth + 1)
    print(f"{' ' * depth}exit factorial({n}) = {result}")
    return result
 
assert traced_factorial(4) == 24

Entry arguments are 4,3,2,1; exit values are 1,2,6,24. A small trace is diagnostic evidence, not a termination proof for arbitrary inputs.

An indented trace is useful for checking a small example; it does not mean the solution should depend on mentally replaying every call. The remaining question is what state must survive when a recursive function is rewritten as a loop.

Myth: "Recursion is just a prettier way to write a loop. Anything recursive can be rewritten as a loop, so it's a style choice."

Truth: a direct simulation can represent pending calls as explicit frames with a program counter and local state. That preserves the stack-shaped computation but moves its storage under your control. Tail recursion can often become a simple loop; some non-tail recurrences also admit a different constant-state algorithm. For example, ordinary recursive factorial can become an accumulator loop even though its multiplication happens after return. Do not claim that every equivalent algorithm must retain the same stack.

A bounded tail-form demonstration:

import sys
 
def countdown(n):
    if type(n) is not int:
        raise TypeError("n must be an integer")
    if n < 0:
        raise ValueError("n must be nonnegative")
    if n == 0:
        return "done"
    return countdown(n - 1)             # tail position, still Python recursion
 
print("configured recursion limit:", sys.getrecursionlimit())
assert countdown(5) == "done"
n = 5
while n:
    n -= 1
assert n == 0

Both versions terminate; the recursive one retains interpreter call state proportional to n, the loop constant scalar state. No test needs to raise the limit or deliberately approach a process-crashing depth.

Question: Why does naive recursive Fibonacci take exponential time, while the identical recurrence with memoisation takes linear time? The recurrence did not change — so what did?

For n ≥ 2, the naive definition branches into n−1 and n−2. Its exact call recurrence is T(n)=1+T(n−1)+T(n−2), not the full binary-tree node count 2ⁿ. Solving it gives Θ(φⁿ), where φ=(1+√5)/2; 2ⁿ is a loose upper bound.

A cold single-threaded fib_memo(n) with unbounded caching and n ≥ 2 reaches states 0..n. Each completed state is computed once and has at most two outgoing recurrence edges, so the total number of arithmetic operations is O(n). Cache lookups replace repeated evaluations; they do not eliminate the O(n) deepest first descent. Calls with n=0 or 1 reach only one state. Warm calls can be direct cache hits.

The general rule is number of reachable states plus work over their transitions, including key construction and arithmetic. Python Fibonacci integers grow to Θ(n) bits: computing all additions has Θ(n²) bit cost with ordinary linear-time addition, and storing all F(0)..F(n) requires Θ(n²) bits. O(n) here counts arithmetic operations and stored values, not bytes. A two-variable iterative Fibonacci avoids the whole cache and keeps only Θ(n) bits of big-integer state.

Memoisation helps when arguments represent repeated subproblems and results are safe to reuse. It does not turn every exponential algorithm polynomial: subset states can already be exponential. Nor does a cache detect a recursive cycle before a result is stored. Distinct nonoverlapping merge-sort subarrays usually give no useful reuse; hashing copied subarrays can add work. DP also includes bottom-up tabulation, not only decorated recursion.

Name: Trust the smaller self

Picture: Trace a small case to debug, but use induction rather than mentally expanding every call to prove the general case. Then: assume a working version of the function already exists for every smaller input, and your only job is to (a) handle the input so small there is nothing to do, and (b) combine the smaller answers into yours.If both parts are correct and every call strictly shrinks the input, the whole thing is correct by induction. The call stack explains resource use; a small hand trace can check the invariant, but it is not a proof for arbitrary inputs.

• Base case first, and make it the case where the answer is obvious — usually empty or size 1, not size 0-is-impossible.

• Every call must decrease a declared well-founded measure, or use another termination argument. Trace a small input when checking the measure and combine step.

• Prove the combine step assuming the smaller-call contract, then separately check base cases and termination.

• Depth costs memory. A logarithmic depth is often manageable, but existing stack depth, constants, total work and input size still need bounds. Linear depth on untrusted input deserves special attention.

Trigger: Fire this model the moment you see: a tree or nested JSON · a directory walk · a problem defined in terms of itself · "all permutations / combinations / subsets" · a parser · a DAG of task dependencies (Airflow) · a query plan · anything where the shape of the data is itself recursive.

Decision: The algorithm is naturally recursive. Ship the recursion, or convert it to an explicit-stack loop?

Name: Keep the recursion

Gain: the code mirrors the definition, so it is far easier to prove correct and to review; the base case and combine step are visible at a glance; less state to get wrong

Cost: interpreter depth is limited and pending calls retain state. In normal CPython use, hitting its recursion limit raises RecursionError; unsafe limit changes or native stack exhaustion can be more severe

Pick: depth is provably bounded and small — logarithmic depth (balanced trees, binary search, merge sort) or a schema you control

Name: Explicit stack + loop

Gain: an explicit stack avoids the interpreter recursion limit and exposes continuation state. Heap memory and total work are still bounded resources; enforce caps for adversarial inputs. Serialisation requires the retained objects/state to support it

Cost: you now hand-manage the "where was I" state, which is exactly the part the language was doing correctly for free; post-order traversals in particular become genuinely fiddly

Pick: depth can scale with input size and the input is untrusted — deeply nested JSON from an API, a linked structure, a skewed tree

Name: Recursion + raise the limit

Gain: one line, keeps the readable code

Cost: the safe setting is platform/runtime dependent; too high can crash or exhaust resources. CPython 3.11 changed Python-call evaluation, so interpreter depth and native C-stack depth must not be equated

Pick: you have measured the actual worst-case depth and are raising the limit to a specific justified number, never as a blind fix

Verdict: Default to recursion when depth is logarithmic, and to an explicit stack when depth can scale with untrusted input size. The failure mode that matters is the second one: recursive parsers over user-supplied nested data are a genuine denial-of-service surface, because the attacker chooses your depth.In data engineering specifically, the recursion you write is usually over a schema (bounded, yours) while the recursion you must harden is over data (unbounded, theirs). Sort your recursive code into those two buckets and the decision makes itself.

(c) Hands-on · 25 min

Save as recursion.py. Zero dependencies.

"""recursion.py — the interview canon for recursion + memoisation.
 
Run:  python recursion.py
"""
from __future__ import annotations
from functools import lru_cache
import time
import sys
 
 
# ------------------------------------------------------------------
# 1) Factorial — the ‘hello world’ of recursion
# ------------------------------------------------------------------
def _natural(n: int) -> None:
    if type(n) is not int:
        raise TypeError("n must be an integer, not bool")
    if n < 0:
        raise ValueError("n must be nonnegative")
 
 
def factorial(n: int) -> int:
    _natural(n)
    if n <= 1:                       # base case
        return 1
    return n * factorial(n - 1)      # recursive case, shrinks by 1
 
 
# ------------------------------------------------------------------
# 2) Fibonacci — naive vs memoised
# ------------------------------------------------------------------
def fib_naive(n: int) -> int:
    _natural(n)
    if n < 2:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)      # exponential — see it below
 
 
@lru_cache(maxsize=None, typed=True)
def fib_memo(n: int) -> int:
    _natural(n)
    if n < 2:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)         # O(n) arithmetic ops on a cold, single-threaded call
 
 
# ------------------------------------------------------------------
# 3) List sum — recursive is fine but iteration is clearer
# ------------------------------------------------------------------
def sum_list(a: list[int]) -> int:
    if not a:
        return 0
    return a[0] + sum_list(a[1:])                     # careful — a[1:] copies! O(n^2) memory
 
 
def sum_list_iter(a: list[int]) -> int:
    total = 0
    for x in a:
        total += x
    return total
 
 
# ------------------------------------------------------------------
# 4) Mergesort — the classic divide-and-conquer
# ------------------------------------------------------------------
def merge_sort(a: list[int]) -> list[int]:
    if len(a) <= 1:                                  # base case
        return a                                    # aliases input at length 0 or 1
    mid = len(a) // 2
    left = merge_sort(a[:mid])                       # recursive on smaller
    right = merge_sort(a[mid:])
    return _merge(left, right)
 
 
def _merge(left: list[int], right: list[int]) -> list[int]:
    out: list[int] = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:])
    out.extend(right[j:])
    return out
 
 
# ------------------------------------------------------------------
# 5) Binary tree — the recursive definition matches the code exactly
# ------------------------------------------------------------------
class TreeNode:
    __slots__ = ("val", "left", "right")
 
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
def tree_depth(root: TreeNode | None) -> int:
    if root is None:                                 # base case
        return 0
    return 1 + max(tree_depth(root.left), tree_depth(root.right))
 
 
def inorder(root: TreeNode | None) -> list:
    if root is None:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)
 
 
# ------------------------------------------------------------------
# 6) Iterative DFS on a tree — recursion with your own explicit stack
# ------------------------------------------------------------------
def inorder_iter(root: TreeNode | None) -> list:
    """Same inorder values, with O(height) explicit stack plus output; heap limits remain."""
    out, stack, node = [], [], root
    while node or stack:
        while node:                                  # descend the left spine
            stack.append(node)
            node = node.left
        node = stack.pop()
        out.append(node.val)
        node = node.right
    return out
 
 
# ------------------------------------------------------------------
# 7) The perf demo — see exponential vs linear
# ------------------------------------------------------------------
def perf_demo() -> None:
    n = 20                         # bounded demonstration, not a stress benchmark
    t = time.perf_counter(); fib_naive(n); dt_naive = time.perf_counter() - t
    fib_memo.cache_clear()
    t = time.perf_counter(); fib_memo(n); dt_memo = time.perf_counter() - t
    print(f"fib({n}) naive : {dt_naive*1000:.3f} ms")
    print(f"fib({n}) memo  : {dt_memo*1000:.4f} ms (timings vary)")
 
 
if __name__ == "__main__":
    print("factorial(5) :", factorial(5))
    print("sum_list([1..10]) :", sum_list(list(range(1, 11))))
    print("merge_sort([3,1,4,1,5,9,2,6]) :", merge_sort([3, 1, 4, 1, 5, 9, 2, 6]))
 
    # Build a small tree:   1
    #                      / \
    #                     2   3
    #                    / \
    #                   4   5
    root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
    print("tree_depth :", tree_depth(root))
    print("inorder recursive :", inorder(root))
    print("inorder iterative :", inorder_iter(root))
 
    perf_demo()
 
    # Inspect configuration; do not raise limits as a diagnostic experiment.
    print("configured recursion limit:", sys.getrecursionlimit())

Anatomy of the script

What each function teaches

Name: factorial

Desc: Nonnegative integer factorial; zero and one return 1, otherwise shrink by one. O(n) multiplications and interpreter depth; actual big-integer multiplication cost grows with the result. Negative and non-integer/bool inputs are rejected.

Name: fib_naive vs fib_memo

Desc: Same recurrence with and without caching. Naive call count is Θ(φⁿ); memoised cold state/transition count is O(n), still O(n) recursive depth. The bounded n=20 timing run is illustrative, not a fixed speedup claim.

Name: sum_list

Desc: Each a[1:] copies a suffix. Lengths n−1,n−2,… remain referenced by pending frames, yielding Θ(n²) peak live reference storage and copying work, plus O(n) depth. The iterative version uses O(1) scalar/reference state apart from growing integer values.

Name: merge_sort

Desc: The canonical divide-and-conquer: split in half, sort each half, merge. Recursion depth is O(log n). O(n log n) time, O(n) extra memory.

Name: tree_depth / inorder

Desc: On a finite proper binary tree, tree_depth visits n nodes in O(n) time and O(h) depth. Concatenating lists in inorder repeatedly copies results: Θ(n log n) on a balanced tree and Θ(n²) on a chain; its returned values are correct but it is not the linear-output-buffer implementation.

Name: inorder_iter

Desc: Each node is pushed/popped once and its value appended once: O(n) work, O(h) explicit stack and O(n) output references. It avoids the interpreter recursion limit, not all resource limits; a yield protocol would be needed to expose pausing to a caller.

Name: perf_demo

Desc: A bounded illustration of exponential calls versus linear cached-state count. Elapsed times also include cache, validation and interpreter overhead; they do not isolate function-call overhead or establish asymptotic complexity by themselves.

What to observe when you run it

ClassName: ml-4 list-decimal space-y-1

factorial(5) = 120. merge_sort output is sorted. tree_depth = 3. Recursive inorder and iterative inorder return identical lists — they're implementing the same algorithm, differently. The bounded demo computes fib(20)=6765. The naive function makes 21,891 calls; a cold memo run reaches 21 states. Timings vary, and caching does not remove its first-descent depth. Do not raise the limit to run larger examples.

Contracts, ownership and cache lifetime

All tree examples require a finite proper tree without cycles/shared child nodes. They do not detect cycles; a general graph needs visited-state semantics. Tree depth counts nodes on the longest root-to-leaf path (empty=0, leaf=1). Traversals leave structure intact and return new output lists whose elements still reference the original values.

sum_list and its loop version accept lists of integers and do not mutate them. merge_sort requires a total order compatible with <= (the annotated domain is integers); choosing the left element on ties makes merging stable. It never modifies the input. Its length-0/1 base case returns the same list object, while longer input yields a new outer list; it is not a deep copy. Live auxiliary list storage is O(n), depth O(log n), while total slicing/merging allocations across levels amount to O(n log n) references over the run.

The cache has maxsize=None, so it retains all argument/result references until cache_clear() or wrapper destruction. typed=True keeps the validated integer domain distinct from float/bool calls; it does not recursively type every nested component of arbitrary arguments. Arguments must be hashable. Reusing mutable returned objects would alias them across calls, so this Fibonacci cache stores immutable integers. Single-threaded “computed once per state” is not a concurrency guarantee: another thread may compute a not-yet-cached value concurrently. A bounded LRU may evict states; recomputation then depends on traversal and capacity.

Goal: Count nonempty downward paths in a binary tree that sum to a target — prefix counts with backtracking

Hint: A brute-force oracle starts at every node and enumerates its downward paths (O(n²) worst case). The implementation below instead does one DFS, keeping counts of ancestor prefixes only. Query before adding the current prefix to exclude empty paths, then undo before visiting a sibling. Expected O(n) hash-table work, O(h) live prefix keys and interpreter depth, for bounded-cost integer/hash operations.

def count_paths_with_sum(root: TreeNode | None, target: int) -> int:
    from collections import defaultdict
    counts = defaultdict(int)
    counts[0] = 1
 
    def dfs(node, running: int) -> int:
        if node is None:
            return 0
        running += node.val
        found = counts.get(running - target, 0)
        counts[running] += 1
        found += dfs(node.left, running) + dfs(node.right, running)
        counts[running] -= 1                          # undo before sibling branch
        if counts[running] == 0:
            del counts[running]                       # retain only active prefixes
        return found
 
    return dfs(root, 0)
 
sample = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
assert count_paths_with_sum(sample, 6) == 1             # path 2 -> 4
assert count_paths_with_sum(None, 6) == 0
assert count_paths_with_sum(TreeNode(0, TreeNode(0), TreeNode(0)), 0) == 5

Exercise answer: for the sample, the only downward sum-6 path is 2→4, not a nonexistent 1→2→3 chain. At node 4 the current prefix is 7; the ancestor prefix 1 is present, so 7−1=6 contributes one. After returning from a child, remove that child's contribution. On a root 0 with two zero leaves, there are five nonempty downward paths: three singletons and two root-to-leaf paths. Leaving a child's prefix in the table falsely counts paths crossing siblings. This is ancestor-frequency state, not cached answers to dfs(node) calls.

The takeaway: recursion + a mutable running state = backtracking. You must undo your mutation on the way back up.

(d) Production reality · 15 min

Untrusted nesting: bound depth and total work

Do not infer a universal JSON depth constant or a parser CVE from recursion alone. The earlier DEFAULT_JSON_LEVELS=200 claim is not a Python json contract, and a PyYAML unsafe-deserialisation advisory is not evidence for that claim. A service must bound input bytes before parsing and use parser-supported limits or a validated streaming design; a check performed only after parsing cannot protect the parse step.

A bounded explicit traversal can check an already constructed nested-list model without risking interpreter depth:

def validate_nested_lists(root, max_depth=8, max_items=100):
    if type(max_depth) is not int or type(max_items) is not int:
        raise TypeError("limits must be integers")
    if max_depth < 0 or max_items < 1:
        raise ValueError("depth >= 0 and items >= 1 required")
    pending = [(root, 0)]
    scheduled = 1
    while pending:
        value, depth = pending.pop()
        if depth > max_depth:
            raise ValueError("nesting limit exceeded")
        if isinstance(value, list):
            if scheduled + len(value) > max_items:
                raise ValueError("work limit exceeded")
            scheduled += len(value)
            pending.extend((child, depth + 1) for child in value)
    return scheduled
 
assert validate_nested_lists([1, [2]]) == 4

The root is depth zero and counts as one item; every child reference counts, including repeated aliases. Cycles eventually hit a work/depth bound rather than receiving graph semantics. Checking the child count before extending pending prevents one wide node from allocating an unbounded frontier inside this model. This is not a JSON parser or a full secure-input boundary.

Explicit continuations and cooperative scheduling

A synchronous recursive tree walk does not voluntarily return control until a call returns. To interleave work, retain a continuation: node, stage and any pending result. inorder_iter retains nodes waiting for their left child, then moves to the right child after output. A scheduler can process a bounded number of steps and retain this state between turns; a recursive generator can also suspend, so recursion is not inherently unpausable. Fiber's architecture notes describe virtual stack frames for React work. That conceptual comparison is not a claim that our loop implements Fiber or that Hooks introduced it.

Diagnose shape, not just node count

A balanced tree with 1,200 nodes has small height; a chain with 1,200 nodes has height 1,200. Total nodes alone do not predict recursion failure. Test the empty tree, a branching tree and a modest chain; separately measure maximum active depth and total visits. For untrusted shape, use an iterative traversal with node/depth/work caps. Raising sys.setrecursionlimit can change where failure occurs but does not make an unbounded input safe.

Where this shows up in the rest of the plan

Root: Recursion is the substrate of much of DSA

Label: S028 · Trees & BSTs

Desc: Recursive tree definitions naturally express traversal and height; iterative algorithms are also valid, especially for unbounded height.

Label: S030 · Graphs (DFS)

Desc: DFS can be recursive or iterative; an exact continuation-stack simulation preserves recursive traversal order, while eager neighbour pushes can choose a different DFS tree.

Label: S031 · Sorting (mergesort/quicksort)

Desc: Merge sort has O(n log n) comparison work; ordinary quicksort has expected O(n log n) under appropriate pivot assumptions but O(n²) worst case.

Label: S033 · Dynamic Programming

Desc: DP reuses state results through top-down memoisation or bottom-up tabulation. State count and transition cost determine complexity, not the presence of a decorator.

Label: S034 · Backtracking

Desc: Recursion with an undo step. N-queens, sudoku, permutations.

Label: Compilers and parsers

Desc: Recursive descent is one parser design; table-driven and other parsing algorithms are alternatives. The useful link is retained grammar/continuation state, not a universal implementation claim.

(e) Recall + stretch · 10 min

Self-check (answer follows each question).

Recall — click to reveal

Q: State the three ingredients of every correct recursion.

A: A base case, a recursive reduction/combine step, and a well-founded termination measure. The measure need not be the raw numeric argument; for cyclic graphs, visited-state handling must supply a real termination argument.

Q: Why is naive Fibonacci O(2^n)?

A: The exact Fibonacci call count follows a Fibonacci-like recurrence and grows Θ(φⁿ), where φ≈1.618. O(2ⁿ) is a convenient valid upper bound, not a tight leaf count.

Q: How does @lru_cache turn fib from O(2^n) into O(n)?

A: For a cold single-threaded call with n ≥ 2 and an unbounded cache, the n+1 states 0..n are computed once, each with at most two transitions. That gives O(n) arithmetic operations and O(n) stored values/depth; growing Fibonacci integers make total bit storage and addition cost Θ(n²). For n=0 or 1, only that base state is reached. Other recurrences need their own state/transition analysis.

Q: Why does Python crash at ~1000 levels of recursion?

A: The interpreter enforces a configurable recursion limit, inspectable with sys.getrecursionlimit; crossing it normally raises RecursionError. The available depth depends on surrounding calls and wrappers. CPython 3.11+ generally avoids a new C evaluator call for Python-to-Python calls, so Python depth is not one-for-one C-stack usage. Raising the limit remains platform-dependent and potentially unsafe; bound inputs or rewrite iteratively.

Q: What is tail-call optimisation, and why does Python NOT implement it?

A: Tail-call elimination reuses/replaces a continuation when no work remains after the call, avoiding stack growth for such calls. Python does not promise this optimisation, so do not rely on tail-form recursion for constant space. Preserving ordinary traceback/calling behaviour is one design concern; the reliable engineering rule is to write a loop when constant interpreter depth is required.

Q: Give one example where recursion is the WRONG choice.

A: Summing a huge list, or walking an unbounded stream of events, or any long linear scan. Iteration is clearer here, avoids the interpreter recursion limit, and avoids a recursive call per item; memory and total-work limits still apply. Or: reversing a linked list with millions of nodes.

Q: What's the connection between recursion and a stack?

A: The call stack IS a stack — each recursive call pushes a frame; each return pops one. ‘Iterative rewrite with an explicit stack’ literally means moving that stack from the runtime into your code.

Q: In backtracking, why must you ‘undo’ mutations on the way back up?

A: You may be exploring many branches from the same node. Any state you mutated for one branch must be restored before you try the next branch, or the branches contaminate each other.

Q: You have a recursive function that occasionally crashes with RecursionError. Two-step diagnosis?

A: First verify base cases and a decreasing termination measure on bounded inputs. Then inspect maximum active depth and input shape; correct nontermination, bound valid depth, or use an iterative algorithm. Do not raise limits just to discover whether the function terminates.

Q: Stretch — write mergesort iteratively (bottom-up). What's the advantage?

A: Merge adjacent sorted runs of widths 1,2,4,…, clipping the final partial run. This removes recursive depth while preserving stable O(n log n) comparison work and O(n) live auxiliary storage. The code below returns a new shallow list even at length 0/1; the recursive version aliases its base-case list. Do not equate this fixed-width algorithm with every production sort: TimSort detects natural runs and has additional policies.

Bottom-up merge sort: a complete answer

def merge_sort_bottom_up(a):
    out = list(a)                        # fresh outer list, shallow elements
    width = 1
    while width < len(out):
        for lo in range(0, len(out), 2 * width):
            mid = min(lo + width, len(out))
            hi = min(lo + 2 * width, len(out))
            out[lo:hi] = _merge(out[lo:mid], out[mid:hi])
        width *= 2
    return out
 
assert merge_sort_bottom_up([3, 1, 4, 1, 5]) == [1, 1, 3, 4, 5]

At the start of a width-w pass, each aligned run of at most w values is sorted. _merge creates sorted stable runs of at most 2w; the final incomplete run is clipped, not dropped. After doubling past n, the whole array is one sorted run. Unlike a prompt to “write it yourself,” this includes the boundary handling to check on an odd length.

Explain-out-loud test

Teach these three, one minute each, no notes:

1. What are the three parts of a correct recursion, and what breaks if any is missing?
2. Why does memoisation turn Fibonacci from exponential to linear?
3. Give one real-world case where recursion is the RIGHT tool and one where it's the WRONG tool.

Explain-out-loud answer guide

1. Factorial handles 0/1, reduces n to n−1 and multiplies the smaller answer. Its measure is the nonnegative integer n; failing to decrease it can repeat forever, while an incorrect combine step can terminate with the wrong value.
2. Fibonacci's repeated states form a DAG; caching completed states reduces exponential calls to linear state/transition count, not constant depth or constant-cost big integers.
3. Bounded-height tree traversal fits recursion. Summing a long list or accepting arbitrarily nested input calls for an iterative algorithm plus explicit resource bounds, not an automatic recursion-limit increase.

What comes next

Next: S028 · Trees & BSTs — Traversal (BFS/DFS)

Hub: The 6-Month Learning Plan

Part of a 130-session evergreen learning series. Session structure: intuition → visual → hands-on → production war stories → recall. Duration: 90 minutes.

Corrective source notes

• Python 3.14 sys — configurable interpreter depth and platform-dependent crash risk.
• CPython 3.11 inlined Python calls — why Python and C-stack frames are not interchangeable counts.
• Python 3.14 functools — hashable arguments, unbounded-cache lifetime and concurrency caveats.
• Fiber architecture notes — conceptual explicit-continuation/scheduling connection, not a reproduced React runtime.
• Python 3.14 interpreter note — internal tail calls do not implement Python-function tail-call optimisation.
• Python json — input-resource warnings and implementation limits; CVE-2020-14343 describes PyYAML unsafe deserialisation, not a JSON depth constant.

Sources checked 2026-10-10. Fibonacci counts and complexity are derived from the displayed recurrences; tests are bounded, not depth-stress or production-parser certification.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.