Recursion in Java Explained - Quiz

Recursion in Java is a technique where a method calls itself, either directly or through a chain of other methods, splitting the task into smaller subproblems of the same shape.

Every correct recursive method has two parts:

1. The base case — a condition under which the method returns a result without calling itself again. It is mandatory and must be reachable for every valid argument: write it as an inequality if (n <= 1) rather than an equality if (n == 1), otherwise a call with zero or a negative number jumps over the base and ends in StackOverflowError.

2. The recursive case — the method calls itself with an argument that moves the computation closer to the base case.

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

Recursion reads more naturally than a loop for tree and graph traversal, divide-and-conquer algorithms (quicksort, merge sort, binary search) and backtracking.

On every method invocation the JVM pushes a new frame onto the call stack, holding the arguments, local variables and the return address. A frame is popped only when its method has returned, so during recursion every intermediate frame stays in memory until the calls reach the base case.

StackOverflowError is thrown when the total size of those 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.

There is no fixed depth limit. It depends on:

• thread stack size — usually 512 KB to 1 MB by default, configurable with the JVM flag -Xss (for example java -Xss2m RecursionExample);
• frame size — the more parameters and local variables a method has, the fewer calls fit on the stack.

In practice a simple method survives a few thousand to a few tens of thousands of nested calls, but code must never rely on a specific number. Raising -Xss is only a stopgap: if the depth depends on input size, rewrite the algorithm as a loop.

Virtual threads (Java 21+) keep their stack on the heap and grow it on demand, so -Xss does not apply to them — yet their depth is finite too.

Direct recursion — a method calls itself.

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:

static long factorialTail(int n, long acc) {
    if (n <= 1) {
        return acc;
    }
    return factorialTail(n - 1, n * acc);
}

Java does not optimize tail recursion. The JVM specification does not require tail call optimization (TCO) and HotSpot does not implement it: a new stack frame is created for every call anyway. Scala and Kotlin compilers rewrite such a call into a loop, Java does not. That is why the tail form gives no protection against StackOverflowError in Java, and deep recursion has to be converted into a loop by hand. This is a frequent interview question.

The naive implementation makes two recursive calls on every step, so the same values are recomputed over and over. The complexity is exponential — O(2ⁿ): fibonacci(40) makes more than 300 million calls and visibly freezes.

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);
}

Memoization means caching values that have already been computed so each one is calculated exactly once. Complexity drops to O(n):

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];
}

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

Any recursion can be rewritten as a loop and vice versa. The differences are memory, speed and readability:

• Memory: recursion uses O(depth) on the call stack (one frame per call), a loop uses O(1) extra memory.
• Speed: the loop is faster; recursion pays the overhead of a method call and return on every step.
• Failure risk: recursion fails with StackOverflowError at large depth, while the loop never grows the stack.
• Readability: recursion wins for trees, graphs and backtracking; loops win for linear passes and counters.

Linear recursion (factorial, Fibonacci) becomes an ordinary loop that accumulates the result:

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

For trees and graphs, introduce an explicit stack: an ArrayDeque for depth-first traversal or a Queue for breadth-first traversal. The nesting moves from the thread stack to the heap, so the depth is bounded by available memory instead of the -Xss flag:

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);
            }
        }
    }
}