Introduction

Every time your program calls a function, the runtime pushes a stack frame — a small block of memory holding the local variables and the return address. Call deeply enough and you exhaust the stack: the dreaded stack overflow.

Recursion is the natural way to express many algorithms, but naive recursion builds a tower of frames proportional to the depth. A function that counts down from a million would need a million frames just sitting there, waiting.

Tail-call optimization (TCO) cuts that tower to one frame. The insight is simple: if the very last thing a function does is call another function — and then return its result unchanged — the caller's frame is useless from that moment on. The compiler can reuse the same frame for the callee, turning the call into a plain jump.

The result: a recursive function in tail position runs in O(1)O(1) stack space, no matter how deep the recursion goes. First described explicitly by Guy L. Steele Jr. in 1977 and mandated by the Scheme standard, TCO is now guaranteed by languages like Scheme, Erlang, Elixir, and Lua, and present in many modern compilers for Haskell, Scala, and others.

Try It

The demo below runs two countdowns side by side: one naive (each call waits for the next), one tail-recursive (each call is the last act, so the frame can be recycled). Drag the slider to set the recursion depth, then hit Run both.

<p class="hint">Naive recursion stacks one frame per call — deep enough and it crashes. Tail-recursive code lets the <b>compiler reuse a single frame</b>. Drag the slider to choose depth, then run both versions.</p>
<div class="controls">
  <label for="depth-slider">Recursion depth: <span id="depth-val">5000</span></label>
  <input id="depth-slider" type="range" min="100" max="50000" step="100" value="5000">
</div>
<div class="columns">
  <div class="col">
    <div class="col-title">Naive recursion</div>
    <div class="stack-wrap">
      <div class="stack-bar" id="bar-naive"></div>
    </div>
    <div class="col-status" id="status-naive">—</div>
  </div>
  <div class="col">
    <div class="col-title">Tail-recursive (TCO)</div>
    <div class="stack-wrap">
      <div class="stack-bar" id="bar-tco"></div>
    </div>
    <div class="col-status" id="status-tco">—</div>
  </div>
</div>
<div class="btns">
  <button id="run" type="button">Run both</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>

