Tail Calls and Deep Recursion

This guide answers one task: use WebAssembly’s tail call instructions so that recursive code runs in constant stack space instead of trapping — and know which code actually benefits.

Prerequisites

  • [ ] A toolchain that emits the instructions: LLVM 18+, Emscripten 3.1.60+.
  • [ ] An engine with the proposal: Chrome 112+, Firefox 121+, Safari 18.2+, Node 20+.
  • [ ] Code that recurses deeply, or an interpreter dispatch loop.
  • [ ] A detection check, because support is broad rather than universal.

The stack, and why it runs out

A WebAssembly instance has a call stack managed by the engine, and it is finite. Each call adds a frame holding the function’s locals and its return address; when the stack is exhausted the engine traps.

RuntimeError: Maximum call stack size exceeded

The limit is engine-specific and typically allows tens of thousands of frames — enough for ordinary code and not enough for an algorithm whose recursion depth follows its input. A tree walk over a deeply nested document, a recursive descent parser on hostile input, or an interpreter whose dispatch is a chain of calls all reach it.

The tail call instructions, return_call and return_call_indirect, replace the current frame rather than adding to it. A function ending in a tail call therefore runs in constant stack space no matter how many times it calls itself.

Add a frame, or replace it An ordinary call pushes a new frame and returns to the caller afterwards. A tail call replaces the current frame, so a chain of tail calls uses one frame regardless of length. call frame 1 frame 2 frame 3 frame 4 … until the stack is exhausted return_call frame 1 reused for call 2, call 3, call 4 … call 10,000,000 The distinction is not performance — a tail call is about the same speed as an ordinary one — but whether the program can run at all.

Which calls qualify

A call is in tail position when its result is immediately returned and nothing happens afterwards. That is a narrower condition than it sounds, and the usual mistakes are worth naming.

// tail position: the result is returned directly
fn walk(node: &Node, acc: u64) -> u64 {
    match node.next {
        Some(ref n) => walk(n, acc + node.value),     // tail call
        None => acc,
    }
}

// NOT tail position: there is work after the call
fn sum(node: &Node) -> u64 {
    match node.next {
        Some(ref n) => node.value + sum(n),           // the addition happens after
        None => node.value,
    }
}

The second form accumulates frames however the compiler is configured, because the result of the recursive call is used rather than returned. Converting it to the first form — by threading an accumulator through the parameters — is the standard transformation, and it is what makes tail calls applicable to code that was not written for them.

A call in a try block is also not in tail position, because the handler must remain on the stack. That interaction surprises people combining this proposal with exception handling.

Enabling it

For Rust and C the feature is a target flag, and it must reach both the compiler and any post-processing tool.

# Rust
RUSTFLAGS="-C target-feature=+tail-call" cargo build --release --target wasm32-unknown-unknown

# C / C++ with Emscripten
emcc app.c -mtail-call -O3 -o app.js

# wasm-opt must be told the feature is allowed, or it rejects the input
wasm-opt -Oz --enable-tail-call -o dist/app.wasm build/app.wasm

Forgetting the wasm-opt flag produces a validation error in the middle of the build, which is at least loud. Forgetting the compiler flag produces a module that works and still uses ordinary calls, which is silent — and is why the verification step below matters.

Interpreter dispatch, the classic use

The case that motivated much of the proposal is an interpreter whose instruction dispatch is a chain of calls: each handler ends by calling the handler for the next instruction. Without tail calls that chain grows the stack once per instruction executed, which is immediately fatal.

typedef void (*handler)(VM *vm);

static void op_add(VM *vm) {
    vm->sp[-2] += vm->sp[-1];
    vm->sp -= 1;
    __attribute__((musttail)) return DISPATCH(vm);   // becomes return_call_indirect
}

musttail in Clang asks the compiler to guarantee a tail call and to fail the build if it cannot, which is the right strictness here — a dispatch loop that silently stops being tail-recursive is a program that works on small inputs and crashes on real ones.

This pattern is why language implementations targeting WebAssembly waited for the proposal, and why several interpreters became viable in the browser only once it shipped.

Dispatch as a chain of tail calls Each instruction handler performs its work and tail-calls the handler for the next instruction. The frame is reused for every instruction, so a program of any length runs in constant stack space. op_add does its work tail op_load same frame op_branch same frame … millions of instructions stack depth: 1 Without the proposal this chain is a stack overflow after a few tens of thousands of instructions, which for an interpreter is immediately.

