Demo: tracing recursion on the call stack

Written Explanation

The program we trace

We use a slightly expanded factorial so each step has a visible line:

static int factorial(int n) {
    if (n <= 1) {
        return 1;                       // base case
    }
    int smaller = factorial(n - 1);     // recursive call
    return n * smaller;                 // runs only after the call returns
}

Splitting the work into smaller and the final return is purely for observation: it gives you a line to stop on after each recursive call comes back.

Step 1: trace by hand with a table

Before running anything, predict. Every call is a frame with its own n; smaller only gets a value when the call below it returns.

The answer is 24, and at the deepest point there are four factorial frames above main.

Step 2: watch it with print statements

You do not need a debugger to see the pile. Add a line on entry and one on exit, plus a stack dump at the base case:

static int factorial(int n) {
    System.out.println("enter n=" + n);
    if (n <= 1) {
        Thread.dumpStack();             // prints the stack right now
        return 1;
    }
    int smaller = factorial(n - 1);
    int result = n * smaller;
    System.out.println("leave n=" + n + " result=" + result);
    return result;
}

(These println calls are temporary tracing tools, so they do not break Lesson 2's rule: delete them afterwards.) Read the real output in Example 1 below.

Step 3: use a debugger

A debugger runs your program while letting you pause it. The steps below describe the common IDE workflow; names differ per tool, so adapt them.

1. Set a breakpoint on the first line of factorial (in many IDEs by clicking in the margin beside the line number). A breakpoint tells the debugger to pause there.
2. Start in debug mode (often a bug icon or a "Debug" entry next to "Run").
3. When it pauses, find the call stack panel. IDEs call it "Frames", "Call Stack" or similar. You should see factorial above main, and a variables panel showing n = 4.
4. Resume to the next breakpoint hit (or use "step into" at the recursive line). Each time the breakpoint hits again, another factorial frame is on top, with n = 3, then 2, then 1.
5. Click each frame in the panel: the variables panel changes to show that frame's n. This is Lesson 4's "each call has its own variables" made visible.
6. Keep stepping (or remove the breakpoint and set one on return n * smaller;). Watch the frames disappear one at a time from the top as their values return: 1, 2, 6, 24.

Note on the environment: I could not drive a debugger in the writing environment, so the debugger steps above come from the general behaviour of IDE debuggers rather than a live session. The print and stack-dump output below was run for real.

Step 4: the planned mistake, with the base case removed

Delete the base case:

static int factorial(int n) {
    return n * factorial(n - 1);
}

Run it. There is no frame that ever returns. The stack grows until it overflows, and Java reports StackOverflowError with a trace in which one line repeats. Compare the repeating line to the single-line chain you saw for a, b, c in Lesson 5. With a debugger you would see the same thing: the call-stack panel growing deeper with n going 4, 3, 2, 1, 0, -1, -2 and so on, never reaching a stopping point.

Finally, restore the base case and run again to confirm the answer 24. Always finish the demo by making the fix; a bug you understood but did not fix teaches less than one you closed.