🧩 Methods · Beginner

Recursion in Java

Base case + recursive case; tracing recursive calls.

🧩 The mysteryTo compute 5!, you only need 4!. To know 4!, you only need 3!... Everyone passes the job down. So who does the actual work? (The answer is beautiful.)

Solve a smaller version

A recursive method calls itself on a smaller version of the same problem. 5! is 5 × 4!, and 4! is 4 × 3!, and so on, down to 1! = 1, which we just know.

static int factorial(int n) {
    if (n <= 1) return 1;        // base
    return n * factorial(n - 1); // recursive
}

Two essential parts

Every correct recursion has a base case: the simplest input, answered directly without recursing. And a recursive case that calls itself on an input moving toward the base case. Without a reachable base case, the calls never stop and you get StackOverflowError.

static int sum(int n) {
    if (n == 0) return 0;     // base case
    return n + sum(n - 1);    // smaller n
} // sum(4) = 4+3+2+1+0 = 10

🔮 Predict it

Your turn

What prints?

static int pow2(int n) {
    if (n == 0) return 1;
    return 2 * pow2(n - 1);
}
void main() {
    System.out.println(pow2(5));
}

10
32
64

Show the answer

pow2(5) = 2 × pow2(4) = 2 × 2 × pow2(3) = ... = 2 × 2 × 2 × 2 × 2 × pow2(0). The base case returns 1, so the answer is 32.

Every call gets its own frame

Each call has its own n, in its own frame. count(3) waits for count(2), which waits for count(1)... Code after the recursive call runs as the calls unwind, deepest first. That's why this prints 1 2 3, not 3 2 1.

static void count(int n) {
    if (n == 0) return;
    count(n - 1);
    System.out.print(n + " ");
} // count(3) prints: 1 2 3

🔮 Predict it

Down and back up

One print before the call, one after. What prints?

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

3 2 1 1 2 3
3 2 1
1 2 3 3 2 1
3 3 2 2 1 1

Show the answer

On the way down, each call prints before recursing: 3 2 1. At 0 the base case returns, and on the way back up, each call finishes its second print: 1 2 3.

⚠️ The trap

No progress, no stop

The recursive call must make the problem smaller. Below, sum(n) calls itself with the same n, so it never gets closer to 0. Every call pushes another frame until StackOverflowError. It should be sum(n - 1).

static int sum(int n) {
    if (n == 0) return 0;
    return n + sum(n); // same n!
}

🔮 Predict it

Two calls per call

This is Fibonacci: 0, 1, 1, 2, 3, 5, ... What is f(7)?

static int f(int n) {
    if (n <= 1) return n;
    return f(n - 1) + f(n - 2);
}
void main() {
    System.out.println(f(7));
}

8
13
21
7

Show the answer

Each call splits into f(n - 1) + f(n - 2) until n <= 1. The sequence f(0) to f(7) is 0, 1, 1, 2, 3, 5, 8, 13.

💼 In the real world

In real projects

Recursion fits anything shaped like a tree: folders inside folders, JSON inside JSON, HTML elements, org charts, and divide-and-conquer algorithms like merge sort. It's also an interview favorite: tracing a recursive call by hand is a skill interviewers love to test.

Key takeaways

Base case: the simplest input, answered directly
Recursive case: call yourself on a smaller input
Each call has its own parameters and locals
Code after the recursive call runs as the calls unwind

💡 Like Russian dolls: open one to find a smaller one inside, until you reach the solid doll that doesn't open (the base case).

🤯 Did you know?

Search Google for "recursion" and it asks: "Did you mean: recursion". Click it, and you're right back where you started.

Practice questions

What does this print?

static int sum(int n) {
    if (n == 0) return 0;
    return n + sum(n - 1);
}
void main() {
    System.out.println(sum(4));
}

Check your answer

10. sum(4) = 4 + sum(3) = 4 + 3 + sum(2) ... = 4 + 3 + 2 + 1 + 0 = 10.

What does this print?

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

3 2 1
1 2 3
0 1 2 3
3 2 1 0

Check your answer

1 2 3. count(3) first calls count(2), which first calls count(1), and so on. The prints happen as the calls return, deepest first: 1, then 2, then 3.

Next: what really happens when recursion never stops, and the error a famous website is named after.