Tailcall

tailcall lets you write deeply recursive functions in Rust without blowing the stack—on stable Rust.

It provides explicit, stack-safe tail calls using a lightweight trampoline runtime, with a macro that keeps usage ergonomic.

The runtime crate is no_std, so it can be used on targets without the standard library.

If the proposed become keyword is ever stabilized, it will likely be the preferred solution for proper tail calls.

Installation

[dependencies]
tailcall = "~2"

Quick Example

use tailcall::tailcall;

#[tailcall]
fn gcd(a: u64, b: u64) -> u64 {
    if b == 0 {
        a
    } else {
        tailcall::call! { gcd(b, a % b) }
    }
}

assert_eq!(gcd(12, 18), 6);

That’s the core API:

mark the function with #[tailcall]
wrap recursive tail calls with tailcall::call!

This runs in constant stack space, even for very large inputs.

When to Use This

tailcall is useful when:

you want to write naturally recursive code without risking stack overflow
converting to loops would make the code harder to read
you’re working with mutual recursion or recursive traversals
you want stack safety without nightly features

It may not be ideal when:

a simple loop is clearer
you need maximum performance (there is some trampoline overhead)

Cost

A common alternative for stack-safe recursion in Rust is to box each step. That can offer a similar interface, but it introduces allocation and indirection on every recursive step.

tailcall keeps each step inline instead, so the main cost is:

an extra indirect call per Thunk::bounce step

In some cases, that cost disappears entirely. If a simple free function or inherent method only tail-calls itself directly, #[tailcall] can lower it to an inline loop.

Rough Performance Shape

On a simple benchmark (relative to a handwritten loop):

handwritten loop: 1.0×
#[tailcall] (inline loop): ~1.0×
#[tailcall] (Thunk runtime): ~3.2× slower
boxed runtime: ~14× slower

This is just a local measurement, but the general pattern holds:

direct self-recursion can optimize down to loop-like performance
the Thunk runtime is slower, but supports more complex cases
heap-allocating approaches are slower again

Tradeoff

The slower path is also the more flexible one.

It’s what allows tailcall to support:

mutual recursion
borrowed-state builders
recursive control flow that doesn’t collapse into a single loop

If your recursion is simple, you get loop-like performance.

If it’s not, you still get stack safety—without paying for heap allocation.

How It Works (Briefly)

Rust does not guarantee tail call optimization. Deep recursion can overflow the stack.

tailcall avoids this by using a trampoline:

each recursive step returns a deferred computation (Thunk)
the runtime repeatedly executes those steps in a loop
no additional stack frames are created

The key operation is:

Thunk::bounce(...) — produces the next step instead of recursing

This turns recursion into iteration under the hood.

Macro Usage

Most users only need the macro.

For simple direct self-recursion, the macro can compile free functions and inherent methods to an inline loop. Mutual recursion and other more complex cases continue to use the hidden Thunk builder automatically.

For methods, that optimized path works by aliasing the receiver once, rebinding the non-receiver arguments as loop state, and turning each direct self tail call into "assign the next arguments, then continue the loop".

Basic Pattern

#[tailcall]
fn f(...) -> T {
    if done {
        result
    } else {
        tailcall::call! { f(next_args...) }
    }
}

Only calls wrapped in tailcall::call! are stack-safe.

If the function only tail-calls itself directly, this pattern is also the one that enables the inline-loop optimization.

Mutual Recursion

use tailcall::tailcall;

#[tailcall]
fn is_even(x: u128) -> bool {
    if x == 0 {
        true
    } else {
        tailcall::call! { is_odd(x - 1) }
    }
}

#[tailcall]
fn is_odd(x: u128) -> bool {
    if x == 0 {
        false
    } else {
        tailcall::call! { is_even(x - 1) }
    }
}

Methods

use tailcall::tailcall;

struct Parity;

impl Parity {
    #[tailcall]
    fn is_even(&self, x: u32) -> bool {
        if x == 0 {
            true
        } else {
            tailcall::call! { self.is_odd(x - 1) }
        }
    }

    #[tailcall]
    fn is_odd(&self, x: u32) -> bool {
        if x == 0 {
            false
        } else {
            tailcall::call! { self.is_even(x - 1) }
        }
    }
}

