Recursion Mechanics

Recursion is not magic. It is a function that calls itself with a smaller input, plus a contract that says: “when the input is trivial, return a known answer directly.” Everything else — trees, DFS, backtracking, divide-and-conquer, dynamic programming — is built on top of this single idea. If you make the call stack concrete and visible in your mind, none of it will feel mysterious again.

---

1. The Call Stack Mental Model

When a function calls itself, the runtime pushes a new stack frame onto the call stack. Each frame has its own local variables, its own parameters, and a return address pointing to where execution should resume when the frame finishes.

Let’s make this concrete with factorial(5).

factorial(n):
  if n == 0: return 1          // base case
  return n * factorial(n - 1)  // recursive case

Here is exactly what happens, frame by frame:

CALL STACK (grows downward as calls are made)

[factorial(5)] — waiting for factorial(4) to return
  [factorial(4)] — waiting for factorial(3) to return
    [factorial(3)] — waiting for factorial(2) to return
      [factorial(2)] — waiting for factorial(1) to return
        [factorial(1)] — waiting for factorial(0) to return
          [factorial(0)] — hits base case, returns 1
        [factorial(1)] — receives 1, computes 1*1=1, returns 1
      [factorial(2)] — receives 1, computes 2*1=2, returns 2
    [factorial(3)] — receives 2, computes 3*2=6, returns 6
  [factorial(4)] — receives 6, computes 4*6=24, returns 24
[factorial(5)] — receives 24, computes 5*24=120, returns 120

Two phases happen here. The winding phase: calls pile up on the stack, each waiting. The unwinding phase: base case triggers, frames pop off in reverse order, each one computing its result from the value returned by the frame below it.

What most people get wrong: They try to trace the entire winding and unwinding mentally for every problem. This works for factorial(3). It collapses at factorial(10) or any tree with depth > 4. The fix is the recursive leap of faith (Section 3).

---

2. Base Case and Recursive Case: How to Always Identify Them

Every correct recursive function has exactly two components:

Base case: The smallest version of the problem where you can return an answer without another recursive call. This is the “exit ramp.” Without it, you get infinite recursion and a stack overflow.

Recursive case: The general case, where you reduce the problem to a smaller version of itself and make a recursive call.

Framework for identifying them:

1. Ask: “What is the smallest input where the answer is obvious?” — that’s your base case.

2. Ask: “How can I express the answer for input n in terms of the same function called on something smaller than n?” — that’s your recursive case.

Example: Count nodes in a binary tree.

• Smallest input where answer is obvious: null node → 0 nodes.

• Answer for any other node: 1 + count(left child) + count(right child).

int countNodes(TreeNode node) {
    if (node == null) return 0;             // base case
    return 1 + countNodes(node.left)        // recursive case
             + countNodes(node.right);
}

---

3. The Recursive Leap of Faith

This is the single most important mental shift in all of recursion. It was formalized in Brian Harvey’s Computer Science Logo Style (MIT Press, 1997) and independently described in How to Think Like a Computer Scientist (Downey). The idea:

Assume your function already works correctly for all inputs smaller than the current one. Then just write what needs to happen for the current input.

You are not supposed to trace the recursion. You are supposed to trust the contract and write the combining logic.

Applied to tree height:

Step 1: Define the contract. height(node) returns the height of the subtree rooted at node.

Step 2: Invoke the leap of faith. Assume height(node.left) and height(node.right) already return the correct heights of the left and right subtrees.

Step 3: Write the combining logic. If I have the heights of both subtrees, the height of the current node is 1 + max(leftHeight, rightHeight).

Step 4: Handle the base case. If node == null, height is 0.

int height(TreeNode node) {
    if (node == null) return 0;
    int leftHeight = height(node.left);   // trust this
    int rightHeight = height(node.right); // trust this
    return 1 + Math.max(leftHeight, rightHeight);
}

Why this works: Mathematical induction. You prove it holds for the base case, then prove that if it holds for n-1, it holds for n. The recursive call IS the inductive step. You don’t need to simulate it — you need to trust it.

The two caveats that most explanations skip:

1. The argument to the recursive call must be strictly smaller than the current argument (closer to the base case).

2. Every execution path must either reach the base case or make a recursive call with a smaller argument.

---

4. Tail Recursion vs. Non-Tail Recursion

Tail recursion: The recursive call is the last operation in the function. No computation happens after it returns.

