Recursion

Some tasks are easiest to describe through themselves. Take the sum of the numbers from 1 to n. It can be defined by two rules:

• the sum up to zero is 0;
• the sum up to n is n plus the sum up to n - 1.

A Java method repeats this definition word for word and calls itself:

public class Main {
    static int sum(int n) {
        if (n == 0) {
            return 0;
        }
        return n + sum(n - 1);
    }

    public static void main(String[] args) {
        System.out.println(sum(3)); // 6
        System.out.println(sum(5)); // 15
    }
}

Back to the kitchen appliance; let's see how it computes sum(3):

1. The appliance sum got 3, but does not know the answer right away.
2. It sets up an identical appliance next to it, hands it 2 and waits for the result, to add its own 3 to it.
3. The second appliance hands the work to a third one with 1 in the same way, and that one to a fourth with 0.
4. The fourth answers 0 at once, calling no one.
5. The answers travel back: the third returns 1 + 0, the second 2 + 1, the first 3 + 3, that is 6.

The two branches of a recursive method

Recursion is a method calling itself. A recursive method always has two branches.

The base case

The branch where the method finishes without a new call is called the base case. In sum it is if (n == 0) { return 0; }: the call sum(0) returns 0 at once.

Without a base case the calls never end. So every new call must bring the argument closer to the base case: here n goes down by one.

The recursive step

The line return n + sum(n - 1); calls the same method with an argument one smaller. The call sum(3) waits for the result of sum(2), which waits for sum(1), and so on down to sum(0). Only then does each waiting call add its own n and return its answer.

The call stack

Until a call finishes, Java keeps its parameters and the place to return the result to. These records live on the call stack: each unfinished call has its own record. The stack is like a pile of plates:

• a new call puts a plate on top;
• a finished call takes the top plate off.

That is why every call of sum has its own variable n. The pile holds records with n equal to 3, 2, 1 and 0 at the same time, and they do not get in each other's way. Press "Next step" and watch the "call frames" column: each frame in it is the record of one call. The pile grows up to sum(0) and then comes apart from the top down.

The results come back in reverse order: the call started last finishes first.

Here the appliance picture is off. You would need four appliances, but the program has one method sum. Only each call's own data is kept separately: its own n and the place to return the result to.

StackOverflowError

The call stack is not endless. If there is no base case, or the calls never reach it, records pile up until the space runs out. Then the program stops with the error StackOverflowError, a name that means the stack has overflowed. This usually happens after thousands or tens of thousands of calls: the exact number depends on the JVM's settings.

Interviewers often ask: "When does a StackOverflowError happen?" The answer: when a chain of calls is too long or never stops, because the base case cannot be reached.

A loop instead of recursion

The same sum can be computed with a loop:

static int sumLoop(int n) {
    int total = 0;
    for (int i = 1; i <= n; i++) {
        total = total + i;
    }
    return total;
}

A loop calls no new methods, so the pile does not grow, however many steps there are. Java does not turn recursion into a loop by itself, so for very long chains you write a loop. Recursion fits where the task is built from a smaller copy of itself.

Common mistake

The method was called with an argument for which the base case cannot be reached:

System.out.println(sum(-1)); // ✗

Exception in thread "main" java.lang.StackOverflowError

From -1 the chain goes to -2, -3 and on, and n == 0 never comes. Each call puts a new record on the stack until the space runs out. Make the base case reachable for any argument: for example, if (n <= 0) { return 0; }.

Key points

• A recursive method calls itself, and it needs a base case that finishes without a new call.
• Each unfinished call takes a record on the call stack, so every call of sum has its own n.
• The results come back in reverse order: the call started last finishes first.
• If the base case cannot be reached, the stack overflows and the program stops with a StackOverflowError.