Mixed Recursion

Only tailcall::call! sites are trampoline-backed:

use tailcall::tailcall;

#[tailcall]
fn sum(n: u64) -> u64 {
    match n {
        0 => 0,
        _ if n % 2 == 0 => {
            let partial = sum(n - 1); // normal recursion
            n + partial
        }
        _ => tailcall::call! { sum(n - 1) },
    }
}

Recommended Pattern: Tail-Recursive Helper

use tailcall::tailcall;

fn factorial(n: u64) -> u64 {
    #[tailcall]
    fn inner(acc: u64, n: u64) -> u64 {
        if n == 0 {
            acc
        } else {
            tailcall::call! { inner(acc * n, n - 1) }
        }
    }

    inner(1, n)
}

Using the Runtime Directly

The macro is just a thin layer over runtime::Thunk.

A runtime::Thunk<T> is a fixed-size deferred value from a computation, so it can live on the stack. It may contain the value directly or a type-erased closure that will eventually produce the value.

On 64-bit targets, the current runtime keeps Thunk at 32 bytes. It does that by storing deferred closures in a small inline slot, which means manual Thunk values and macro-generated helpers can only capture a limited amount of data before construction panics.

Pending Thunk values still preserve normal destructor-on-drop behavior for captured values.

You build a chain of steps, then execute it with .call().

Core constructors

Thunk::value(x) — final result
Thunk::new(f) — deferred computation returning a value
Thunk::bounce(f) — deferred computation returning another Thunk (this is what enables stack safety)

Example

use tailcall::runtime::Thunk;

fn count_down(n: u64) -> u64 {
    build(n).call()
}

fn build(n: u64) -> Thunk<'static, u64> {
    Thunk::bounce(move || {
        if n == 0 {
            Thunk::value(0)
        } else {
            build(n - 1)
        }
    })
}

Thunk::bounce ensures each step returns control to the runtime loop instead of growing the call stack.

What the Macro Generates

At a high level, this:

#[tailcall]
fn f(...) -> T { ... }

becomes:

a wrapper that calls .call()
a hidden builder that returns Thunk<T>

So the macro:

rewrites your function into a trampoline-compatible form
leaves control flow and logic unchanged

Limitations

Explicit Tail Calls

Tail-recursive transitions must be written with tailcall::call!.

Plain recursive calls are left alone, which means they still use the native Rust call stack.

Simple Argument Patterns

#[tailcall] currently only supports simple identifier arguments.

Patterns in function parameters are not rewritten by the macro.

`?` Is Not Supported

The ? operator is not supported inside #[tailcall] functions on stable Rust.

Use match or explicit early returns instead.

Trait Methods

Methods in ordinary impl blocks are supported.

Trait methods are not supported.

`async fn` and `const fn`

#[tailcall] does not support async fn or const fn.

Closure Size Limit

Each deferred closure is stored in a fixed-size inline slot (~16 bytes).

Closures that exceed that size panic when the Thunk is constructed.

Macro-generated helper thunks are subject to the same limit, so functions with enough arguments or captured state can also exceed it.

Development

For normal development, the main local checks are:

cargo test
cargo test --doc
cargo +nightly miri test --all
cargo fmt --all -- --check
cargo clippy --all
cargo doc --no-deps

If you are changing the public docs or runtime internals, it is also worth doing a quick end-to-end smoke test from a fresh crate that depends on the published version from crates.io.

Publishing

tailcall and tailcall-impl are released together.

Update the shared workspace version in Cargo.toml. Also update the matching tailcall and tailcall-impl entries in [workspace.dependencies].
Run the release checks:

cargo test
cargo test --doc
cargo doc --no-deps

Commit the release version bump.
Publish tailcall-impl first:

cargo publish -p tailcall-impl

Publish tailcall after the proc-macro crate is available:

cargo publish -p tailcall

Tag the release from main and push the commit and tag:

git tag vX.Y.Z
git push origin main
git push origin vX.Y.Z

License

Tailcall is distributed under the terms of both the MIT license and the Apache License (Version 2.0).

tailcall-impl 2.2.0