Lesson 12.2 · Recursion

What the Call Stack Does

Each call gets a frame with its own variables; frames stack up until the base case, then unwind in reverse, combining results.

12 min

Think of it like this

Opening nested boxes to find a key: each box you open goes on a pile, and you can't close a box until you've finished with the one inside it. When you find the key, you close the boxes in reverse order.

1.Frames going down and coming back

When factorial(3) calls factorial(2), the first call pauses with its own n = 3 saved in a stack frame. The frames pile up until the base case returns, and then each paused call resumes and finishes its multiplication.

▶ Dry run: factorial(3) on the call stackfactorial(3)

call stack(stack)

factorial(3): waits for factorial(2)

Step 1/5factorial(3) needs factorial(2): it pauses.

2.Stack depth and StackOverflowError

Each frame uses memory, and the JVM thread stack is limited (typically around 10,000–20,000 simple frames with default settings). Recursion depth is the space cost: a depth of n is O(n) space even if each frame is tiny.

Overflow.java

public class Main {
    static int depth = 0;
    static void dive() { depth++; dive(); }
    public static void main(String[] args) {
        try {
            dive();
        } catch (StackOverflowError e) {
            System.out.println("overflowed after more than 1000 frames: " + (depth > 1000));
        }
    }
}

Output

overflowed after more than 1000 frames: true

Remember

Each call has its own frame and variables.
Frames unwind in reverse order.
Depth = stack space; very deep recursion overflows.

Common mistakes

Assuming recursion is free in memory.
Recursing over a 10⁵-node linked list in Java.

Command Palette

What the Call Stack Does

1.Frames going down and coming back

2.Stack depth and StackOverflowError