Recursion

What Is Recursion?

Recursion is when a method calls itself to solve a smaller version of the same problem. Every recursive method needs two essential parts:

Base case — the simplest form of the problem, solved directly without another recursive call. This is what stops the recursion.
Recursive case — the method calls itself with a smaller or simpler input, moving closer to the base case each time.

Warning

If a recursive method is missing a base case, or the recursive case never actually approaches it, the method will call itself forever (or until it crashes). Always make sure every recursive path leads to the base case.

Classic Example: Factorial

The factorial of n (written n!) is the product of all positive integers up to n. It has a natural recursive definition: 0! is 1 (the base case), and n! is n times (n - 1)! for any n greater than 0.

Factorial.java

Java

public class Factorial {

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

    public static void main(String[] args) {
        System.out.println(factorial(5)); // 5 * 4 * 3 * 2 * 1
        System.out.println(factorial(0));
    }
}

120
1

Classic Example: Fibonacci

The Fibonacci sequence (0, 1, 1, 2, 3, 5, 8, 13, ...) is defined so that each number is the sum of the two before it. It has two base cases (fib(0) and fib(1)) and a recursive case that calls itself twice:

Fibonacci.java

Java

public class Fibonacci {

    static int fib(int n) {
        if (n == 0 || n == 1) { // base cases
            return n;
        }
        return fib(n - 1) + fib(n - 2); // recursive case
    }

    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            System.out.print(fib(i) + " ");
        }
    }
}

0 1 1 2 3 5 8 13 21 34

Tip

This naive Fibonacci implementation recalculates the same values many times and runs in exponential time. In real code, prefer an iterative loop or memoization (caching previously computed results) for Fibonacci-style problems.

StackOverflowError

Each recursive call adds a new frame to the call stack to track its local variables and where to resume execution. If recursion goes too deep — because there is no base case, the base case is never reached, or the input is simply too large — the JVM runs out of stack space and throws a StackOverflowError.

A recursive call with no base case

Java

static void runaway(int n) {
    System.out.println(n);
    runaway(n + 1); // never stops — no base case
}

Warning

StackOverflowError is an Error, not an Exception. Unlike checked exceptions, it signals a serious problem with the program itself (uncontrolled recursion, in this case) and is generally not meant to be caught and recovered from. Catching it can mask a real bug; the correct fix is to add or repair the base case, or restructure the algorithm to avoid deep recursion.

No Tail-Call Optimization in Java

Note

Some languages (like Scheme or Scala) optimize "tail-recursive" calls — where the recursive call is the very last thing a method does — by reusing the current stack frame instead of creating a new one, which lets recursion run in constant stack space. The JVM does not perform this optimization. Even a tail-recursive-looking Java method still consumes one stack frame per call and can overflow on deep enough input.

When to Prefer Iteration

Because Java has no tail-call optimization, recursion carries a real cost: stack frame overhead per call and a hard ceiling on recursion depth (typically a few thousand to tens of thousands of frames, depending on stack size and frame complexity). For performance- or depth-sensitive code, an equivalent iterative loop is usually safer and faster in Java.

The same factorial, written iteratively

Java

static long factorialIterative(int n) {
    long result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

Recursion tends to read more naturally for problems that are inherently recursive: tree/graph traversal, divide-and-conquer algorithms, backtracking
Iteration is usually preferable when the recursion depth could scale with input size and a loop expresses the same logic just as clearly
When you do need deep recursion, consider increasing the JVM stack size (the -Xss flag) or restructuring the algorithm rather than relying on default limits