Recursion: A Method That Calls Itself

Calling yourself

A recursive method is one that calls itself to solve a smaller version of the same problem.

Think of it like this: Russian nesting dolls: to reach the smallest doll, you open a doll, find a smaller doll inside, and do the same again... until you reach a doll that doesn't open. That last doll is the base case.

public class Main {
    static void countdown(int n) {
        if (n == 0) {
            System.out.println("Go!");
            return;
        }
        System.out.println(n);
        countdown(n - 1);
    }

    public static void main(String[] args) {
        countdown(3);
    }
}

Output

3
2
1
Go!

Every recursive method needs two parts:

• A base case – when to stop (here: n == 0).
• A recursive step – call itself with a smaller problem (here: n - 1).

Factorial

5! (five factorial) = 5 × 4 × 3 × 2 × 1. Notice that 5! = 5 × 4!, and 4! = 4 × 3!, and so on:

public class Main {
    static long factorial(int n) {
        if (n <= 1) {
            return 1;
        }
        return n * factorial(n - 1);
    }

    public static void main(String[] args) {
        System.out.println(factorial(5));
        System.out.println(factorial(10));
    }
}

Output

120
3628800

Forgetting the base case

Without a way to stop, the method calls itself forever until Java runs out of memory:

public class Main {
    static int forever(int n) {
        return forever(n + 1);
    }

    public static void main(String[] args) {
        forever(1);
    }
}

Output (Java stops with an error)

Exception in thread "main" java.lang.StackOverflowError

Remember: No base case = StackOverflowError. Always write the stopping rule first.