Java Recursion

Java recursion is when a method calls itself to solve a problem in smaller steps. A recursive method must have a stopping condition, called a base case, so it does not call itself forever.

Recursion is useful when the same kind of task repeats on a smaller value, such as counting down, adding a range of numbers, or calculating a factorial.

How Recursion Works

A recursive method usually has two main parts:

• A base case, which returns an answer without another recursive call.
• A recursive case, which calls the same method with a smaller or simpler argument.

Without a base case, the method keeps calling itself until the program runs out of stack memory.

Countdown Example

This method prints a number, then calls itself with a smaller number. When the number reaches 0, the base case stops the recursion.

public class Main {
    static void countDown(int number) {
        if (number == 0) {
            System.out.println("Done");
            return;
        }

        System.out.println(number);
        countDown(number - 1);
    }

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

Output:

3
2
1
Done

The call countDown(3) prints 3, then calls countDown(2). The process continues until countDown(0) prints Done and returns.

Returning A Recursive Result

Recursive methods can also return values. The next example calculates the sum of all whole numbers from 1 to n.

public class Main {
    static int sumTo(int n) {
        if (n == 1) {
            return 1;
        }

        return n + sumTo(n - 1);
    }

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

Output:

15

The expression sumTo(5) becomes 5 + sumTo(4). Then sumTo(4) becomes 4 + sumTo(3), and so on. When sumTo(1) returns 1, Java works back through the waiting method calls and adds the values together.

Factorial Example

A factorial multiplies a number by each positive whole number below it. For example, 4! means 4 * 3 * 2 * 1.

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

        return n * factorial(n - 1);
    }

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

Output:

24
720

The base case handles n <= 1. Otherwise, the method multiplies n by the factorial of the next smaller number.

Recursion And The Call Stack

Each method call takes a small amount of memory on the call stack. A recursive method creates a new stack frame every time it calls itself. When a base case is reached, the calls finish in reverse order.

Because of this, recursion should move toward the base case every time. If the argument does not get closer to stopping, the program can fail with a StackOverflowError.

Common Mistakes

• Forgetting the base case.
• Writing a base case that can never be reached.
• Calling the method with the same value instead of a smaller or simpler value.
• Using recursion where a simple loop would be clearer for beginners.

Takeaway: Java recursion lets a method solve a problem by calling itself, but each recursive call must move closer to a clear base case.