Eric Campbell 6 min read Engineering

Tail Call Optimization: Stack-Safe Recursion

Every function call adds a frame to the call stack. Each frame stores local variables, return addresses, and execution context. With recursion, this becomes a problem fast.

Key Insights

  • Tail call optimization allows recursive functions to execute in constant stack space by reusing stack frames, but only when the recursive call is the absolute last operation before returning.
  • Most JavaScript engines don’t implement TCO despite ES6 specification, so trampolines provide a practical alternative for stack-safe recursion in production code.
  • The accumulator pattern is the most common technique for converting standard recursion to tail-recursive form, trading elegant return expressions for stack safety.

The Stack Overflow Problem

Every function call adds a frame to the call stack. Each frame stores local variables, return addresses, and execution context. With recursion, this becomes a problem fast.

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

factorial(5);      // 120 - works fine
factorial(10000);  // RangeError: Maximum call stack size exceeded

When you call factorial(10000), the runtime creates 10,000 stack frames before it can start returning values. Each frame waits for the next recursive call to complete. The stack grows linearly with input size.

Here’s what the call stack looks like for factorial(5):

factorial(5) waiting for factorial(4)
  factorial(4) waiting for factorial(3)
    factorial(3) waiting for factorial(2)
      factorial(2) waiting for factorial(1)
        factorial(1) returns 1
      returns 2 * 1 = 2
    returns 3 * 2 = 6
  returns 4 * 6 = 24
returns 5 * 24 = 120

The multiplication happens after the recursive call returns. This is the core issue. The function can’t complete until all nested calls complete, so every frame must persist.

What Makes a Tail Call

A tail call occurs when a function call is the final action a function performs. Nothing happens after the call returns—the result passes directly to the caller.

// NOT a tail call - multiplication happens after the recursive call
function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);  // Must wait for result, then multiply
}

// IS a tail call - recursive call is the last operation
function factorialTail(n, accumulator = 1) {
  if (n <= 1) return accumulator;
  return factorialTail(n - 1, n * accumulator);  // Nothing after this
}

The difference is subtle but critical. In the tail-recursive version, the multiplication happens before the recursive call, passed as an argument. When factorialTail calls itself, there’s no pending work—the caller can be discarded.

Common patterns that break tail position:

// Not tail calls - operations after the recursive call
return 1 + recurse(n - 1);           // Addition after
return recurse(n - 1) * recurse(n - 2);  // Multiple calls
return process(recurse(n - 1));      // Wrapping function
return recurse(n - 1) || defaultValue;   // Logical operator after

How TCO Works Under the Hood

When a runtime implements tail call optimization, it recognizes tail position calls and reuses the current stack frame instead of creating a new one. The mechanics are straightforward:

  1. Evaluate all arguments for the tail call
  2. Replace the current frame’s parameters with new arguments
  3. Jump to the beginning of the function
  4. Repeat until base case

This transforms recursion into something resembling a loop internally. The stack never grows beyond a single frame.

// With TCO, factorialTail(5, 1) executes as:
Frame 1: n=5, acc=1  → tail call with (4, 5)
Frame 1: n=4, acc=5  → tail call with (3, 20)
Frame 1: n=3, acc=20 → tail call with (2, 60)
Frame 1: n=2, acc=60 → tail call with (1, 120)
Frame 1: n=1, acc=120 → return 120

ES6 (ECMAScript 2015) specified proper tail calls. Scheme mandates them. Erlang and Elixir depend on them. But here’s the catch: as of 2024, Safari is the only major browser implementing TCO. V8 (Chrome, Node.js) and SpiderMonkey (Firefox) don’t. The feature exists in the spec but not in practice.

Converting Recursive Functions to Tail-Recursive Form

The accumulator pattern is your primary tool. Instead of building up the result on the way back from recursion, you build it on the way down.

Fibonacci transformation:

// Standard recursive - exponential time, linear stack
function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

// Tail-recursive with accumulators - linear time, constant stack (with TCO)
function fibTail(n, a = 0, b = 1) {
  if (n === 0) return a;
  if (n === 1) return b;
  return fibTail(n - 1, b, a + b);
}

Array sum transformation:

// Standard
function sum(arr, index = 0) {
  if (index >= arr.length) return 0;
  return arr[index] + sum(arr, index + 1);
}

// Tail-recursive
function sumTail(arr, index = 0, accumulator = 0) {
  if (index >= arr.length) return accumulator;
  return sumTail(arr, index + 1, accumulator + arr[index]);
}

Tree traversal transformation:

// Standard in-order traversal - builds result on return
function inOrder(node) {
  if (!node) return [];
  return [...inOrder(node.left), node.value, ...inOrder(node.right)];
}