// Tail recursive factorial (accumulator pattern)
int factTail(int n, int acc) {
    if (n == 0) return acc;
    return factTail(n - 1, n * acc);  // last operation
}

Non-tail recursion: Something happens after the recursive call returns (combining step).

// Non-tail recursive factorial
int fact(int n) {
    if (n == 0) return 1;
    return n * fact(n - 1);  // multiplication happens AFTER the call
}

Why it matters: Tail-recursive calls can be optimized by the compiler/runtime into a loop (tail-call optimization, TCO), eliminating stack frame accumulation. Java does NOT implement TCO. C++ and C also do not guarantee it. This means deep non-tail recursion in Java/C/C++ can cause StackOverflowError on inputs of depth ~10,000+.

Practical rule: For most LeetCode problems, the input size is bounded (tree depth ≤ 10,000, array length ≤ 10^5), and recursive depth ≤ input size. Stack overflow is a real concern for linear recursion on large inputs. For trees with reasonable depth (≤ 1,000), you are fine.

---

5. Common Recursion Patterns

Linear recursion: One recursive call per invocation. Processes a list or array by removing one element at a time. O(n) time, O(n) space (call stack).

int sumArray(int[] arr, int i) {
    if (i == arr.length) return 0;
    return arr[i] + sumArray(arr, i + 1);
}

Tree recursion: Two or more recursive calls per invocation. Branches like a tree. Fibonacci is the textbook example — O(2^n) calls without memoization.

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);  // two calls = tree recursion
}

Mutual recursion: Function A calls B, B calls A. Used in parsers, grammars, and some state machines. Rarely tested directly in LeetCode but appears in compiler-related problems.

Accumulator pattern (tail-recursive style): Thread an accumulator parameter through recursive calls to avoid the combining step on unwind.

---

6. Memoization: The Bridge to Dynamic Programming

Tree recursion recomputes subproblems. fib(5) calls fib(4) and fib(3). fib(4) also calls fib(3). fib(3) is computed twice. For fib(40), this becomes catastrophically wasteful.

Memoization: Cache the result the first time you compute it. Return the cached result on subsequent calls.

Map<Integer, Integer> memo = new HashMap<>();

int fib(int n) {
    if (n <= 1) return n;
    if (memo.containsKey(n)) return memo.get(n);  // cache hit
    int result = fib(n - 1) + fib(n - 2);
    memo.put(n, result);                           // cache write
    return result;
}

Time complexity goes from O(2^n) to O(n). This is the entry point to dynamic programming — DP is just memoized recursion (top-down) or the iterative equivalent (bottom-up). Phase 5 will make this concrete.

---

7. Common Mistakes

Mistake	Symptom	Fix
Missing base case	StackOverflowError or infinite loop	Ask: “What is the smallest input?” first
Not reducing the problem	Infinite recursion with same argument	Verify the recursive call uses n-1, node.left, etc.
Forgetting to return the recursive call	Function returns null/0 for non-base cases	Every code path must return a value
Modifying global state unsafely	Backtracking problems produce wrong results	Undo state changes after recursive calls
Tracing instead of trusting	Mental paralysis on complex trees	Write the contract, apply the leap of faith
Checking n == 1 instead of n == 0	Off-by-one in factorial, Fibonacci, etc.	Trace the base case by hand once

---

8. Practice Exercises

Warmup (implement these before looking at solutions)

W1. Factorial Write factorial(n) recursively. Then rewrite it with an accumulator (tail-recursive style). What is the maximum n before stack overflow in Java?

W2. Fibonacci with Memoization Write fib(n) naive first. Profile the call count for n=30. Then add memoization. Compare call counts.

W3. Power Function Write power(base, exp) recursively. O(exp) version first, then optimize to O(log exp) using the identity: x^n = x^(n/2) * x^(n/2) for even n.

Applied (these build the patterns you’ll need for trees and DP)

A1. Flatten Nested List Given a nested list like [1, [2, [3, 4], 5], 6], return [1, 2, 3, 4, 5, 6] using recursion. Define clearly: what does your function receive, what does it return?

A2. Count Paths in Grid Count unique paths from top-left to bottom-right of an m x n grid where you can only move right or down. Use recursion first (exponential), then memoize.

A3. Generate All Subsets Given [1, 2, 3], return all 8 subsets: [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]. The recursive structure: for each element, either include it or don’t. Two recursive calls. Derive the decision tree.

---

Navigation

← Back to Phase Overview: README.md → Next: 02 — Divide & Conquer