The Call Stack Growing and Unwinding

A recursive method calls itself before it can finish, so Java needs a way to remember every unfinished call at once. It does this with a call stack: a pile of frames, one per active method call. Each frame holds that call's local variables, its parameters, and the exact line it needs to return to. When a method calls another method (or itself), a new frame gets pushed on top. That call runs until it hits a return or another call. Nothing below it on the stack can proceed until the frame on top finishes and pops off, handing its result back down.

Trace fib(4), using fib(n) = fib(n-1) + fib(n-2) with base cases fib(0)=0 and fib(1)=1. Calling fib(4) pushes a frame that immediately needs fib(3), which pushes its own frame needing fib(2), and so on, down to fib(1) or fib(0), where a frame finally returns a value instead of calling again. That frame pops, its answer feeds the waiting frame below it, and the unwinding continues back up until fib(4) itself returns. Counting every call in that branching tree (not just the deepest path) gives the total work done — fib(4) makes 9 calls total, far more than its depth of 4 suggests.

This matters for spotting infinite recursion and stack overflow: every unreturned call sits on the stack taking memory, so a base case that never triggers keeps pushing frames until the stack runs out. It also sets up a common misconception addressed next: even when a recursive call is the last action a method performs, Java still pushes a full new frame for it. There is no shortcut that collapses tail calls, so deep tail recursion overflows the stack exactly like any other deep recursion.