The cost of pending calls
Ordinary recursion grows the call stack because each call must wait for its child to return before finishing its own work. Deep recursion can overflow the stack. Tail recursion is a special shape that can avoid this growth.
What makes a call a tail call
A recursive call is in tail position when it is the very last action of the function, with nothing left to do after it returns.
- A tail recursive routine carries its running result forward as an argument, often called an accumulator.
- There is no pending addition or multiplication waiting on the result of the recursive call.
Tail call optimization
When a compiler or interpreter performs tail call optimization, it reuses the current stack frame for the recursive call instead of pushing a new one.
- The recursion then runs in constant stack space, behaving like a loop.
- Stack overflow stops being a risk no matter how deep the logical recursion goes.
Not guaranteed everywhere
Many languages do not perform this optimization, so a tail recursive function can still overflow. When the optimization is absent, rewriting as an explicit loop gives the same guarantee.
Key idea
A tail recursive call is the function's last action and carries results in an accumulator, letting compilers that support tail call optimization reuse one frame and run in constant stack space.