# Tailcall
[](https://github.com/alecdotninja/tailcall/actions/workflows/ci.yml)
[](https://crates.io/crates/tailcall)
[](https://docs.rs/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](https://internals.rust-lang.org/t/pre-rfc-explicit-proper-tail-calls/3797/16) is ever stabilized, it will likely be the preferred solution for proper tail calls.
---
## Installation
```toml
[dependencies]
tailcall = "~2"
```
---
## Quick Example
```rust
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
```rust
#[tailcall]
fn f(...) -> T {
if done {
result
} else {
tailcall::call! { f(next_args...) }
}
}
```
Only calls wrapped in `tailcall::call!` are stack-safe.
---
### Mutual Recursion
```rust
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
```rust
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:
```rust
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
```rust
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
```rust
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:
```rust
#[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:
```bash
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.
1. Update the shared workspace version in `Cargo.toml`.
Also update the matching `tailcall` and `tailcall-impl` entries in `[workspace.dependencies]`.
2. Run the release checks:
```bash
cargo test
cargo test --doc
cargo doc --no-deps
```
3. Commit the release version bump.
4. Publish `tailcall-impl` first:
```bash
cargo publish -p tailcall-impl
```
5. Publish `tailcall` after the proc-macro crate is available:
```bash
cargo publish -p tailcall
```
6. Tag the release from `main` and push the commit and tag:
```bash
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).
See [LICENSE-APACHE](LICENSE-APACHE), [LICENSE-MIT](LICENSE-MIT), and [COPYRIGHT](COPYRIGHT) for
details.