Tail Call Optimization Visualization | Call stack and stack overflow

The idea: a call with nothing left to do

Every function call pushes a stack frame that holds its arguments, its local variables and the place to return to. The frame is popped when the function returns. A tail call is a call that is the very last thing a function does: its result is returned as-is, with no work after it. Then the caller's frame is no longer needed, and a compiler can reuse it for the callee. That is tail-call optimization (TCO): the stack stays one frame deep, however many calls are made.

Left: the call stack for normal fact(4) holds four frames, fact(4) waiting for 4 × fact(3), fact(3) waiting for 3 × fact(2), fact(2) waiting for 2 × fact(1), and fact(1) on top. Right: with TCO the stack holds one frame fact_acc(n=1, acc=24) that was reused three times — Normal recursion keeps one waiting frame per call; a tail call with TCO overwrites the same frame.

Normal recursion keeps pending work

def fact(n):
    if n <= 1: return 1
    return n * fact(n - 1)

The last line looks like it ends with a call, but it does not: after fact(n - 1) returns, the frame still has to multiply by n. So each frame waits on the stack with its own n, and fact(5) needs 5 frames at the deepest point. The multiplies run on the way back, as the frames are popped. Stack space is O(n) (Demo: fact(5) normal recursion). The page Recursive Factorial walks through this same function frame by frame.

The accumulator rewrite

To make the call a tail call, move the pending work into an extra argument, the accumulator. It carries the product built so far, so the multiply happens before the call instead of after it:

def fact_acc(n, acc=1):
    if n <= 1: return acc
    return fact_acc(n - 1, acc * n)

Before: fact(4) expands to 4 × (3 × (2 × fact(1))), the multiplies wait for the calls. After: fact_acc(4, 1) becomes fact_acc(3, 4), fact_acc(2, 12), fact_acc(1, 24), and returns 24 with nothing waiting — The accumulator does the multiply on the way down, so nothing is left to do on the way back.

The same trick works for sums, list reversal, counting and most loops written as recursion. Fibonacci needs two accumulators: fib(n, a=0, b=1) calls fib(n - 1, b, a + b).

A tail call alone saves nothing

A tail call only allows the frame to be reused. If the language does not do it, each call still pushes a frame, and each frame just passes the answer down when it returns. fact_acc(5) without TCO needs exactly as many frames as fact(5) (Demo: accumulator, no TCO). Python, Java and most JavaScript engines work this way.

What TCO does

With TCO the compiler turns the tail call into: overwrite the parameters with the new values, then jump to the top of the function. In other words, a loop:

def fact_loop(n):
    acc = 1
    while n > 1:
        n, acc = n - 1, acc * n
    return acc

The frame for fact_acc(5) is reused four times and the stack never grows past 1 (Demo: accumulator + TCO). Stack space is O(1). A call to a different function in tail position can be reused the same way; this general form is called tail-call elimination, and it makes mutual recursion like is_even/is_odd run in constant stack.

Stack overflow

The stack has a fixed size: about 8 MB for a thread on Linux, 512 KB to 1 MB for a Java thread by default, and Python stops at a recursion depth of 1000 (sys.getrecursionlimit()). The canvas shrinks this to 8 frames. fact(10) needs 10, so the 9th push fails with RecursionError (Java: StackOverflowError) (Demo: fact(10) normal). The same fact(10) with TCO runs in one frame (Demo: fact(10) with TCO).

Which languages do it

Language	Tail calls
Scheme	Required by the standard: every tail call is eliminated
Haskell, OCaml, F#, Erlang, Elixir	Eliminated; loops are written as tail recursion
Scala, Kotlin	Self tail calls become loops; `@tailrec` / `tailrec` makes the compiler check it
C, C++, Rust	Often at `-O2`, but not promised; Clang has `[[clang::musttail]]`
JavaScript	In the ES2015 spec, but only Safari ships it
Python, Java	No: write a loop for deep recursion

A cost of TCO: the reused frames are gone from stack traces, which is one reason Python does not do it.

See also Recursive Factorial (the call stack of normal recursion, step by step), Reversing a String, and Plain Recursion vs Memoization vs Tabulation (another way to get rid of deep recursion).

What the page leaves out

The canvas uses a stack of 8 frames and shows one frame per call; real frames differ in size and also hold saved registers and the return address. It leaves out how the jump looks in machine code, continuation-passing style (which makes every call a tail call), trampolines (a loop that calls returned thunks, used where the language has no TCO), and tree recursion like the plain Fibonacci, which cannot be made a single tail call without an explicit stack.