Why does my recursion throw StackOverflowError, and when should I use a loop instead?

The Answer

• Each call allocates a stack frame — parameters, locals, return address — and it lives until that call returns. Recursion depth is memory.
• The default thread stack is around 1 MB, which is roughly 20,000 frames, not millions. -Xss changes it; it does not make it unbounded.
• Java does not eliminate tail calls. A recursion whose last act is the recursive call still costs a frame per level, unlike Scheme or Scala's @tailrec.
• Every recursion owes two things — call them the contract:
  1. a base case that returns without recursing;
  2. progress: every call must move strictly closer to it.
• Missing either gives StackOverflowError. Having both still overflows if the depth is proportional to a large n.
• Recursion earns its keep on branching problems — trees, graphs, backtracking — where depth is log n or the height of a structure. Linear depth belongs in a loop.

Understand It

The contract, and what each half prevents

solve(problem):
    if problem is small enough:        # BASE CASE
        return answer directly         #   - must not recurse
                                       #   - must be reachable
    smaller ← reduce(problem)           # PROGRESS
                                       #   - strictly closer to the base case
                                       #   - "strictly" is the whole word
    return combine(solve(smaller))

Two failures, and they look identical from the outside:

• No base case. dive() calls dive() forever.
• No progress. There is a base case, but some path never approaches it — solve(n) calling solve(n) when n is odd, or a graph walk revisiting a node it has already seen. The second is the one that survives code review, because the base case is right there in the source.

A cycle in the data is the same bug wearing a disguise. Walking a tree that turns out to have a back-edge never reaches a leaf, and "it worked on the test data" means the test data was acyclic.

The stack is smaller than people expect

depth = 0;
try {
    dive();
} catch (StackOverflowError e) {
    System.out.println("frames before overflow: about " + (depth / 1000) * 1000);
}

frames before overflow: about 21000

About twenty thousand. Not a million. The exact number moves between runs and JVMs — it depends on frame size, which depends on how many locals the method has — which is itself the point: the limit is not a number you can design against. A recursion of depth n over user data is a crash waiting for a large enough input.

Note it is an Error, not an Exception. Catching it is legitimate only to report and exit, as above. The stack is in an unknown state and the usual advice is not to continue.

Depth is the thing to count, not calls

Recursion over a tree is fine, because depth is the tree's height. Recursion over a list is not, because depth is the list's length. Same technique, completely different risk:

The last row is why a recursive walk of a binary search tree is safe in a test and dangerous in production: insert already-sorted data and the tree degenerates into a linked list.

Tail recursion does not save you here

A tail call is one where the recursive call is the entire return expression — nothing is left to do afterwards, so in principle the current frame could be reused instead of stacked. Many languages do exactly that. Java does not:

try {
    System.out.println("sumTail(100000) = " + sumTail(100000, 0));
} catch (StackOverflowError e) {
    System.out.println("sumTail(100000) -> StackOverflowError (no tail-call elimination)");
}

sumTail(100000) -> StackOverflowError (no tail-call elimination)

sumTail is written in perfect tail position and still overflows at 100,000. The JVM keeps every frame because stack frames are observable — Throwable stack traces and the security model have historically depended on them. So in Java, "make it tail-recursive" is not a fix. Converting to a loop is the fix.

When recursion is the right tool, memoise it

The problem with naive recursion on overlapping subproblems is not the stack — it is redoing work. fib(30) recomputes fib(10) thousands of times:

long[] naiveCalls = {0};
long naive = fibNaive(30, naiveCalls);

long[] memo = new long[31];
long[] memoCalls = {0};
long memoised = fibMemo(30, memo, memoCalls);

System.out.println("fib(30) naive     : " + naive + " in " + naiveCalls[0] + " calls");
System.out.println("fib(30) memoised  : " + memoised + " in " + memoCalls[0] + " calls");
System.out.println("fib(30) iterative : " + fibLoop(30));

fib(30) naive     : 832040 in 2692537 calls
fib(30) memoised  : 832040 in 59 calls
fib(30) iterative : 832040

Two and a half million calls against fifty-nine, for the same answer, from the same recursion. The only change is remembering results already computed — O(2^n) becomes O(n).

That is the whole of top-down dynamic programming: recursion plus a cache. The bottom-up form is the loop in fibLoop, which needs no stack at all. Write the recursion first because it is easier to get right, then memoise it, then turn it into a loop only if the depth is a problem.

