Recursion & the Call Stack

Review boundary and corrected contracts

Recursion needs a well-founded decreasing measure, not a fixed numerical depth folklore. Python has a configurable recursion limit; these small examples do not establish safety for input-sized recursion. Factorial/Fibonacci accept nonnegative integers; arithmetic cost grows with result bit length.

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: Stop treating recursion as spooky: see it as a function that calls itself on a smaller problem, trust the recursive leap, write bulletproof base cases, hand-trace the call stack, and know exactly when recursion is the wrong tool.

Series: LeetCode — From Basics to Production-Ready · Session 21 / 65 · Phase 1 · Core patterns

Prerequisites

What you need first

You need the stack from L16 — recursion runs on a stack, and understanding that makes everything here concrete rather than mystical. Nothing else. This is the substrate for every remaining phase: trees (L22+), backtracking (L31+), and dynamic programming (L33+) are all recursion with structure added, so time spent here pays compound interest.

Optional original companions: Recursion in 5 minutes — freeCodeCamp for base cases; Call stack visualised — Reducible for pending frames; Recursion tree and complexity — take U forward for counting calls.

What this pattern IS

Recursion is a function that solves a problem by calling itself on a smaller version of the same problem, until the problem is small enough to answer directly. That's it. Two parts, always: the base case (the smallest input, answered without recursing) and the recursive case (reduce the problem, call yourself, combine). Without a reachable base case, this recursive process does not terminate mathematically. Python normally raises RecursionError at its configured recursion limit; a crash is not the same thing as that catchable exception.

The hard part isn't writing the recursive call — it's trusting it. The recursive leap of faith is the discipline of assuming your function already works correctly on the smaller input, using that result, and not mentally unrolling the whole thing. If factorial(n) should return n * factorial(n-1), you assume factorial(n-1) is correct and move on. Trying to trace every level in your head is what makes recursion feel impossible; refusing to is what makes it easy. You prove correctness the way you'd prove induction: base case holds, and if the smaller case is right, the combination is right.

Under the hood, each call gets a stack frame holding its local variables and where to return. Calls push frames as they go deeper; returns pop them as they come back. With bounded-size frame state, call-frame overhead is O(depth); large locals and copied slices can add more. Python exposes the configured limit through sys.getrecursionlimit(). Available depth also depends on already-active calls and wrappers: do not treat a folklore number as an input-size guarantee or raise the limit as a routine fix.

Russian nesting dolls

Real: To count the dolls, you open one, and to count what's inside you do the exact same thing — open and count — until you reach the tiny solid doll that doesn't open (the base case). You don't need to see all the dolls at once; you trust that 'count the inside' works, and add one.

def count(doll): return 1 if doll.solid else 1 + count(doll.inside)

Deriving correct recursion

Question: What guarantees a recursive function terminates and returns the right answer?

Premise: Every recursive call must move strictly toward the base case.

Because: a well-founded measure must decrease, such as the number of unprocessed elements. The entire input object need not get smaller: an index can advance toward its end. A decreasing real-valued quantity alone is not enough, since it may approach zero forever without reaching it.

Premise: The base case must handle the smallest input directly and correctly.

Because: it's the anchor the whole induction rests on; a wrong base case corrupts every level above it.

Premise: Assuming the recursive call is correct on the smaller input, the combine step must produce the correct answer for the current input.

Because: this is the inductive step — correctness propagates upward only if the combination is right.

Premise: Termination + correct base + correct combine => correct for all inputs, by induction on input size.

Because: the base case anchors induction, and the combine step proves the next case once the well-founded decreasing measure establishes termination.

Premise: The call stack depth equals the longest chain of un-returned calls.

Because: each pending call holds a frame; O(depth) measures frame overhead only when each frame retains O(1)-size state. Copied data and memo tables require separate accounting.

Conclusion: Recipe: (1) name the base case and answer it directly; (2) shrink the input; (3) assume the recursive call works and combine. Correctness is induction; the depth is your space bill.

The templates — annotated Python

# ---- Template A: the universal recursion shape --------------
def solve(problem):
    if is_base_case(problem):          # 1. the anchor
        return base_answer(problem)
    smaller = reduce(problem)          # 2. move toward the base
    sub = solve(smaller)               # 3. LEAP OF FAITH: trust it
    return combine(problem, sub)       # 4. build the answer
 
 
# ---- Template B: concrete example — factorial ---------------
def factorial(n: int) -> int:
    if n <= 1:                          # base: 0! = 1! = 1
        return 1
    return n * factorial(n - 1)         # trust factorial(n-1)
 
 
