Recursion: A Method That Calls Itself

Russian dolls

Open a Russian doll and there's a smaller doll inside. Open that, and there's another… until you reach a tiny solid doll that doesn't open. Recursion is the same:

public class Main {
    static int countDolls(int size) {
        if (size == 1) {                       // base case: the solid doll
            System.out.println("size 1: solid, stop");
            return 1;
        }
        System.out.println("size " + size + ": open it");
        return 1 + countDolls(size - 1);       // this doll + the dolls inside
    }

    public static void main(String[] args) {
        System.out.println("total dolls: " + countDolls(4));
    }
}

Output

size 4: open it
size 3: open it
size 2: open it
size 1: solid, stop
total dolls: 4

The call stack

Each call waits for the smaller call to finish, like a pile of plates. Java keeps this pile in memory – the call stack. Watch the calls go down and the answers come back up:

public class Main {
    static int factorial(int n, String indent) {
        System.out.println(indent + "factorial(" + n + ") called");
        if (n <= 1) return 1;
        int answer = n * factorial(n - 1, indent + "  ");
        System.out.println(indent + "factorial(" + n + ") returns " + answer);
        return answer;
    }

    public static void main(String[] args) {
        factorial(4, "");
    }
}

Output

factorial(4) called
  factorial(3) called
    factorial(2) called
      factorial(1) called
    factorial(2) returns 2
  factorial(3) returns 6
factorial(4) returns 24

Common mistake: Forgetting the base case (or never reaching it). The method calls itself forever until Java runs out of stack and stops with StackOverflowError.

Remember: Every recursive method needs: 1) a base case that stops, 2) a call on a smaller problem that moves toward the base case.