5.3 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 tellStory() {
    System.out.println("Once upon a time...");
    tellStory();
}

Factorial

Factorial is a classic first recursion example.

public class FactorialDemo {
    static int factorial(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        return n * factorial(n - 1);
    }

    public static void main(String[] args) {
        System.out.printf("5! = %d%n", factorial(5));
    }
}

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 Function

Ackermann's function is a classic recursion example. Unlike factorial, it does not simply subtract 1 from n; it chooses different recursive branches based on both m and n.

public class AckermannDemo {
    static int ackermann(int m, int n) {
        if (m == 0) {
            return n + 1;
        }
        if (n == 0) {
            return ackermann(m - 1, 1);
        }
        return ackermann(m - 1, ackermann(m, n - 1));
    }

    public static void main(String[] args) {
        System.out.println(ackermann(2, 2));
    }
}

Output:

7

This function is useful for seeing recursion nested inside recursion, but it grows extremely fast. As a beginner, only try very small inputs such as ackermann(2, 2) or ackermann(3, 1).

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 int fibonacci(int n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    return fibonacci(n - 2) + fibonacci(n - 1);
}

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 the source peg to the helper peg.

2. Move the largest disk from the source peg to the destination peg.

3. Move the n - 1 disks from the helper peg to the destination peg.

static int moveCount = 0;

static void hanoi(int n, char src, char mid, char dst) {
    if (n == 1) {
        System.out.println(src + " -> " + dst);
        moveCount++;
    } else {
        hanoi(n - 1, src, dst, mid);
        System.out.println(src + " -> " + dst);
        moveCount++;
        hanoi(n - 1, mid, src, dst);
    }
}

Each visible move moves only one disk, but the recursive task is "move the top n - 1 disks first, then move the largest disk." Use the lab below to step through the three pegs.

Recursion is not for looking clever. It is useful when a problem has a naturally self-similar structure.