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

tailcall avoids heap allocation.

That is an important difference from some other stack-safe recursion libraries with a similar interface, which build the recursive state machine on the heap.

The main runtime cost here is an indirect call at each Thunk::bounce step. In favorable cases, the optimizer may be able to devirtualize that call, but you should still think of the trampoline as paying for an extra dispatch per bounced step.

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.

Basic Pattern

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

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

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: u128) -> bool {
        if x == 0 {
            true
        } else {
            tailcall::call! { self.is_odd(x - 1) }
        }
    }

    #[tailcall]
    fn is_odd(&self, x: u128) -> 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.

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 (~48 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.1.0