Tailcall is a library that adds safe, zero-cost tail recursion to stable Rust.
Eventually, it will be superseded by the become keyword.
Tailcall is distributed as a crate.
Add this to your Cargo.toml:
toml
[dependencies]
tailcall = "0.1.5"
Add the tailcall attribute to functions which you would like to use tail recursion:
```rust use tailcall::tailcall;
fn gcd(a: u64, b: u64) -> u64 { if b == 0 { a } else { gcd(b, a % b) } } ```
For more detailed information (including some limitations), please see the docs.
The core idea is to rewrite the function into a loop using the trampoline approach.
Here is the (slightly reformatted) expansion for the gcd example above:
rust
fn gcd(a: u64, b: u64) -> u64 {
tailcall::trampoline::run(
#[inline(always)] |(a, b)| {
tailcall::trampoline::Finish({
if b == 0 {
a
} else {
return tailcall::trampoline::Recurse((b, a % b))
}
})
},
(a, b),
)
}
You can view the exact expansion for the tailcall macro in your use-case with cargo expand.
Development dependencies, testing, documentation generation, packaging, and distribution are all managed via Cargo.
After checking out the repo, run cargo test to verify the test suite.
The latest documentation can be generated with cargo doc.
Before commiting, please make sure code is formatted canonically with cargo fmt and passes all lints with cargo clippy.
New versions are released to crates.io with cargo publish.
There are a few benchmarks available; currently the benchmarks demonstrate that for single-function tail-recursion, performance is the same as using a loop. Mutual recursion runs, but suffers penalties.
``` $ cargo bench Finished bench [optimized] target(s) in 0.05s Running target/release/deps/tailcall-b55b2bddb07cb046
running 0 tests
test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
Running target/release/deps/bench-b8ab29e7ebef8d8d
running 4 tests test benchoddnessboom ... bench: 6 ns/iter (+/- 0) test benchoddnessloop ... bench: 6 ns/iter (+/- 0) test benchoddnessmutrec ... bench: 4,509,915 ns/iter (+/- 7,095,455) test benchoddnessrec ... bench: 3 ns/iter (+/- 0)
test result: ok. 0 passed; 0 failed; 0 ignored; 4 measured; 0 filtered out ```
If the optimization level is set to zero so that bench_oddness_boom isn't cleverly
optimized away, it blows the stack as expected:
``` $ RUSTFLAGS="-C opt-level=0" cargo bench _boom Finished bench [optimized] target(s) in 0.05s Running target/release/deps/tailcall-b55b2bddb07cb046
running 0 tests
test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
Running target/release/deps/bench-b8ab29e7ebef8d8d
running 1 test
thread 'main' has overflowed its stack fatal runtime error: stack overflow ```
In fact the same occurs when running RUSTFLAGS="-C opt-level=0" cargo bench _mutrec
, indicating mutual recursion can also blow the stack, but the loop and tailrec-enabled
single-function, tail-recursive functions enjoy TCO:
``` $ RUSTFLAGS="-C opt-level=0" cargo bench _loop Finished bench [optimized] target(s) in 0.06s Running target/release/deps/tailcall-b55b2bddb07cb046
running 0 tests
test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
Running target/release/deps/bench-b8ab29e7ebef8d8d
running 1 test test benchoddnessloop ... bench: 4,514,730 ns/iter (+/- 7,498,984)
test result: ok. 0 passed; 0 failed; 0 ignored; 1 measured; 3 filtered out
$ RUSTFLAGS="-C opt-level=0" cargo bench _rec Finished bench [optimized] target(s) in 0.05s Running target/release/deps/tailcall-b55b2bddb07cb046
running 0 tests
test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
Running target/release/deps/bench-b8ab29e7ebef8d8d
running 1 test test benchoddnessrec ... bench: 22,416,962 ns/iter (+/- 16,083,896)
test result: ok. 0 passed; 0 failed; 0 ignored; 1 measured; 3 filtered out ```
Bug reports and pull requests are welcome on GitHub.
Tailcall is distributed under the terms of both the MIT license and the Apache License (Version 2.0).
See LICENSE-APACHE and LICENSE-MIT, and COPYRIGHT for details.