Java Recursion

Recursion is a technique where a method solves a problem by calling itself with a smaller or simpler version of the same problem, until it reaches a case simple enough to answer directly. It is an alternative to iteration (loops) for expressing repetitive computation, and it is especially natural for problems that are already defined in terms of themselves, such as factorials, tree traversals, and many divide-and-conquer algorithms.

Every correct recursive method needs two distinct parts: a base case that stops the recursion, and a recursive case that makes progress toward that base case. Get either one wrong, and the method either never recurses (wrong answer) or never stops (a StackOverflowError).

Why it matters

Some problems are defined in terms of smaller versions of themselves: walking a folder tree, traversing a nested structure, dividing a list in half. Recursion expresses those directly. It is also a favourite interview topic because it tests whether you can reason about the call stack — and because a missing base case fails in a very recognisable way.

Base Case vs Recursive Case

The base case is the condition under which the method returns a value directly, without calling itself again — it is what eventually stops the recursion. The recursive case is where the method calls itself, but always with an argument that is "closer" to the base case than the current call (a smaller number, a shorter list, a node one level deeper). If the recursive case doesn't reliably shrink the problem, or the base case condition is never actually reached, the recursion never terminates.

The Call Stack: Building Up and Unwinding

Each time a method calls itself, the JVM pushes a new stack frame onto the call stack, holding that call's local variables and its return address. Calls keep building up (going "deeper") until the base case is hit, at which point that innermost frame returns a value. Then the frames unwind one at a time, back down the stack, with each waiting call resuming exactly where it paused, using the value just returned to complete its own calculation, and returning its own result to the frame below it. This build-up-then-unwind pattern is why tracing recursion visually as a stack of pending calls is so useful.

• factorial(4) calls factorial(3), which calls factorial(2), which calls factorial(1), which calls factorial(0) — the base case.
• factorial(0) returns 1 immediately, without recursing further.
• factorial(1) resumes, computes 1 * 1 = 1, and returns 1.
• factorial(2) resumes, computes 2 * 1 = 2; factorial(3) computes 3 * 2 = 6; factorial(4) computes 4 * 6 = 24.

Recursion vs Iteration

Anything expressible recursively can also be expressed iteratively with a loop, and vice versa. Recursion often produces shorter, more readable code for naturally self-referential problems (tree/graph traversal, backtracking, divide-and-conquer algorithms like merge sort), because the code mirrors the problem's own definition. Iteration is usually more memory-efficient, since it doesn't grow the call stack, and can be faster because it avoids the overhead of repeated method calls. As a rule of thumb, prefer iteration for simple linear repetition, and reach for recursion when the problem structure is naturally hierarchical or self-similar.

StackOverflowError

Each recursive call consumes stack memory, and the JVM's call stack has a fixed, finite size. If a recursive method is missing its base case, has a base case that is never reached due to a logic error, or simply recurses too deeply for a very large input, the stack fills up and the JVM throws a StackOverflowError. This is an Error, not an Exception, signaling a serious problem with the program's structure rather than an expected, recoverable condition — though it can technically still be caught with a try-catch block.

Examples

public class RecursionDemo {

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

    static int fibonacci(int n) {
        if (n <= 1) {           // base case
            return n;
        }
        return fibonacci(n - 1) + fibonacci(n - 2); // recursive case
    }

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

120
13

public class RecursionErrorDemo {

    // Bug: no condition ever stops the recursion
    static int badRecursion(int n) {
        return badRecursion(n + 1);
    }

    public static void main(String[] args) {
        try {
            badRecursion(0);
        } catch (StackOverflowError e) {
            System.out.println("Caught: StackOverflowError due to a missing base case");
        }
    }
}

Caught: StackOverflowError due to a missing base case

Exercise

Write a recursive method that returns the sum of the digits of a non-negative number. Do not use a loop.

Expected output: 19 for 4096 (4 + 0 + 9 + 6), then 7 for 7.

public class DigitSum {

    static int sumDigits(int n) {
        // TODO: base case - a single digit is its own sum
        // TODO: recursive case - last digit plus the sum of the remaining digits
        return 0;
    }

    public static void main(String[] args) {
        System.out.println(sumDigits(4096));
        System.out.println(sumDigits(7));
    }
}

public class DigitSum {

    static int sumDigits(int n) {
        if (n < 10) {
            return n;
        }
        return n % 10 + sumDigits(n / 10);
    }

    public static void main(String[] args) {
        System.out.println(sumDigits(4096)); // 19
        System.out.println(sumDigits(7));    // 7
    }
}

Quick quiz

Interview questions