How Java Runs Recursion

Each call is a new copy

When a method calls itself, Java makes a new copy of it (called a frame) with its own variables and puts it on top of the call stack. The calling copy pauses on that line. When the new copy returns, the paused copy continues from where it stopped.

static int fact(int n) {
    if (n == 0) return 1;          // base case
    int smaller = fact(n - 1);     // pause here until the answer comes back
    return n * smaller;
}

Watch three things:

1. Going down, every copy stops at fact(n - 1).
2. Only fact(0) answers without calling anyone.
3. Coming back up, each copy multiplies by its own n.

Code before the call vs after the call

static void show(int n) {
    if (n == 0) return;
    System.out.println("down " + n);   // before the call
    show(n - 1);
    System.out.println("up " + n);     // after the call
}

• Code before the call runs on the way down.
• Code after the call runs on the way back up, in reverse order.

Guess the output of show(3), then check:

The answer is down 3, down 2, down 1, up 1, up 2, up 3. If you expected up 3 first, you were thinking “the call is a jump”. It isn’t: show(3) is a separate copy that still has n = 3 when it continues.

Tracing on paper

For “what does this print” questions, write one line per call and indent by depth:

fact(3)
  fact(2)
    fact(1)
      fact(0) -> 1
    fact(1) = 1 * 1 = 1
  fact(2) = 2 * 1 = 2
fact(3) = 3 * 2 = 6

The indentation is the call stack. You can do the same in Java when debugging: print with " ".repeat(depth).

StackOverflowError

• No base case, or it’s never reached: the calls never stop.
• Too deep: Java handles a few thousand nested calls. On this site, Java runs in your browser, so stay under about 5,000.

For very deep inputs, use a loop or a table instead (chapter 3).

Remember

• New call = new copy with its own variables.
• The caller waits, then continues.
• Before the call = on the way down. After the call = on the way up.

void show(int n) {
    if (n == 0) return;
    show(n - 1);
    System.out.print(n + " ");
}