The Call Stack
When a function calls another, the caller cannot finish yet, so the runtime parks it: a frame holding its arguments and its place in the code goes on a stack, and the callee's frame goes on top. Recursion is the same thing with the function calling itself on a smaller input, so the frames pile up until a base case returns without calling, and then unwind one by one as each waiting frame gets its value. If the recursive call is the last thing a frame does, nothing is waiting, and the frame can simply be replaced, which is why tail recursion behaves like a loop. And without a base case, the pile never stops growing.
factTail(5, 1) carries the running product in acc, so the recursive call is the very last thing a frame does. There is no work waiting below, which means the frame can be replaced by the next one instead of stacking up. Depth stays at 1, exactly like a loop.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 5, with their answers.
factTail(5, 1) makes its tail call. How deep is the stack afterwards?
Answer: Still 1 frame. No work is pending in the caller, so its frame can be dropped as the call is made.
factTail(4, 5) makes its tail call. How deep is the stack afterwards?
Answer: Still 1 frame. No work is pending in the caller, so its frame can be dropped as the call is made.
factTail(3, 20) makes its tail call. How deep is the stack afterwards?
Answer: Still 1 frame. No work is pending in the caller, so its frame can be dropped as the call is made.
factTail(2, 60) makes its tail call. How deep is the stack afterwards?
Answer: Still 1 frame. No work is pending in the caller, so its frame can be dropped as the call is made.
factTail(1, 120) makes its tail call. How deep is the stack afterwards?
Answer: Still 1 frame. No work is pending in the caller, so its frame can be dropped as the call is made.
How it runs, step by step
factTail(5, 1) carries the running product in acc, so the recursive call is the very last thing a frame does. There is no work waiting below, which means the frame can be replaced by the next one instead of stacking up. Depth stays at 1, exactly like a loop.
Tail recursive factorial of 5.
factTail(5, 1) calls factTail(4, 1 x 5 = 5) and has nothing to do with the result but pass it on. The frame is reused: same slot, new arguments.
Tail call with n 4 and acc 5, depth still 1.
factTail(4, 5) calls factTail(3, 5 x 4 = 20) and has nothing to do with the result but pass it on. The frame is reused: same slot, new arguments.
Tail call with n 3 and acc 20, depth still 1.
factTail(3, 20) calls factTail(2, 20 x 3 = 60) and has nothing to do with the result but pass it on. The frame is reused: same slot, new arguments.
Tail call with n 2 and acc 60, depth still 1.
factTail(2, 60) calls factTail(1, 60 x 2 = 120) and has nothing to do with the result but pass it on. The frame is reused: same slot, new arguments.
Tail call with n 1 and acc 120, depth still 1.
factTail(1, 120) calls factTail(0, 120 x 1 = 120) and has nothing to do with the result but pass it on. The frame is reused: same slot, new arguments.
Tail call with n 0 and acc 120, depth still 1.
n is 0: return acc = 120. Nobody is waiting, so this single return finishes the whole computation.
Base case returns 120.
factTail(5) = 120 with a maximum depth of 1 instead of 6. That is why a tail call can be turned into a loop: replace the call with an update of n and acc and jump back to the top. Languages that guarantee this reuse never overflow on tail recursion.
Result 120 with depth 1.
Remember
- A frame is pushed on every call and popped on every return; the deepest point is the space cost.
- The recursive case shrinks the problem, the base case stops it. Missing either one is a bug.
- A tail call has no work left after it, so its frame can be reused: that is a loop in disguise.
Related
What the words mean
- Tail Recursion
- The recursive call is the last action, so the frame can be reused and the stack never grows.
Where this is used
Developer toolsStack traces and debuggers
Every frame stores the return address of the function that called it, so the live frames are a record of how execution reached this line. A Python traceback and gdb's backtrace are both that chain, collected by following the frame links outward from the one that is running; gdb prints it newest first, Python newest last. Nothing else in a running process holds that path, which is why a crash that corrupts the stack is so much harder to diagnose than one that does not.
PerformanceFlame graphs
A sampling profiler such as Linux perf interrupts the program at a fixed frequency, often somewhere between 99 and a few thousand times a second, and copies the entire call stack each time. A flame graph stacks those samples so that width is how often a function was on the stack, which shows where time went without timing a single function. It works only because the stack at any instant is the complete call path, not just the function currently executing.
CompilersRecursive descent parsers
Grammars are recursive: an expression can contain another expression. A parser with one function per grammar rule that calls itself mirrors the grammar line for line, and the nesting depth of the input is tracked by the call stack for free instead of by a structure you maintain. The price is that deeply nested input becomes deep recursion, which is why serde_json caps nesting at 128 levels by default rather than letting the stack decide.
RuntimesGoroutine stacks
An operating system thread gets one fixed contiguous stack reserved when it starts, so a process cannot hold very many of them. Go instead gives each goroutine a stack of about two kilobytes and copies it into a larger block when a call would run off the end. That whole design exists because a call stack has to be contiguous while its eventual depth is not known in advance.
Why it works this way
Why a stack, and why a call costs almost nothing
Returns happen in exactly the reverse order of calls: the most recent caller is always the next one to resume. Last in, first out is not a design choice here, it is the shape of the problem. Because the newest frame is always at the end, entering a function is one subtraction from the stack pointer and returning is one addition, so a local variable costs nothing to allocate. The same locals on the heap would need an allocator on the way in and a collector on the way out.
A stack overflow is not running out of memory
The stack is a separate region whose size is fixed when the thread starts, typically 8 MB on Linux and 1 MB per thread on Windows. You can have gigabytes of free heap and still overflow after a few tens of thousands of frames, because the frames were never competing for that memory. CPython layers a softer limit on top, sys.setrecursionlimit with a default around 1000, so you get a catchable RecursionError instead of the process dying when the real C stack runs out.
Writing a tail call does not mean you get one
Frame reuse is something a compiler has to implement; the shape of your code does not guarantee it. Kotlin only does it when you mark the function tailrec, and it warns you when the call turns out not to be in tail position. return n * fact(n - 1) is not in tail position, because the multiplication still has to happen after the call comes back, so that frame has to stay. Neither the JVM nor CPython eliminates tail calls at runtime, so tailrec is really the Kotlin compiler rewriting the function into a loop before any bytecode exists.
Rewriting recursion as a loop does not remove the stack
Turning a recursive traversal into an iterative one means pushing the pending work onto a stack you declare yourself, so the O(n) space does not go away. What changes is where it lives: your own stack sits on the heap and can grow to whatever memory allows, instead of in the fixed thread stack that overflows. That is the real reason an iterative depth-first search survives a million-node graph while the recursive version does not.
Read more
- Call stackWikipedia
- Tail callWikipedia
- Tail recursive functionsKotlin docs · kotlinlang.org
- sys.setrecursionlimitPython docs · docs.python.org
- Flame graphsBrendan Gregg