How a Compiler Trick Lets You Recurse Ten Thousand Times Without Crashing

01 / 06

What the call stack actually costs

Every time a function calls another function (or itself), the runtime pushes a new frame onto the call stack. That frame stores the return address, function arguments, and any local variables. When the called function finishes, the runtime pops the frame and jumps back to the return address.

On most systems the stack has a fixed size. Linux defaults to eight megabytes per thread. Windows gives one megabyte. A typical stack frame for a simple function might use 32 to 128 bytes. So a recursive function that calls itself 100,000 times would need somewhere between three and twelve megabytes of stack space, depending on how much each frame holds. That is enough to blow past the default limit and crash the program.

The crash is not a bug in your logic. The code might be perfectly correct. It just ran out of physical room on the stack.

02 / 06

The special case: nothing left to do

Look at two versions of the same function. The first computes factorial the usual way:

factorial(n) { if (n <= 1) return 1; return n * factorial(n - 1); }

When factorial(5) calls factorial(4), it cannot throw away its own frame. It still needs to multiply the result by 5 after the recursive call returns. So five frames sit on the stack at once.

Now rewrite it:

factorial(n, acc) { if (n <= 1) return acc; return factorial(n - 1, n * acc); }

This time, when factorial(5, 1) calls factorial(4, 5), there is genuinely nothing left for the caller to do. The recursive call is the return value. No multiplication after, no formatting, no logging. The last action of the function is the call itself. That position has a name: the tail position.

03 / 06

What the compiler does with a tail call

If the compiler detects that a call is in the tail position, it can perform a quiet optimisation. Instead of pushing a new frame, it reuses the current one. It overwrites the current arguments with the new ones, resets the program counter to the top of the function, and jumps. From the machine's perspective, the recursion just became a loop.

Guy Steele laid this out in a 1977 paper presented at the ACM National Conference, titled "Lambda: The Ultimate GOTO." His argument was that a tail call is semantically identical to a GOTO that passes parameters. If the compiler treats it that way, there is no overhead: no frame allocation, no stack growth, no cleanup on return. The procedure call that everyone assumed was expensive turned out to cost nothing when it happened last.

Steele and Gerald Jay Sussman made this guarantee a requirement of the Scheme programming language. To this day, any conforming Scheme implementation must support proper tail recursion, meaning you can recurse indefinitely without running out of stack.

04 / 06

Why most languages still do not do it

If the trick is that clean, you might wonder why every language does not use it. The reasons are practical, not theoretical.

First, debugging. When a compiler eliminates stack frames, the stack trace shrinks. If your function recurses ten thousand times and crashes on iteration 9,437, the debugger cannot show you the nine thousand frames that led there, because they were overwritten. For language teams that prioritise debugging (Java, Python, most JavaScript engines), that loss of observability is a dealbreaker.

Second, not every recursive pattern qualifies. Mutual recursion (function A calls B, B calls A) needs a more general form of the optimisation. Tree recursion, where a function calls itself twice per invocation, cannot be tail-call optimised at all because neither call is the last action.

Third, specification politics. ECMAScript 2015 (ES6) mandated proper tail calls in strict mode. Safari's JavaScriptCore engine implemented it. V8 (Chrome, Node.js) and SpiderMonkey (Firefox) did not, citing the debugging cost and the complexity it added to their optimising compilers. As of 2026, Safari remains the only major JavaScript engine with the feature, more than a decade after the spec was published.

05 / 06

Languages that guarantee it, and what they get

Scheme requires it. Erlang depends on it: its concurrency model runs millions of lightweight processes as recursive loops, and without tail call elimination every process would blow its stack within seconds. Haskell uses it pervasively because lazy evaluation turns most code into tail-position calls under the hood. Elixir inherits the guarantee from the Erlang VM (BEAM).

In these languages, recursion is not a clever alternative to a loop. It is the loop. A web server in Erlang listens for a request, handles it, then tail-calls itself to wait for the next one. That function never returns. It runs for months, using one frame the entire time.

C and C++ do not guarantee tail call optimisation, but GCC and Clang perform it as a best-effort optimisation at -O2 and above. Rust likewise applies it when it can, though the language spec makes no promise. If you rely on it in these languages, you are relying on a compiler's mood, not a contract.

06 / 06

Trampolines: faking it when the language will not help

In languages without TCO, developers use a pattern called a trampoline. Instead of making the recursive call directly, the function returns a thunk: a zero-argument closure that, when called, performs the next step. A tiny driver loop keeps calling the returned thunks until one of them returns an actual result instead of another thunk.

The recursion never actually happens. Each "call" is just a new closure, and the driver loop runs them iteratively. The stack stays flat. It is uglier than real tail calls, but it works everywhere, and it is the standard workaround in JavaScript, Python, and Java when the recursion depth would otherwise crash the program.

The trampoline is proof that tail call optimisation is not about the compiler being clever. It is about saving you from having to write the loop yourself.