# ---- Template C: two recursive calls (branching) ------------
def fib(n: int) -> int:
    if n < 2:                          # base: fib(0)=0, fib(1)=1
        return n
    return fib(n - 1) + fib(n - 2)      # two leaps; combine by +
# WARNING: this is O(2^n) — it recomputes the same subproblems.
# Memoise (L33) to make it O(n): cache results by n.
 
 
# ---- Template D: memoised (top-down DP preview) -------------
from functools import lru_cache
 
@lru_cache(maxsize=None)               # cache every (n) -> result
def fib_fast(n: int) -> int:
    if n < 2:
        return n
    return fib_fast(n - 1) + fib_fast(n - 2)   # each n computed once => O(n)
 
 
# ---- Template E: recursion -> iteration with an explicit stack
def factorial_iter(n: int) -> int:
    result = 1
    stack = list(range(2, n + 1))      # the frames we'd have pushed
    while stack:
        result *= stack.pop()          # unwind by hand
    return result
# Any recursion can be rewritten with an explicit stack — do this
# when depth might exceed the configured recursion limit.

Template E deliberately stores O(n) integers to illustrate an explicit stack; factorial itself can instead multiply over range(2, n + 1) with a constant number of accumulator variables. Memoised Fibonacci stores O(n) values and has O(n) first-call depth; caching removes repeated work, not that depth. These operation counts do not make growing Python integers constant-size.

The single most common bug is a base case that's missing or wrong for an edge input — an empty list, n == 0, a leaf node. Write the base case first, before the recursive case, every time. The second most common is a recursive call that doesn't actually shrink the input (passing the same list, forgetting to slice), which loops until overflow. And the branching template (C) is a trap: naive fib is exponential because it recomputes subproblems — that observation is the entire seed of dynamic programming, which we'll grow in L33.

Name: The stack of unfinished promises

Picture: Each call is a promise 'I'll return once my sub-call returns'. Promises pile up (the stack grows) as you go deeper, then get fulfilled bottom-up (the stack unwinds) as the base case resolves and answers bubble back up. The deepest pile is your memory cost.

• Write the base case FIRST — it's the anchor.

• Every recursive call must decrease a well-founded measure toward a base case; the physical input object need not shrink.

• Take the leap: assume the recursive call is correct, then combine.

• O(depth) frame overhead assumes bounded frame state; check the configured recursion limit and count retained data separately.

Trigger: 'Same problem on a smaller part' — trees, nested structure, 'try all choices', divide-and-conquer, or a definition that refers to itself.

Memory / mnemonic

The recall peg is "BRC" — Base case, Reduce, Combine — recited in that order because that is the order you should write the three parts. Base case first (so you never forget the anchor), then how you shrink, then how you glue the sub-answer back. If you can say "B-R-C" you have the skeleton of every recursive function.

For the mindset, memorise the phrase "trust the leap." When you're mid-write and the recursion starts to feel dizzying, that dizziness is you trying to unroll it — stop, and trust that the smaller call already works. And keep the induction slogan handy: "base holds, small⇒big holds." Those two clauses are a full correctness proof, and reciting them stops you from hand-tracing five levels deep and losing the thread.

Myth: Recursion is elegant and therefore the right choice whenever a problem can be phrased recursively.

Truth: Recursion adds call frames and can reach the configured recursion limit. For potentially deep lists or skewed trees, iteration avoids that limit. Branching by itself does not guarantee shallow depth, and an explicit stack still consumes memory.

Why: Tiny examples hide input-sized depth. With a recursion limit below the needed depth, a 100000-node recursive reversal raises RecursionError; iterative reversal needs only a constant number of node references.

Trace safely instead of provoking a deep failure: factorial(3) suspends 3 * factorial(2), which suspends 2 * factorial(1). The base returns 1; the pending calls then return 2 and 6. Three active calls at the deepest point, not three simultaneous completed answers. An iterative accumulator reaches the same result without recursive calls.

What reviewers actually ask

Pure recursion is rarely the whole question — it's the substrate a reviewer builds on. But they do probe base-case discipline, the leap of faith, complexity of a recursion tree, and whether you know when to convert to iteration.

