Recursion: Essence, Stack Frames, and Tail Optimization

What is Recursion?

The essence of recursion is a function calling itself to break down a large problem into smaller sub-problems of the same structure.

[!TIP] Core Concept: Transform a problem of scale $N$ into a problem of smaller scale (usually $N-1$ or $N/2$) until it hits a Base Case that has a trivial, direct solution.

The Three Pillars of Recursion

Recursion and Stack Frames

Every function call creates a Stack Frame on the Call Stack, which stores:

• Local variables
• The return address (where to go back after finishing)
• Function parameters

factorial(4)
  └─ factorial(3)
       └─ factorial(2)
            └─ factorial(1)
                 └─ factorial(0) → Returns 1
            ← 1 * 1 = 1
       ← 2 * 1 = 2
  ← 3 * 2 = 6
← 4 * 6 = 24

StackOverflowError: Occurs when recursion depth is too high, exhausting the stack memory. Java typically supports 1,000 to 10,000 levels depending on stack size (default 1MB).

Implementation Template

public ReturnType recurse(params) {
    // 1. Base Case (CRITICAL: Must be at the very beginning)
    if (isBaseCase) {
        return baseResult;
    }
    
    // 2. Recursive calls (Scale reduction)
    ReturnType subResult = recurse(smallerParams);
    
    // 3. Post-order processing (Combining results)
    return merge(params, subResult);
}

Classic Examples

Fibonacci Sequence

// Naive: O(2^n) time - Exponential explosion
public int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

// Memoized: O(n) time - Eliminates redundant subproblems
public int fib(int n, Integer[] memo) {
    if (n <= 1) return n;
    if (memo[n] != null) return memo[n];
    return memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
}

Maximum Depth of Binary Tree

Trees are recursively defined, making recursion the most natural way to traverse them.

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    int leftHeight = maxDepth(root.left);
    int rightHeight = maxDepth(root.right);
    return Math.max(leftHeight, rightHeight) + 1;
}

Tail Recursion Optimization

Tail Recursion occurs when the recursive call is the final operation in the function, with no computation remaining afterwards.

// Standard: return n * fact(n-1); (Needs a multiplication AFTER the call)
// Tail: Carry the "work yet to be done" via an accumulator parameter
public int factorial(int n, int accumulator) {
    if (n == 0) return accumulator;
    return factorial(n - 1, n * accumulator);
}

While some languages (like Kotlin or Scala) perform Tail Call Optimization (TCO) to reuse stack frames, Java currently does NOT support TCO. For high-depth recursion in Java, rewrite to iteration.

Recursion to Iteration

Any recursion can be simulated using an explicit stack.

// Recursive Preorder
void recurse(TreeNode node) {
    if (node == null) return;
    visit(node);
    recurse(node.left);
    recurse(node.right);
}

// Iterative Preorder (Using explicit Deque as Stack)
void iterate(TreeNode root) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        if (node == null) continue;
        visit(node);
        stack.push(node.right); // Push right first to process left first
        stack.push(node.left);
    }
}

Complexity Reference Table

Technical Summary for Production

1. Focus on the Base Case: It's the most common failure point.
2. Memoize early: Don't calculate the same thing twice.
3. Analyze the stack depth: $O(N)$ depth can overflow; $O(\log N)$ is usually safe.
4. Trust the Logic: When writing recursion, trust your recurrence relation. Don't try to manually expand the "call tree" in your head beyond 2-3 levels. 筋