Tail Call Optimization and Recursion: When the Stack Grows and When It Doesn't

Recursion is one of the only places where a program's depth is a real resource: every nested call pushes a frame, and frames occupy a fixed-size stack region that runs out. But there is a special case — the tail call — where the language, compiler, or runtime can collapse the recursion into a loop, making depth a non-issue. Whether that happens is not a matter of language elegance. It is a matter of the machine's stack discipline, and it is decided differently in C, JavaScript, and functional languages.

What "tail position" actually means

A call is in tail position when it is the last thing a function does — its result is returned immediately, with no arithmetic, no conditional, and no bookkeeping applied afterward:

int factorial(int n, int acc) {
    if (n <= 1) return acc;
    return factorial(n - 1, acc * n);   // tail position: result returned as-is
}

The insight is that the current frame is dead the moment the call is made — nothing in it will ever be read again. So instead of pushing a new frame, the callee can reuse the caller's frame and jump. Compilers call this tail call optimization (TCO); for self-calls it's tail recursion elimination, and the call becomes a plain jmp:

factorial:
    cmp    edi, 1
    jle    .L1
.L2:
    imul   esi, edi          ; acc *= n
    dec    edi               ; n--
    cmp    edi, 1
    jg     .L2               ; jump back — no new frame, no growth
.L1:
    mov    eax, esi
    ret

No call, no push, no new frame, no stack growth. The recursion runs as long as the arithmetic holds out, which is effectively forever.

Why C compilers only do it with optimization

Nothing stops GCC or Clang from doing this — but at -O0 they deliberately don't. Two reasons. First, the C standard doesn't require TCO, so there's no correctness obligation; second, and more practically, unoptimized code is meant to be debuggable, and a frame that was optimized away makes the debugger's view of the call stack a lie. At -O2 (or -foptimize-sibling-calls) the frames vanish, and with them the stack-overflow risk of deep tail recursion. The exact same source has two completely different stack behaviors depending on a flag — which is why "C has no TCO" is wrong, and "C doesn't guarantee it" is right.

Why JavaScript engines tried, then mostly stopped

ECMAScript 2015 made proper tail calls mandatory in the spec: engines had to eliminate tail calls in strict mode. Safari's JSC implemented it. V8 implemented it too — then removed it. The reasons are instructive: mandatory PTC broke stack traces (engineers expect to see the recursive frames when a function throws), complicated debugger stepping, and made Error.stack misleading. After years of ecosystem friction, V8 dropped the feature in 2017, and Node browsers still mostly run without guaranteed TCO. The lesson: TCO is not free — the frames you optimize away are also the frames developers inspect.

Trampolines: TCO when the runtime won't give it

When the runtime won't eliminate tail calls, you can simulate the reuse of the stack with a trampoline: a loop that calls functions, each of which returns either a value or the next function to call:

const loop = (fn, ...args) => {
  let result = fn(...args);
  while (typeof result === "function") result = result();  // one frame at a time
  return result;
};
 
const count = (n, acc) => (n === 0 ? acc : () => count(n - 1, acc + 1));
 
loop(count, 1_000_000, 0);   // no stack growth — the loop reuses one frame

Instead of deep recursion you get a flat loop and per-iteration heap closures. It is not as cheap as a compiler-level jmp, but it is the standard trick for languages without TCO — and it works in any language with first-class functions.

When recursion is safe, and when it isn't

Languages that guarantee tail calls — Scheme (spec-mandated), Elixir, Erlang, Kotlin's tailrec — let you recurse millions of levels deep. Languages that don't guarantee them (C, Python, Java, most JavaScript engines) have a hard wall: the runtime's stack limit, typically a few MB, and a "Maximum call stack size exceeded" or segmentation fault when the frame pointer walks past it.

The frame, the tail position, and the guarantee: recursion isn't a performance question — it's a stack discipline question, answered by your compiler's flags and your runtime's commitments.