L21 · Recursion & the Call Stack

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

Prerequisites

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). Miss the base case and you recurse forever; the machine runs out of stack and crashes — a stack overflow, named after the very structure recursion runs on.

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. That's why recursion depth costs real memory (O(depth)) and why Python caps recursion at ~1000 frames by default — a limit that turns some naturally-recursive problems into "convert to iteration" problems.

Deriving correct recursion

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 Python's ~1000-frame limit.

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.

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.

What interviewers actually ask

Pure recursion is rarely the whole question — it's the substrate the interviewer 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 · Amazon · 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 · Amazon, Meta, Google · 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 · Amazon, Microsoft · probes: the recursive formulation vs iterative (from L19) · follow-up: merge k lists via divide-and-conquer recursion.
• Reverse Linked List (206) · Easy · Amazon, Microsoft, Meta · 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 · Amazon, LinkedIn · 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 · Amazon, Meta · 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). Insight: x^n = (x^(n/2))^2, so each step halves the exponent — O(log n) via recursion that shrinks the problem by 2x.

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) time (exponent halves each level), O(log n) space (recursion depth). 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.

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 stack frame, so a list of 100000 nodes overflows Python's recursion limit. 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

Where this shows up in production

The call stack is not an abstraction — it's the mechanism every language uses to run functions, which is why a stack trace exists and why infinite recursion produces a RecursionError / stack overflow (the site Stack Overflow is named after it). Recursive descent parsers (used in real compilers and JSON/config readers) are recursion mirroring grammar structure. Quicksort and mergesort are divide-and-conquer recursion. File-system traversal (os.walk), rendering nested UI component trees, and evaluating nested expressions are all recursion on tree structure. The honest framing: recursion is natural wherever data is nested, and dangerous wherever data is deep-and-linear — the same trade this session drills.

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.