Recursion

Recursion is the process of a method calling itself. It can break a complex problem into smaller versions of the same problem, but it can also create repeated work and a growing call stack.

Two parts of recursion

A recursive method usually needs two parts:

• Base case: stop recursing and return a direct result.
• Recursive case: make the problem smaller and call itself.

Without a base case, the method calls itself forever until the call stack overflows.

static void tell_story() {
    System.out.println("Once upon a time...");
    System.out.println("There was an old monk in a temple.");
    System.out.println("The old monk told a young monk a story:");
    tell_story();
}

Each call to tell_story() prints three sentences, then calls itself to tell the same story again. This counterexample has no stopping condition: running it keeps growing the call stack and eventually triggers StackOverflowError. Use it to recognize a method calling itself, not as a program that can finish normally.

Factorial

Factorial is a classic first recursion example.

static long factorial(int n) {
    if (n == 0) {
        return 1;
    }
    return n * factorial(n - 1);
}

Output:

5! = 120

factorial(5) first calls factorial(4), then factorial(3), until it reaches factorial(1). Only then do the results return upward.

Ackermann's Method

Ackermann's method is a classic recursion example. Unlike factorial, it chooses different recursive branches based on both m and n.

static long ackermann(long m, long n) {
    if (m == 0) {
        return n + 1;
    }
    if (n == 0) {
        return ackermann(m - 1, 1);
    }
    return ackermann(m - 1, ackermann(m, n - 1));
}

Output:

7

This method grows extremely fast. As a beginner, only try very small inputs.

The table below shows m = 0…3 and n = 0…4. The first three rows grow gently, but at m = 3 each step to the right almost doubles the preceding result before adding more:

The table stops before m = 4: it jumps from A(4,0) = 13 to A(4,1) = 65533, and the following entry is already impractical to calculate or display directly.

The cost of recursion

Recursive code can be concise, but every recursive call creates a method call. For large inputs, this can be slow or even overflow the stack.

static long fibonacci(int n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    return fibonacci(n - 2) + fibonacci(n - 1);
}

Output:

13

This version repeats many calculations. For example, both fibonacci(5) and fibonacci(4) eventually compute fibonacci(3).

Tower of Hanoi

Some problems are naturally recursive. Tower of Hanoi can be described as:

1. Move the top n - 1 disks from source to helper.
2. Move the largest disk from source to destination.
3. Move the n - 1 disks from helper to destination.

static void hanoi(int n, char from, char helper, char to) {
    if (n == 0) {
        return;
    }
    hanoi(n - 1, from, to, helper);
    System.out.println(from + " -> " + to);
    hanoi(n - 1, helper, from, to);
}

Output:

A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C
Moves: 7

Each visible move moves one disk, but the recursive task first moves the top n - 1 disks.

Recursion is not meant to look advanced. It helps express problems that already have a self-similar structure.