the call stack and recursion in java

every method call pushes a frame onto the call stack, and every return pops one: last in, first out. recursion is a method calling itself, which works because each call gets its own frame. it needs a base case to stop, and java will not turn deep recursion into a loop for you, so very deep recursion ends in StackOverflowError.

the picture

a stack of plates. you can only put a plate on top, and only take the top one off. a method call puts a plate on (with that call's local variables written on it), and returning takes it off. whatever plate is on top is the method running right now. everything underneath is paused, waiting.

recursion is when the method on top calls itself: another plate, same recipe, its own copy of the variables. the plates keep piling up until some call can answer without calling again (the base case), and then they come off one by one, each finishing the work it paused.

watching it stack up and unwind

Main.java next to run

1public class Main {
2 static int factorial(int n) {
3 if (n <= 1) {
4 return 1;
5 }
6 return n * factorial(n - 1);
7 }
8
9 public static void main(String[] args) {
10 int result = factorial(4);
11 System.out.println("4! = " + result);
12 }
13}

stdout

·

stack

main

no locals yet

heap

nothing allocated yet.

main calls factorial(4).

step 1/15

a real recording of factorial(4) from the JVM. step through: four frames for the same method pile up, each with its own n, then unwind in reverse as each multiplication finally gets its answer.

notice what each frame is doing while it waits: factorial(4) is stuck in the middle of 4 * factorial(3). the 4 is saved in its frame, the multiplication is on hold, and it resumes the instant factorial(3) returns. that "remember where i was" is exactly what the stack is for.

predict the output

java

void show(int n) {
    if (n == 0) return;
    show(n - 1);
    IO.print(n + " ");
}
 
void main() {
    show(3);
}

the two rules

every recursive method needs both:

a base case that returns without recursing (if (n <= 1) return 1;).
progress: each recursive call must get closer to the base case (factorial(n - 1), not factorial(n)).

break either rule and the calls never stop. the stack is a fixed-size block of memory (1 to 2 MB per thread by default, depending on the platform, and -Xss changes it), so eventually there's no room for the next frame:

text

Exception in thread "main" java.lang.StackOverflowError
	at Main.factorial(Main.java:6)
	at Main.factorial(Main.java:6)
	at Main.factorial(Main.java:6)
	...

how deep you can go before that depends on the frame size and the JIT, more than on your code. stack and heap has a meter you can drag to the edge.

recursion trees and repeated work

some problems split into two smaller copies of themselves, so the calls form a tree. fibonacci is the classic: fib(n) = fib(n - 1) + fib(n - 2).

java

static long fib(int n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
}

fib =

call stack right now (bottom → top)

main

calls 0/15depth 0

press step. each call to fib(n) makes two more calls, until n is 0 or 1.

step 1/31

step through every call fib(5) makes. the amber path is the call stack at that moment: only one branch is ever active. then switch on the cache and watch whole subtrees disappear: the dashed nodes are answers looked up instead of recomputed.

the naive version computes fib(3) twice, fib(2) three times, and it gets exponentially worse. the stack never gets deep (at most n frames), but the tree gets enormous:

naive331,160,281 calls

with a cache79 calls

log scale

calls made to compute fib(40), measured on jdk 25 (apple silicon). the cached version stores each answer in a HashMap the first time it's computed. log scale.

331 million calls (about 370 ms) versus 79 (about 0.03 ms), same answer: 102,334,155. remembering answers you've already computed is called memoization, and it's the first step toward dynamic programming. (and for fibonacci, a plain loop with two variables beats both.)

java doesn't optimize tail calls

a call is a tail call when it's the very last thing a method does: return countDown(n - 1);. some languages notice that the current frame isn't needed anymore and reuse it, so tail recursion runs in constant stack space. java doesn't. every call gets a new frame, tail position or not:

Main.java

public class Main {
    static int depth = 0;
    static long countDown(long n) {
        depth++;
        if (n == 0) return 0;
        return countDown(n - 1); // a tail call. java still pushes a frame.
    }
    public static void main(String[] args) {
        try {
            countDown(1_000_000);
        } catch (StackOverflowError e) {
            System.out.println("StackOverflowError after " + depth + " calls");
        }
    }
}

terminal

$ java Main.java
StackOverflowError after 32710 calls

(32,606 on the next run: the exact depth wobbles with JIT timing.) if the recursion can be millions deep (walking a long linked list, processing a big file line by line), write it as a loop. a loop needs one frame no matter how many times it goes around.

one level deeper:why no tail call optimization?+

HotSpot never did it, and the language has no way to ask for it. a long-cited reason is that parts of the JDK look at the call stack (stack traces, and APIs that ask "who called me?"), and silently removing frames would change what they see. a stack trace with half its frames missing would also be miserable to debug. so if you want constant-space iteration in java, you write a loop. (kotlin's tailrec keyword does exactly that conversion at compile time, on the same JVM.)

keylines

every call pushes a frame, every return pops one. the top frame is what's running.
recursion works because each call has its own frame and its own copy of the locals.
a base case to stop, and progress toward it, every time.
work after the recursive call happens during unwinding, in reverse order.
java never optimizes tail calls. deep recursion overflows, a loop doesn't.