Recursion in Java Explained

factorial(0) looks trivial — everyone knows 0! = 1. But if the base case is written as if (n == 1), the method never returns 1 — it crashes with StackOverflowError. Recursion in Java forgives a lot of mistakes. An unreachable base case isn't one of them.

Recursion in Java is a technique where a method calls itself to solve a problem. A recursive method splits the original task into smaller subproblems of the same shape and stops when it reaches the base case. Without a reachable base case the calls never end, and the program dies with StackOverflowError.

What Is Recursion in Java

A recursive method in Java is a method that calls itself, either directly or through a chain of other methods. Every such call is pushed onto the call stack and holds memory until it returns a result.

Any correct recursion consists of two parts:

• base case — a condition under which the method returns a result without calling itself again;
• recursive case — the method calls itself with an argument that moves the computation closer to the base case.

Problems where recursion reads more naturally than a loop:

• traversing trees (file system, DOM, JSON), graphs and other nested structures;
• divide-and-conquer algorithms: quicksort, merge sort, binary search;
• backtracking: N-queens, sudoku solvers, generating permutations;
• classic math exercises: factorial, Fibonacci numbers, sum of digits, exponentiation.

How Recursion Works: The Call Stack

On every method invocation the JVM creates a new frame on the call stack. A frame holds:

• the method arguments;
• local variables;
• the return address — where to continue once the method finishes.

A frame is popped only when its method has returned. That gives recursion a property beginners often miss: until the nested calls reach the base case, every intermediate frame stays in memory at the same time.

Here is how the stack unwinds for factorial(5):

factorial(5) -> 5 * factorial(4)         // frame 1
   factorial(4) -> 4 * factorial(3)      // frame 2
      factorial(3) -> 3 * factorial(2)   // frame 3
         factorial(2) -> 2 * factorial(1)// frame 4
            factorial(1) -> 1            // frame 5: base case, start unwinding
         factorial(2) = 2 * 1  = 2
      factorial(3) = 3 * 2  = 6
   factorial(4) = 4 * 6  = 24
factorial(5) = 5 * 24 = 120

The multiplication n * factorial(n - 1) happens after the nested call returns — which is exactly why the frame cannot be released earlier. The stack depth here equals n.

Base Case and Recursive Call

A base case is mandatory, and writing one is not enough — it must be reachable for every valid argument. The classic mistake: the base is declared as n == 1, and then the method is called with zero or a negative number. The condition never fires, the argument keeps going down, and the stack overflows.

Factorial: A Recursive Method

The factorial of n is the product of all positive integers from 1 to n:

n! = n × (n - 1) × (n - 2) × ... × 1, and by convention 0! = 1.

Recursive implementation in Java:

public class RecursionExample {

    static long factorial(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("Factorial is undefined for negative numbers: " + n);
        }
        if (n <= 1) {          // base case: 0! = 1 and 1! = 1
            return 1;
        }
        return n * factorial(n - 1); // recursive case
    }

    public static void main(String[] args) {
        System.out.println("5! = " + factorial(5));   // 5! = 120
        System.out.println("0! = " + factorial(0));   // 0! = 1
        System.out.println("20! = " + factorial(20)); // 20! = 2432902008176640000
    }
}

Breaking it down:

• n <= 1 — the base case, which also covers 0!;
• factorial(n - 1) — the recursive call with a smaller argument;
• the n < 0 guard turns endless recursion into a clear exception.

Fibonacci Numbers and Memoization

The Fibonacci sequence is defined by F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2). Translating the formula straight into code gives:

public class FibonacciExample {

    static long fibonacci(int n) {
        if (n <= 1) {           // base cases: F(0) = 0, F(1) = 1
            return n;
        }
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    public static void main(String[] args) {
        System.out.println(fibonacci(6)); // 8
    }
}

The code is easy to read, but it has a serious problem: two recursive calls per step give exponential complexity O(2ⁿ). The same values are recomputed over and over — fibonacci(40) makes more than 300 million calls and visibly freezes.

The cure is memoization — caching values that have already been computed. Complexity drops to O(n):

public class FibonacciMemo {

    private static final long[] CACHE = new long[93]; // F(92) is the largest value that fits in long

    static long fibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        if (CACHE[n] != 0) {   // already computed
            return CACHE[n];
        }
        CACHE[n] = fibonacci(n - 1) + fibonacci(n - 2);
        return CACHE[n];
    }

    public static void main(String[] args) {
        System.out.println(fibonacci(50)); // 12586269025 - instantly
    }
}