Converting recursion to tail form

Most recursive code is not in tail form to begin with, and the transformation is mechanical enough to be worth knowing rather than rediscovering.

The general technique is to introduce an accumulator parameter carrying whatever the caller would have done with the result. Work that happened after the recursive call moves before it, applied to the accumulator.

// not tail recursive: the multiply happens after the call
fn factorial(n: u64) -> u64 {
    if n <= 1 { 1 } else { n * factorial(n - 1) }
}

// tail recursive: the multiply happens before, into the accumulator
fn factorial_tail(n: u64, acc: u64) -> u64 {
    if n <= 1 { acc } else { factorial_tail(n - 1, acc * n) }
}

For a tree traversal the accumulator is usually an explicit work list, which is the point at which the transformation stops being free: you are managing a stack by hand, in linear memory, and the tail call only removes the frame overhead rather than the bookkeeping.

fn walk_iter(root: &Node, todo: &mut Vec<&Node>, acc: &mut u64) {
    todo.push(root);
    while let Some(n) = todo.pop() {
        *acc += n.value;
        for child in &n.children { todo.push(child); }
    }
}

That loop version needs no tail calls at all and works on every engine, which is worth noticing: for a traversal, converting to an explicit work list is often simpler than arranging tail calls and has no support requirement. Tail calls earn their place where the call graph is genuinely mutual — a dispatch loop, a state machine with a function per state — and a work list would mean reimplementing control flow rather than data flow.

Verify the instructions are there

A build that was supposed to use tail calls and does not is indistinguishable from one that does, until the input gets deep enough. Check the disassembly.

wasm-objdump -d dist/app.wasm | grep -c 'return_call'
# 18
# and the behavioural test, which is the one that matters
node --experimental-wasm-return_call test.mjs
depth 1000000: ok, stack depth constant

Write that behavioural test with a depth far beyond what an ordinary stack allows — a million is a good number — so the test fails loudly if the feature silently stops being used.

What the tail call removes A recursive call in tail position normally pushes another frame, so depth is bounded by the stack. A tail call reuses the frame, and the depth stops mattering. ordinary call one frame per level — exhausts the stack at roughly 12,000 deep return_call one frame depth is unbounded; the frame is reused at every level This is what makes a straightforward compiler for a functional language viable on this target. Only a call in genuine tail position qualifies — a call whose result is used afterwards cannot be one.

Gotchas

  • The call is not actually in tail position. An addition, a ?, a destructor or a try after the call all disqualify it.
  • Compiler flag missing. The build succeeds and uses ordinary calls.
  • wasm-opt without --enable-tail-call. Rejects the input with a validation error.
  • Assuming the compiler will find them. Use musttail where the guarantee matters.
  • Rust destructors. A value needing a drop at the end of the function prevents the tail call; scope the value so it is dropped before.
  • Assuming universal support. Broad and not complete; detect and keep a fallback.

Performance note

A tail call costs approximately the same as an ordinary call — the saving is the frame, not the time. In a dispatch-loop benchmark the tail-call build ran within 3% of the ordinary-call build for shallow inputs and completed inputs of any depth, where the ordinary build trapped at roughly 42,000 frames. That is the shape of the benefit: not faster, but able to run.

Frequently Asked Questions

Can I get this without the proposal? By transforming the recursion into a loop with an explicit stack in linear memory, which is what interpreters did before and which works everywhere. It is more code and it puts stack management in your hands, which for a hot dispatch loop costs measurable performance.

Does it help ordinary application code? Almost never. Iterative code has no deep recursion, and a tree walk over a document of realistic depth fits comfortably. This proposal serves language implementations and algorithms whose depth follows the input.

Does a tail call show up differently in a stack trace? Yes, and it is a real cost: because the frame is replaced, the intermediate calls are not in the trace. A dispatch loop that tail-calls through a million handlers reports a trace of depth one, which is correct and unhelpful when something fails. Keep your own breadcrumb — the current instruction pointer, the current state — if you need to know where you were.

How deep can the stack go without it? Engine-specific and roughly 10,000 to 50,000 frames, varying with frame size. Treating any specific number as safe is unwise; if depth follows input, either bound the input or use tail calls.

If your code is not an interpreter or a compiler target, you can safely ignore this proposal; if it is, nothing else substitutes for it.

← Back to Post-MVP Wasm Proposals in Practice