• Fibonacci Number (509) · Easy · Practice selection. · probes: naive O(2^n) vs memoised O(n) vs iterative O(1) space · follow-up: the seed of dynamic programming (L33).
• Pow(x, n) (50) · Medium · Practice selection. · probes: fast exponentiation by halving — recursion that shrinks the problem by 2x each step · follow-up: handle negative n and overflow.
• Merge Two Sorted Lists (21) · Easy · Practice selection. · probes: the recursive formulation vs iterative (from L19) · follow-up: merge k lists via divide-and-conquer recursion.
• Reverse Linked List (206) · Easy · Practice selection. · probes: the recursive reversal and its base case · follow-up: why iterative is preferred for long lists (stack depth).
• Maximum Depth of Binary Tree (104) · Easy · Practice selection. · probes: the canonical "recurse on children, combine with 1 +" shape · follow-up: do it iteratively with a stack (the L22 bridge).
• Sort List (148) · Medium · Practice selection. · probes: merge sort as divide-and-conquer recursion on a linked list · follow-up: O(1) space bottom-up merge sort.

Worked solutions

1. Pow(x, n) (50)

Plain words: compute x to the power n efficiently. Brute force multiplies x by itself n times — O(n). For nonnegative integer m, x^m = (x^(m//2))^2 when m is even, and needs one additional factor of x when m is odd. Each step halves m, giving O(log(m + 1)) multiplications. For negative n, invert x first; x must be nonzero.

def myPow(x: float, n: int) -> float:
    if n < 0:                          # x^-n = (1/x)^n
        x, n = 1 / x, -n
    def go(x: float, n: int) -> float:
        if n == 0:                     # base: anything^0 = 1
            return 1.0
        half = go(x, n // 2)           # trust it: x^(n//2)
        if n % 2 == 0:
            return half * half         # even: square it
        return half * half * x         # odd: square and one more x
    return go(x, n)

Complexity: O(log(|n| + 1)) multiplications and call frames, with constant work for n = 0. Floating-point rounding, overflow, and underflow are not eliminated by reducing the multiplication count. The base case n == 0 is the anchor; computing half once and squaring — not calling go twice — is what keeps it logarithmic rather than linear. Follow-up: negative n is handled up front by inverting.

2. Maximum Depth of Binary Tree (104)

Plain words: the depth is the longest root-to-leaf path length. This is the archetypal recursive shape — the depth of a tree is 1 plus the deeper of its two subtrees' depths.

def maxDepth(root) -> int:
    if not root:                       # base: empty tree has depth 0
        return 0
    left = maxDepth(root.left)         # trust: depth of left subtree
    right = maxDepth(root.right)       # trust: depth of right subtree
    return 1 + max(left, right)        # combine: this node + deeper side

Complexity: O(n) time (visit each node once), O(h) space where h is the tree height (the recursion depth) — O(n) for a degenerate list-like tree, O(log n) for a balanced one. This is the BRC template in its purest form and the doorway to all tree DFS in L22.

Goal: Compute the tree's diameter (longest path between any two nodes)

Hint: At each node, the longest path THROUGH it is left-depth + right-depth; track a global max while returning the depth.

Extend maxDepth so it also computes the diameter — the number of edges on the longest path between any two nodes, which need not pass through the root. The trick is the return-vs-update split: each call returns its own depth but updates a shared max with left+right. This split is the single most important idea for L22–L26 tree problems.

3. Reverse Linked List — recursively (206)

Plain words: reverse a list using the leap of faith. Assume the rest of the list is already reversed; then make the current node the new tail of that reversed rest.

def reverseList(head):
    if not head or not head.next:      # base: empty or single node
        return head
    new_head = reverseList(head.next)  # trust: rest is reversed
    head.next.next = head              # the next node now points back to us
    head.next = None                   # sever our old forward link
    return new_head                    # the deepest node is the new head

Complexity: O(n) time, O(n) space — and that space is the catch. Each node adds a call frame, so a list whose depth exceeds the configured limit raises RecursionError. This is exactly why L19 taught the iterative version first: on a long linear structure, iteration is the safe default and recursion is the elegant-but-dangerous alternative.

When NOT to use recursion

Decision: Recursion versus iteration versus recursion-with-an-explicit-stack.

Name: Plain recursion

Gain: Clean, matches recursive structure (trees, divide-and-conquer); minimal code.

Cost: O(depth) call-frame overhead for bounded local state; configured recursion limit; per-call overhead.

Pick: Branching/recursive structure with shallow depth — trees, backtracking, divide-and-conquer.

Name: Iteration (a loop)

Gain: O(1) call-frame overhead and no recursion-depth failure; any explicit stack, accumulator, and input data still consume memory.

Cost: Awkward for genuinely branching structure; you may hand-roll a stack anyway.

Pick: Linear problems with large depth — long lists, big n, streaming.

Name: Recursion + explicit stack

Gain: Keeps the recursive logic but moves frames to the heap, dodging the recursion limit.

Cost: More verbose; you manage the stack manually.

Pick: Tree/graph traversal whose depth may approach or exceed the configured recursion limit.

Verdict: Recurse when the structure branches and depth is bounded (trees). Loop when the problem is linear and deep (lists, large n). When you need recursion's logic but fear the depth limit, convert to an explicit heap-allocated stack — same traversal logic without recursive-call depth limits, but still bounded by available memory.

Where this shows up in production

A stack trace records active calls, which makes the pending-call model useful for debugging Python. Recursive-descent parsers mirror grammar structure; recursive mergesort divides input and combines sorted halves. File-system walks, UI trees, and expression evaluators can be implemented recursively or with explicit work stacks: nested data does not prove a particular library uses recursive Python calls. Choose based on the maximum depth and retained state, not the visual shape alone.

You can now…

• Write any recursion as base-case-first, reduce, combine (BRC).

• Apply the leap of faith instead of hand-tracing every level.

• Prove a recursion correct by induction (base holds, small⇒big holds).

• Explain why naive fib is O(2^n) and how memoisation makes it O(n).

• Account for O(depth) call-frame overhead plus retained data, and check Python's configured recursion limit.

• Use fast exponentiation (halving) for O(log n) recursion.

• Convert a recursion to an explicit-stack iteration when depth is dangerous.

Self-check (answer follows each question).

Recall · L21

Q: What are the two mandatory parts of any recursion?

A: A base case (smallest input, answered directly) and a recursive case that shrinks the input toward the base and combines the sub-result.

Q: What is the recursive leap of faith?

A: Assuming the recursive call already works correctly on the smaller input, and combining that result — rather than mentally unrolling every level.

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

A: Each call branches to n−1 and n−2, not to half-sized inputs. The call-count recurrence T(n)=T(n−1)+T(n−2)+O(1) is Θ(φ^n), hence O(2^n). Memoisation computes O(n) states and O(n) additions; for Python big integers, addition cost grows with the result length.

Q: What is the space cost of recursion and what limits it in Python?

A: O(depth) call-frame overhead for bounded-size local state, plus separately retained data. Python raises RecursionError when its configured recursion limit is exceeded; inspect sys.getrecursionlimit() rather than assuming a universal threshold.

Q: How does Pow(x,n) get to O(log n)?

A: For nonnegative m, compute half = x^(m//2) once. Return halfhalf for even m and halfhalf*x for odd m. For negative n use the reciprocal base and m=|n|, requiring nonzero x. This gives O(log(|n|+1)) multiplications, with constant work at zero.

Q: In the tree-diameter extension, why 'return depth but update a global max'?

A: Each node must RETURN a single value (its depth) so its parent can use it, but the longest path THROUGH the node (left+right) isn't what the parent needs — so you record it separately in a shared max. This return-vs-update split recurs across all hard tree problems.

Stretch: true

Practice queue

• Fibonacci Number (509) — the base case + memo; anchor +7d.

• Maximum Depth of Binary Tree (104) — the BRC shape; anchor +7d.

• Pow(x, n) (50) — halving recursion.

• Reverse Linked List (206) — recursive vs iterative depth.

• Merge Two Sorted Lists (21) — recursive merge.

• Sort List (148) — divide-and-conquer; anchor +21d.

• K-th Symbol in Grammar (779) — pure recursive structure; hardest here.

• Recursion = self-call on a smaller problem; two parts: base case and recursive case.

• Write it BRC: Base case first, Reduce the input, Combine the sub-result.

• Take the leap of faith — trust the smaller call; correctness is induction.

• Call-frame overhead is O(depth), plus retained data; iterate when depth is not safely bounded below the configured recursion limit.

• Naive branching recursion (fib) is exponential; memoising is the seed of DP.

• Fast exponentiation halves the problem for O(log n); explicit stacks dodge the depth limit.

Corrective source notes

• Introduction to Dynamic Programming - Algorithms for Competitive Programming — Memoization stores subproblem results so repeated states need not be recomputed. Checked 2026-10-07.

• Recursion limits (CPython v3.14.0) — the configured limit is inspectable; raising it too far can crash the process. Rechecked 2026-10-09.

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.