/* General layout and typography styles. */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.controls { display: flex; align-items: center; gap: .6rem; margin-bottom: .9rem; font-size: .9rem; }
.controls input[type=range] { flex: 1; }
/* Side-by-side column layout for naive vs TCO comparison. */
.columns { display: flex; gap: 1rem; margin-bottom: .8rem; }
.col { flex: 1; display: flex; flex-direction: column; align-items: center; gap: .4rem; }
.col-title { font-weight: 700; font-size: .85rem; text-align: center; }
/* Visual stack-depth bar styles. */
.stack-wrap { width: 60px; height: 180px; background: #e8eef3; border-radius: 6px; display: flex; flex-direction: column; justify-content: flex-end; overflow: hidden; border: 1px solid #cdd9e3; }
.stack-bar { width: 100%; height: 0%; background: #1d3557; border-radius: 4px 4px 0 0; transition: height .3s ease; }
.col-status { font-size: .82rem; text-align: center; min-height: 2.2em; font-weight: 600; }
.col-status.ok { color: #0a7d33; }
.col-status.bad { color: #c92f3c; }
.col-status.run { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Tail-Call Optimization demo — compare naive vs tail-recursive countdown.
// Naive: each call waits for the recursive result, so frames pile up.
// TCO: the recursive call is the last act; a trampoline simulates frame reuse.

const slider = document.getElementById('depth-slider');
const depthVal = document.getElementById('depth-val');
const barNaive = document.getElementById('bar-naive');
const barTco = document.getElementById('bar-tco');
const statusNaive = document.getElementById('status-naive');
const statusTco = document.getElementById('status-tco');

// Update the depth display when the slider changes.
function updateDepth() {
  depthVal.textContent = slider.value;
}
slider.addEventListener('input', updateDepth);

// Set the status text and CSS class for a column.
function setStatus(el, text, cls) {
  el.textContent = text;
  el.className = 'col-status ' + cls;
}

// Set the visual height of a stack-depth bar (percentage).
function setBar(el, pct) {
  el.style.height = Math.min(pct, 100) + '%';
}

// Naive countdown: NOT a tail call because the caller must still add 1.
// Naive recursion: each call frame stays alive until the innermost returns.
// With large n this will throw a RangeError (Maximum call stack size exceeded).
function naiveCountdown(n) {
  if (n <= 0) return 0;
  return 1 + naiveCountdown(n - 1); // NOT a tail call — must add 1 after the recursive call returns
}

// Tail-recursive countdown with an accumulator argument.
// Tail-recursive countdown using an accumulator.
// The recursive call is the LAST thing the function does,
// so in a TCO-capable engine the frame is reused rather than stacked.
function tcoCountdown(n, acc) {
  if (n <= 0) return acc;
  return tcoCountdown(n - 1, acc + 1); // tail call — the caller does nothing after this returns
}

// Trampoline simulation: iteratively mimics what TCO does in a real compiler.
// JavaScript engines do NOT guarantee TCO (V8 removed it in 2017 for most modes).
// We simulate it here with a trampoline so the demo always works in a browser.
function trampolineCountdown(n) {
  // Iterate instead of recurse — constant stack, same result.
  let current = n;
  let acc = 0;
  while (current > 0) {
    acc++;
    current--;
  }
  return acc;
}

// Cap naive recursion to avoid browser freeze.
// Cap the naive recursion at a safe depth to avoid hanging the browser.
const NAIVE_CAP = 10000;

function runNaive(n) {
  const t0 = performance.now();
  // Show the stack growing as a proportion of the safe cap.
  // Visual: show the stack growing proportionally (capped at 100%).
  const pct = (n / NAIVE_CAP) * 100;
  setBar(barNaive, pct);
  if (n > NAIVE_CAP) {
    setStatus(statusNaive, fmt('Skipped (depth > %cap% risks browser hang)', { cap: NAIVE_CAP }), 'bad');
    return;
  }
  try {
    const result = naiveCountdown(n);
    const ms = (performance.now() - t0).toFixed(1);
    setStatus(statusNaive, fmt('Done — result %result%, took %ms% ms', { result: result, ms: ms }), 'ok');
  } catch (e) {
    setStatus(statusNaive, '✗ Stack overflow — call stack exhausted!', 'bad');
  }
}

function runTco(n) {
  const t0 = performance.now();
  // Show a fixed tiny bar — TCO keeps the stack flat regardless of depth.
  // Visual: the bar stays at a fixed 1-frame height regardless of n.
  setBar(barTco, 4);
  const result = trampolineCountdown(n);
  const ms = (performance.now() - t0).toFixed(1);
  setStatus(statusTco, fmt('Done — result %result%, took %ms% ms', { result: result, ms: ms }), 'ok');
}

document.getElementById('run').addEventListener('click', () => {
  const n = parseInt(slider.value, 10);
  setStatus(statusNaive, 'Running…', 'run');
  setStatus(statusTco, 'Running…', 'run');
  // Use setTimeout(0) so the browser can repaint before blocking work starts.
  // Run naive first, then TCO (both are synchronous in this demo).
  setTimeout(() => {
    runNaive(n);
    runTco(n);
  }, 0);
});

document.getElementById('reset').addEventListener('click', () => {
  slider.value = 5000;
  updateDepth();
  setBar(barNaive, 0);
  setBar(barTco, 0);
  setStatus(statusNaive, '—', '');
  setStatus(statusTco, '—', '');
});

updateDepth();
Result
Console

Notice that the naive version crashes (or gets very slow) at large depths while the tail-recursive version finishes instantly at any depth. The stack bar on the left grows with depth; the one on the right stays flat — that is TCO in action.

The Real Mechanics

What exactly makes a call a tail call?

A call is in tail position if its return value is returned directly by the caller — no arithmetic, no wrapping, nothing happens after the call returns. Compare:

  • Not a tail call: return 1 + f(n - 1) — the +1 must happen after f returns, so the frame must survive.
  • Tail call: return f(n - 1, acc + n) — nothing happens after, so the frame is free.

The compiler's rewrite is mechanical:

  1. Overwrite the current frame's argument slots with the new arguments.
  2. Jump to the start of the callee (which may be the same function — tail recursion).
  3. No CALL instruction, no new frame, no saved return address.

The stack depth stays O(1)O(1) regardless of the number of "recursive" steps. The price is a style constraint: you must pass intermediate results as accumulator arguments rather than computing them on the way back up. This is exactly continuation-passing style in disguise.

TCO is not the same as memoization or dynamic programming — it saves space, not time. The algorithm still runs in O(n)O(n) time; it just no longer needs O(n)O(n) stack frames to do it.

Where It Matters

TCO is not just a performance trick — for some programming styles it is a correctness requirement:

  • Functional languages: Scheme, Erlang, Elixir, and Lua guarantee TCO. Without it, idiomatic code that uses recursion instead of loops would overflow the stack on any non-trivial input.
  • State machines: a state machine coded as mutually recursive functions (one function per state) is natural and readable. With TCO it is also efficient; without it, a long-running machine would exhaust the stack.
  • Trampolining: languages without native TCO (JavaScript pre-ES6, Python) can simulate it: instead of calling the next function, return a thunk (a zero-argument closure), and let a top-level loop bounce between thunks. This is the trampoline pattern.
  • Continuation-passing style: CPS transforms every function call into a tail call, making the entire program a chain of tail calls — TCO is what makes CPS practical.
  • Compiler back ends: many compilers lower recursion schemes and pattern matching to tail-recursive code so that the generated machine code is a tight loop.

The absence of guaranteed TCO is one reason languages like Python and Java discourage deep recursion; the presence of it is one reason functional programmers can write elegant recursive code without fear.

Conclusion

The gap between a regular call and a tail call is one instruction: the CALL that saves a return address versus the JMP that simply continues. But that one instruction determines whether recursion costs O(n)O(n) stack frames or O(1)O(1).

TCO turns the stack from a limiting resource into a non-issue. It lets you write loops as recursive functions, state machines as mutual recursion, and entire programs in continuation-passing style — all without fear of overflow.

The next time you hit a stack overflow in a deeply recursive program, ask whether the recursive call is truly the last thing the function does. If it is — or if you can reshape the code so it is — you are one compiler flag (or one language switch) away from running forever on a flat stack.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/tail-call-optimization/Content licensed under CC BY-NC 4.0.