Reference

Turning linear recursion into iteration — the mechanical version:

// Recursive: depth n, overflows
static long sum(int n) {
    return n == 0 ? 0 : n + sum(n - 1);
}

// Iterative: constant stack
static long sum(int n) {
    long acc = 0;
    for (int i = n; i > 0; i--) acc += i;
    return acc;
}

When the recursion branches and you still need to avoid the stack, move the stack into the heap where you control its size:

// Recursive tree walk — depth is the tree height
static void walk(Node node) {
    if (node == null) return;
    visit(node);
    walk(node.left);
    walk(node.right);
}

// Same traversal, explicit stack — depth limited by heap, not by -Xss
static void walk(Node root) {
    Deque<Node> stack = new ArrayDeque<>();
    if (root != null) stack.push(root);
    while (!stack.isEmpty()) {
        Node node = stack.pop();
        visit(node);
        if (node.right != null) stack.push(node.right);   // right first,
        if (node.left != null) stack.push(node.left);     // so left pops first
    }
}

Guarding a walk over data that might contain a cycle, which is the fix for the "progress" half of the contract:

static void walk(Node node, Set<Node> seen) {
    if (node == null || !seen.add(node)) return;   // add returns false if present
    visit(node);
    for (Node child : node.children()) walk(child, seen);
}

Raising the stack, which is a last resort and worth knowing the shape of:

java -Xss4m MyApp          # per thread, not global

It buys a constant factor — roughly four times the depth — and costs that memory on every thread. It does not change an O(n)-depth algorithm into a safe one.

Scenarios

Parsing deeply nested JSON from an external source. A recursive descent parser has depth proportional to nesting depth, and the nesting depth is chosen by whoever sends the document. That is a denial-of-service vector, not a performance concern: many parsers cap nesting explicitly for this reason.

A recursive toString() on a graph. Two objects referencing each other produce infinite recursion the first time anyone logs one. Base case present, progress absent.

Directory traversal. Depth is the filesystem's depth, normally small — so recursion is fine and clearer. Symlink loops break it, which is why Files.walk takes an explicit depth limit and does not follow links by default.

Quicksort in a library. Recursion on the smaller partition and looping on the larger bounds depth at log n even in the worst case. The JDK's sort does this; a hand-written quicksort recursing on both sides can reach depth n on already-sorted input.

Interviewer's Next Move

1. "How deep can Java recurse?" Around twenty thousand frames on a default 1 MB stack, but it varies with frame size and JVM, so the honest answer is that it is not a number to design against. Depth must be bounded by the algorithm — log n or a structure's height — not by the stack limit.

2. "If a method is tail-recursive, does the JVM optimise it?" No. Java has no tail-call elimination. The JVM keeps frames because stack traces and the historical security model observe them. A tail-recursive method overflows at the same depth as any other, which is why converting to a loop is the actual remedy.

3. "Is StackOverflowError catchable?" Technically yes, and you should not build on it. It is an Error because the stack is in an unknown state; catching it to log and shut down is defensible, catching it to retry is not.

4. "Where did the 2.7 million calls go when you memoised?" They were recomputations of the same subproblems. Naive fib recomputes fib(n-2) inside both branches, giving an exponential call tree over only n distinct values. The cache turns the tree into a DAG, so each value is computed once and the count drops to O(n).

5. "When would you prefer recursion even though a loop exists?" When the problem branches and the recursion mirrors the data — tree and graph traversal, backtracking, divide and conquer. The explicit-stack version of a tree walk is longer and easier to get wrong; the recursive one is the shape of the structure. Prefer it while depth stays logarithmic.

Check Yourself

A recursion has a correct base case and still overflows. Name two causes. The depth is proportional to the input size and the input got large; or the data has a cycle, so some path never approaches the base case. Both satisfy "has a base case" and fail "makes progress".

Why is recursive binary search safe but a recursive linked-list walk not? Binary search halves the range, so depth is log n — about 30 for a billion elements. A list walk visits one node per call, so depth is n, and it overflows at around twenty thousand.

Memoising changed 2,692,537 calls into 59. What changed about the complexity, and what did it cost? O(2^n) became O(n) because each distinct subproblem is computed once instead of once per path to it. The cost is O(n) memory for the cache — the usual trade of space for time.