How Recursion Actually Works
The confusing thing about recursion is not that a function calls itself — it is that several copies of the same function are alive at once, each with its own private variables, all waiting on the one above. Once you can see those frames stacked up and collapsing back down, the mystery evaporates and never returns.
This isn't a canned animation. DryRun compiles and executes the code below, then draws every step from the real trace — the same values your machine would produce.
The code
int factorial(int n) {
if (n <= 1) return 1;
int sub = factorial(n - 1);
return n * sub;
}
int sumDigits(int n) {
if (n == 0) return 0;
return (n % 10) + sumDigits(n / 10);
}
int main() {
cout << factorial(5) << endl;
cout << sumDigits(9425) << endl;
return 0;
}factorial stores the recursive result in a named local so the pending multiplication is visible in the frame while the deeper calls run.
How it works, step by step
Each call gets its own frame
Calling factorial(5) creates a frame holding n = 5. The nested call creates a separate frame with n = 4. Both exist simultaneously and neither can see the other's n — that independence is what makes recursion work at all.
The caller is suspended, not finished
When factorial(5) reaches the recursive call, it stops mid-statement. The multiplication n * sub has not happened yet and will not happen until the inner call returns a value. Five frames pile up before a single multiplication occurs.
The base case is the only exit
if (n <= 1) return 1; is the sole path that returns without recursing. Without it, or with a condition the arguments never satisfy, frames accumulate until the stack is exhausted and the process dies.
Results flow back down the pile
The deepest frame returns 1, which lets the frame above compute 2 * 1, which lets the next compute 3 * 2, and so on. Watching each frame wake up, receive its value, and finish is the single most useful thing you can do for your understanding of recursion.
Every recursive call must make progress
factorial(n - 1) and sumDigits(n / 10) both move strictly towards the base case. If an argument can stay the same or move away, the recursion is unbounded regardless of how correct the base case looks.
Complexity
One frame per pending call means recursion depth is a real memory cost, not a bookkeeping detail; a recursion that is linear in depth will overflow the default stack somewhere around a few hundred thousand frames, long before it runs out of time.
Common bugs
A base case the arguments never hit
if (n == 0) in factorial looks fine until someone calls factorial(-1), which recurses to -2, -3, and downward forever. Use n <= 1 or validate the input. Test the boundary and one step past it, not just the happy path.
Recursing without changing the argument
Calling helper(n) instead of helper(n - 1) inside itself produces an identical frame every time. In a step-through this is unmistakable: the same parameter value on frame after frame, growing until the crash. Reading the code for the same bug can take much longer.
Expecting a local variable to persist across calls
int count = 0; inside a recursive function is reinitialised in every frame, so it never accumulates anything. If you need shared state, pass it by reference or return it up the chain — do not reach for a static, which then leaks between separate top-level calls.
Treating stack overflow as a logic error
A crash with no output often means the recursion simply went too deep, not that the algorithm is wrong. Recursive quicksort on sorted input, DFS on a long chain, and naive tree recursion on a degenerate tree all fail this way. The fix is an iterative version or a bound on depth, not a change to the recurrence.
Each of these is easier to see than to describe — step through it and watch the values change. Run it in DryRun.
Frequently asked
What is a base case in recursion?
The condition under which the function returns a value directly instead of calling itself. It is what stops the recursion — every recursive call must eventually reach it. A missing or unreachable base case means frames pile up until the call stack is exhausted and the program crashes.
Why does recursion use more memory than a loop?
Because every pending call keeps a stack frame alive, holding its parameters, local variables, and the position to return to. A loop reuses one set of variables, while a recursion n levels deep holds n complete frames simultaneously. That is the O(n) space cost people mean when they say recursion is expensive.
What causes a stack overflow?
Recursion that goes deeper than the call stack can hold — either because of a missing base case, an argument that never approaches it, or a legitimately deep recursion on a large input. The default stack is typically a few megabytes, which runs out somewhere in the hundreds of thousands of frames.
Is recursion slower than iteration?
Usually somewhat, because each call has the overhead of setting up and tearing down a frame. The bigger cost is memory. Compilers can eliminate that overhead for tail-recursive functions by turning them into loops, but factorial as written here is not tail recursive — the multiplication happens after the call returns.