JAVA / METHODS
Recursion, base cases and stack depth
Write recursive Java methods with correct base cases, trace how frames stack and unwind, and know when depth will overflow the stack.
What you will learn
- Place the base case so that every recursive call is guaranteed to reach it
- Trace a recursion as frames that pile up on the way down and unwind in reverse
- Predict maximum depth from the shape: n frames per item, about log n when halving
- Diagnose StackOverflowError as a missing base case or depth that scales with input
Understanding Recursion, base cases and stack depth
A recursive call is an ordinary method call that happens to target the same method. The JVM pushes a new frame holding that call's own parameters and locals, while the caller's frame stays on the stack suspended in the middle of an expression. In the code below, four factorial frames exist at once, and the multiplication in each one cannot complete until the frame beneath it hands back a value, which is why the enter lines appear in descending order and the leave lines in ascending order. There is no leave line for n = 1 because the base case returns before execution ever reaches it.
The base case is the branch that produces a value without calling itself, and it is the only thing that ends the descent. Two conditions must both hold: the base case has to be reachable, and every recursive call has to move the argument strictly closer to it. The test n <= 1 works with a step of n - 1 because n lands exactly on the boundary from any positive start; a test written n == 1 with a step of n - 2 would skip past it for even inputs and never stop. If you cannot say in one sentence why the argument must arrive at the base case, the recursion is not finished.
Each thread gets a fixed block of memory for its stack, commonly 512 KB to 1 MB and adjustable with -Xss, so the number of frames alive at one moment is bounded and exceeding it throws StackOverflowError. Java performs no tail-call elimination, so a recursive call in the last position of a method still costs a full frame; recursion is never a free substitute for a loop. What matters is the shape: visiting n items one call at a time needs n frames, while halving the problem needs about log2 n, which is why a recursive binary search is safe on a million elements and a one-call-per-element walk is not. When depth grows with input size, rewrite the method as a loop or push the pending work onto an explicit Deque instead.
public class RecursionTrace {
static int factorial(int n) {
System.out.println("enter factorial(" + n + ")");
if (n <= 1) { // base case: no recursive call
System.out.println(" base case, returning 1");
return 1;
}
int result = n * factorial(n - 1); // this frame waits here
System.out.println("leave factorial(" + n + ") = " + result);
return result;
}
public static void main(String[] args) {
System.out.println("factorial(4) = " + factorial(4));
}
}A recursive method terminates only if every call provably moves toward a base case, and it is limited by the call stack because every call still in flight holds a frame.
Worked examples
No base case, no bottom
Shows what a missing base case costs and why the failure depth is not a fixed number.
public class NoBaseCase {
static int depth = 0;
static void dive() {
depth++;
dive(); // nothing ever stops this
}
public static void main(String[] args) {
try {
dive();
} catch (StackOverflowError e) {
System.out.println("caught " + e.getClass().getSimpleName());
System.out.println("frames used more than 1000: " + (depth > 1000));
}
}
}Example explained
Line 1dive has no if at all, so no branch returns without recursing and the descent has no bottom.
Line 2depth++ runs before the call, so after the crash it holds the number of frames the JVM managed to fit.
Line 3The catch block can call println only because those thousands of frames were discarded when the error unwound the stack.
Line 4The exact depth reached depends on stack size and frame layout, not on the code, so the example compares against 1000 instead of printing a number you could rely on.
Two base cases, and calls are not depth
Distinguishes the total number of recursive calls from the maximum number of frames alive at once.
public class FibCalls {
static int calls = 0;
static int fib(int n) {
calls++;
if (n == 0) return 0; // first base case
if (n == 1) return 1; // second base case
return fib(n - 1) + fib(n - 2);
}
public static void main(String[] args) {
System.out.println("fib(10) = " + fib(10));
System.out.println("calls = " + calls);
}
}Example explained
Line 1Two base cases are needed because the step reaches down two levels; with only n == 1, fib(2) would call fib(0), which would recurse into negative n forever.
Line 2calls counts invocations, while the stack only holds calls in flight: the deepest chain is fib(10) down to fib(1), ten frames.
Line 3fib(n - 1) is evaluated completely and its frames popped before fib(n - 2) starts, so the two branches never occupy the stack together.
Line 4Total calls follow 2 * fib(n + 1) - 1, so n = 35 costs about 30 million calls while depth stays at 35: this recursion is slow, not deep.
Depth depends on how fast the argument shrinks
Euclid's algorithm reaches its base case in four frames for four-digit inputs.
public class EuclidDepth {
static int gcd(int a, int b) {
System.out.println("frame: gcd(" + a + ", " + b + ")");
if (b == 0) {
return a; // base case
}
return gcd(b, a % b); // b shrinks to a % b
}
public static void main(String[] args) {
System.out.println("result = " + gcd(1071, 462));
}
}Example explained
Line 1b == 0 is the base case, and the a it returns is the answer; every waiting frame simply passes that value back unchanged.
Line 2Each call replaces (a, b) with (b, a % b), and a % b is always smaller than b, which is the argument that the second parameter must reach 0.
Line 3Because the remainder shrinks geometrically, four frames handle inputs above a thousand, while counting down from 1071 by one would need 1071 frames.
Line 4The recursive call is the entire return expression, yet Java still allocates a frame for it; the depth is small here because of the arithmetic, not because of any optimization.
Important notes
StackOverflowError is an Error, not an Exception, so catch (Exception e) will not see it; catching it outside a demonstration is unwise because you cannot tell which half-finished frames were thrown away.
The depth at which recursion fails is not a language constant: it varies with -Xss, the number of locals and parameters in each frame, and whether the method is still interpreted, so never hard-code a safe depth measured on one machine.
Common mistakes
Recursing on the unchanged value, such as return factorial(n) instead of factorial(n - 1): the argument never moves, the base case test is never true, and the method throws StackOverflowError within milliseconds.
Testing the base case with == while the step jumps by more than one, such as if (n == 0) with a call on n - 2: odd inputs go 3, 1, -1, -3 straight past zero, so the method works for even arguments and overflows for odd ones. Writing n <= 0 removes the trap.
Assuming Java turns tail recursion into a loop and then recursing once per list element: small tests pass and the method throws StackOverflowError only on production-sized input, because neither javac nor HotSpot eliminates tail calls.
Try it yourself
Change, predict, then run
Write a recursive int digitSum(int n) that adds the decimal digits of a non-negative int, plus a static counter incremented on entry so you can print how many calls it took. Confirm that digitSum(9045) gives 18 after 5 calls, then explain why n / 10 guarantees the base case is reached.
Open the Java workspaceCheck your understanding
Naive recursion fib(n) = fib(n - 1) + fib(n - 2), with base cases for 0 and 1, makes about 240,000 calls for n = 25, yet it never throws StackOverflowError. Why?
- Because the JVM caches each fib(n) result, so a repeated argument is never recomputed.
- Because HotSpot eliminates the tail calls in fib(n - 1) + fib(n - 2).
- Because only calls in flight occupy frames, and the deepest chain is about n frames.
- Because StackOverflowError happens only when a method has no base case at all.
Show answer
Stack space is consumed by calls alive at the same instant, not by the total number made: fib(n - 1) finishes and its frames pop before fib(n - 2) begins, so the deepest chain is fib(25) down to fib(1). Option 2 is tempting but wrong twice over, since neither call is in tail position (their results are added) and the JVM does not eliminate tail calls anyway; the method is slow, not deep. Option 4 is also wrong, because plenty of methods with correct base cases still overflow once the required depth grows with the input.