// Tail-recursive with explicit stack (hybrid approach)
function inOrderTail(node, stack = [], result = []) {
  if (node) {
    stack.push(node);
    return inOrderTail(node.left, stack, result);
  }
  if (stack.length === 0) return result;
  const current = stack.pop();
  result.push(current.value);
  return inOrderTail(current.right, stack, result);
}

Tree traversal is tricky because you have two recursive calls. The solution often involves managing an explicit stack as an accumulator, which blurs the line between recursion and iteration.

Trampolines: TCO Without Runtime Support

Since most JavaScript environments don’t implement TCO, trampolines provide a workaround. A trampoline is a loop that repeatedly calls functions until it gets a non-function result.

// Trampoline utility
function trampoline(fn) {
  return function(...args) {
    let result = fn(...args);
    while (typeof result === 'function') {
      result = result();
    }
    return result;
  };
}

// Thunk wrapper - returns a function instead of making the call
const thunk = (fn, ...args) => () => fn(...args);

// Trampolined factorial
function factorialTramp(n, acc = 1) {
  if (n <= 1) return acc;
  return thunk(factorialTramp, n - 1, n * acc);
}

const factorial = trampoline(factorialTramp);
factorial(10000);  // Works! Returns Infinity (number too large), but no stack overflow

The key insight: instead of making a recursive call directly, return a thunk (a zero-argument function that will make the call). The trampoline loop handles execution, and since it’s a loop, the stack stays flat.

A more ergonomic implementation:

class Bounce {
  constructor(fn, args) {
    this.fn = fn;
    this.args = args;
  }
}

class Done {
  constructor(value) {
    this.value = value;
  }
}

function trampoline(fn) {
  return (...args) => {
    let result = fn(...args);
    while (result instanceof Bounce) {
      result = result.fn(...result.args);
    }
    return result.value;
  };
}

function factorialT(n, acc = 1) {
  if (n <= 1) return new Done(acc);
  return new Bounce(factorialT, [n - 1, n * acc]);
}

const factorial = trampoline(factorialT);

Continuation-Passing Style (CPS)

CPS transforms every function to take an extra argument: a continuation function that receives the result. All calls become tail calls because you pass results forward instead of returning them.

// Direct style parser
function parseExpr(tokens, pos) {
  const left = parseTerm(tokens, pos);
  if (tokens[left.pos] === '+') {
    const right = parseExpr(tokens, left.pos + 1);
    return { value: left.value + right.value, pos: right.pos };
  }
  return left;
}

// CPS style parser
function parseExprCPS(tokens, pos, cont) {
  parseTermCPS(tokens, pos, (left) => {
    if (tokens[left.pos] === '+') {
      parseExprCPS(tokens, left.pos + 1, (right) => {
        cont({ value: left.value + right.value, pos: right.pos });
      });
    } else {
      cont(left);
    }
  });
}

function parseTermCPS(tokens, pos, cont) {
  // Parse number or parenthesized expression
  const token = tokens[pos];
  if (typeof token === 'number') {
    cont({ value: token, pos: pos + 1 });
  } else if (token === '(') {
    parseExprCPS(tokens, pos + 1, (result) => {
      cont({ value: result.value, pos: result.pos + 1 }); // skip ')'
    });
  }
}

// Usage
parseExprCPS([1, '+', 2, '+', 3], 0, (result) => {
  console.log(result.value); // 6
});

CPS makes the control flow explicit. Every function call is in tail position because continuations handle what happens next. The trade-off is severe: CPS code is harder to read and write. Use it when you need stack safety and can’t use simpler alternatives.

When to Use Each Approach

Use iteration when:

  • The recursive structure maps cleanly to a loop
  • Performance is critical (loops are faster than any recursive alternative)
  • Team familiarity with recursion is low

Use tail recursion when:

  • You’re targeting a runtime with TCO (Safari, Scheme, Erlang/Elixir)
  • The algorithm is naturally recursive and accumulator conversion is straightforward
  • You want to express the algorithm recursively for clarity

Use trampolines when:

  • You need stack safety in JavaScript/TypeScript
  • The recursive structure is complex enough that iteration would obscure intent
  • You’re building libraries where input size is unpredictable

Use CPS when:

  • You’re implementing interpreters or compilers
  • You need fine-grained control over execution (async, generators, debuggers)
  • Other approaches don’t fit the problem structure

Performance benchmarks consistently show: iteration > TCO > trampolines > CPS. For a factorial of 1000, iteration might take 0.01ms, trampolines 0.1ms, and CPS 0.3ms. The differences matter at scale but rarely in practice.

My recommendation for production JavaScript: default to iteration for simple cases, use trampolines for complex recursive algorithms, and reserve CPS for specialized use cases like parsers and interpreters. Don’t rely on TCO until V8 implements it—which may be never.

Liked this? There's more.

Every week: one practical technique, explained simply, with code you can use immediately.