The same result with no recursion at all — a plain loop in O(n) time and O(1) memory:

static long fibonacciIterative(int n) {
    if (n <= 1) {
        return n;
    }
    long prev = 0;
    long curr = 1;
    for (int i = 2; i <= n; i++) {
        long next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

Types of Recursion: Direct, Indirect, Tail

Direct recursion — a method calls itself (every example above).

Indirect (mutual) recursion — method A calls B, and B calls A again:

static boolean isEven(int n) {
    return n == 0 ? true : isOdd(n - 1);
}

static boolean isOdd(int n) {
    return n == 0 ? false : isEven(n - 1);
}

Tail recursion — the recursive call is the last operation of the method, so nothing is left to do after it returns:

// tail form: the result is accumulated in an argument
static long factorialTail(int n, long acc) {
    if (n <= 1) {
        return acc;
    }
    return factorialTail(n - 1, n * acc); // nothing runs after the call returns
}

In languages such as Scala or Kotlin the compiler rewrites such a call into a loop. Java does not do this: the JVM specification does not require tail call optimization (TCO), and HotSpot does not implement it. In Java the tail form consumes exactly as much stack as ordinary recursion and fails with StackOverflowError just as easily. This is a frequent interview question.

Recursion vs Iteration: Which to Choose

Any recursion can be rewritten as a loop, and vice versa. The difference is readability and memory usage.

An iterative factorial for comparison — not a single extra frame on the stack:

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

StackOverflowError and Recursion Depth

StackOverflowError is thrown when the total size of the frames exceeds the thread stack size. It is an Error, not an Exception: catching it and carrying on is a bad idea, because the state of the program after an overflow is undefined.

What determines the maximum depth:

• Thread stack size. Usually 512 KB to 1 MB by default; set it with the JVM flag -Xss, for example -Xss2m. For an individual thread the size can be passed to the Thread constructor.
• Frame size. The more parameters and local variables a method has, the fatter each frame is and the fewer calls fit into the stack.

In practice a simple method survives a few thousand to a few tens of thousands of nested calls. There is no exact number: it depends on the JVM, the platform and the method itself, so never hard-code an assumption about it.

java -Xss2m RecursionExample

Raising -Xss is only a stopgap. If the depth depends on input size (walking a directory tree of arbitrary depth, parsing user-supplied JSON), it is safer to rewrite the algorithm as a loop with an explicit stack:

// walking a directory tree without recursion
static void printTree(File root) {
    Deque<File> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        File current = stack.pop();
        System.out.println(current.getName());
        File[] children = current.listFiles();
        if (children != null) {
            for (File child : children) {
                stack.push(child);
            }
        }
    }
}

The nesting is still there, but it now lives in an ArrayDeque on the heap instead of the thread stack, so the depth is limited by available memory rather than by -Xss.

Where Developers Get Tripped Up

• No base case, or an unreachable one (n == 1 instead of n <= 1) — an immediate StackOverflowError.
• The argument does not approach the base. A typo such as factorial(n) instead of factorial(n - 1) produces an endless chain of calls.
• Exponentially duplicated calls — the naive Fibonacci. Fixed by memoization or by switching to a loop.
• Depth driven by input data. A recursive walk over a million-element list crashes even though it worked fine on ten test items.
• Shared mutable state. Static fields modified between calls break the logic while the stack unwinds; pass state through parameters instead.
• Catching StackOverflowError instead of fixing the algorithm.
• Cyclic data structures. Traversing a graph with back edges without a visited set makes the recursion loop forever.

Always make sure that each recursive call brings the program closer to termination.

Practice Task

Write the following recursive methods:

1. static int sumOfDigits(int n) — the sum of the digits of a number. For 1234 the result is 10. Hint: base case n < 10, recursive step n % 10 + sumOfDigits(n / 10).
2. static String reverse(String s) — reverse a string. The base case is an empty string or a single character.
3. static boolean isPalindrome(String s) — palindrome check by comparing the first and last characters.

For each method test the edge cases separately: 0, an empty string and null.

Conclusion

Recursion in Java is a way of describing a problem in terms of itself, and for trees, graphs and backtracking it produces the shortest, clearest code you can write. The price of that elegance is one stack frame per call, so recursion is the right choice when the depth is bounded and predictable.

Key takeaways:

• a base case is mandatory and must be reachable for every argument;
• every recursive call must move the computation closer to that base case;
• the JVM does not optimize tail recursion — the stack is always consumed;
• naive recursion with repeated computations is rescued by memoization;
• if the depth depends on input data, switch to a loop with an explicit stack.