Java 55: Recursion & the Call Stack
easy⏱ 5 mincoursejava
Base case + recursive case
Every recursion needs a base case that returns without recursing, and a recursive case that makes progress toward the base. factorial(0) = 1 is the base; factorial(n) = n * factorial(n-1) is the recursive case. Miss or never reach the base case and you recurse forever → StackOverflowError. Each call's n and partial result live in that call's own frame.
int factorial(int n) {
if (n <= 1) return 1; // base case
return n * factorial(n - 1); // recursive case — frame waits for the result
}
// factorial(4): frames stack up 4,3,2,1 then unwind 1->2->6->24
The stack grows, then unwinds
factorial(4) pushes frames for 4, 3, 2, 1. Each frame is paused mid-expression at n * factorial(n-1), waiting for the inner call. When factorial(1) hits the base case and returns 1, the frames unwind: 2 computes 2*1=2, 3 computes 3*2=6, 4 computes 4*6=24. The deferred multiplications happen on the way down the stack — that pending work is why this isn't tail-recursive.
Tail form & why the JVM doesn't optimize it
A tail-recursive version carries the result in an accumulator so nothing is pending after the recursive call: fact(n, acc) = fact(n-1, n*acc). Many languages turn this into a loop (no stack growth). The JVM does not do tail-call optimization (frames are needed for stack traces / security), so deep recursion still risks overflow — convert hot recursion to an explicit loop or Deque-based stack.
Trace the call stack
Write factorial(n, depth, trace) that records enter n before recursing and exit n=result after, building a trace of the push/pop order. Run factorial(5) and print: the result 120, the max stack depth reached (5), and the full enter/exit trace. Then write the tail-recursive factTail(n, acc) and confirm it returns the same 120 while keeping depth flat at 1 logical pending frame.
Default stack depth ≈ a few thousand frames
The HotSpot default thread stack (-Xss, ~512KB–1MB) holds roughly a few thousand frames before StackOverflowError. Fine for tree depth or divide-and-conquer; dangerous for linear recursion over a big list. When recursion depth tracks input size, prefer iteration or an explicit ArrayDeque worklist.
Quiz: does the JVM optimize tail calls?
Will factTail(100000, 1) (tail-recursive) avoid StackOverflowError on the JVM? No — the JVM does not perform tail-call optimization, so even tail-recursive code grows the stack one frame per call. To handle deep input, rewrite as an explicit loop.