Recursion

Recursion is a technique where a method calls itself. A task is reduced to the same task of a smaller size, again and again, until the answer is obvious. Recursion is a natural fit for nested structures: folders with subfolders, trees, menus with submenus.

A recursive method

A countdown: the method prints a number and calls itself with a number one smaller. When the number reaches zero, the calls stop:

void countdown(int n) {
    if (n == 0) {
        IO.println("Liftoff!");
        return;
    }
    IO.println(n);
    countdown(n - 1);
}
 
void main() {
    countdown(3);
}

Output:

3
2
1
Liftoff!

The base case

Every recursive method has two parts. The base case is the condition where the method answers right away, without a new call. The recursive step is the call to itself with simpler data. The factorial n! — the product of the numbers from 1 to n — shows both parts well:

long factorial(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}
 
void main() {
    IO.println(factorial(5));
    IO.println(factorial(20));
}

Output:

120
2432902008176640000

factorial(5) becomes 5 * factorial(4), then 5 * 4 * factorial(3) and so on, until it reaches factorial(1), which returns 1 right away.

The call stack

Every unfinished call is kept on the call stack — an area of memory where Java remembers where to return and what values the local variables had. Code after the recursive call runs on the way back, from the deepest call to the first one:

void dive(int depth) {
    if (depth > 3) {
        return;
    }
    IO.println("Down: " + depth);
    dive(depth + 1);
    IO.println("Up: " + depth);
}
 
void main() {
    dive(1);
}

Output:

Down: 1
Down: 2
Down: 3
Up: 3
Up: 2
Up: 1

Recursion and loops

Any recursion can be rewritten as a loop and vice versa. The sum of a number's digits looks shortest when recursive: the last digit plus the digit sum of the rest of the number:

int digitSum(int n) {
    if (n < 10) {
        return n;
    }
    return n % 10 + digitSum(n / 10);
}
 
void main() {
    IO.println(digitSum(2025));
}

Output:

9

For simple repetition a loop is usually clearer and faster. Recursion is the choice when the task itself is recursive.

Common mistake

Without a base case, or with a step that does not move toward it, the method calls itself forever. The call stack overflows and the program crashes:

int sum(int n) {
    return n + sum(n - 1);
}
 
void main() {
    IO.println(sum(3));
}

Output:

Exception in thread "main" java.lang.StackOverflowError

Start a recursive method with the base case and make sure each call brings the data closer to it. How the stack works and how it differs from the heap is covered in the Memory and garbage collection lesson.