Trampolines and algebraic Fibonacci in Rust

In previous articles, we explored tail recursion and the trampoline device in JavaScript and Go as a workaround for missing tail call optimization (TCO).

This article continues the idea, but now in Rust.

Rust is interesting here because it makes the algebraic structure explicit.

In this post, we’ll clarify whether Rust supports TCO, implement a trampoline in idiomatic Rust, write a generic Fibonacci implementation, and finally compute Fibonacci numbers over strings.

Does Rust support tail call optimization?

Rust does not guarantee tail call optimization. Even if a function is tail-recursive, you must assume that each recursive call consumes stack space.

Why?

• Rust compiles via LLVM, which may eliminate tail calls but does not guarantee it.
• Rust has deterministic destruction (Drop), which may require stack frames to remain alive.
• Rust favors predictable performance over implicit optimizations.

Deep recursion in Rust can overflow the stack.

If we want recursion without stack growth, we can use the same workaround mentioned in the previous articles: a trampoline.

Return of the trampoline

Instead of calling itself recursively, a function returns a thunk. That is a function describing the next step. A trampoline repeatedly executes these steps until a final value appears.

The trampoline

enum Bounce<T> {
    Done(T),
    More(Box<dyn FnOnce() -> Bounce<T>>),
}

fn trampoline<T>(mut b: Bounce<T>) -> T {
    loop {
        b = match b {
            Bounce::Done(value) => return value,
            Bounce::More(step) => step(),
        };
    }
}

Despite the name, nothing magical happens here:

• Done(value) → computation finished
• More(step) → keep going

The loop replaces recursion.

Tail-recursive Fibonacci as state

If we look back at the tail-recursive logic from the first post:

(previous, current) → (current, previous + current)

Instead of building stack frames, we carry forward state.

A generic Fibonacci

Fibonacci needs only an addition-like operation and two seed values. No ordering, no multiplication, not even numbers in the usual sense.

In Rust, we can express this precisely.

use std::ops::Add;

fn fib_thunk<T>(n: usize, f0: T, f1: T) -> Bounce<T>
where
    for<'a> &'a T: Add<&'a T, Output = T>,
    T: 'static,
{
    match n {
        0 => Bounce::Done(f0),
        1 => Bounce::Done(f1),
        _ => Bounce::More(Box::new(move || {
            let next = &f0 + &f1;
            fib_thunk(n - 1, f1, next)
        })),
    }
}

fn fib<T>(n: usize, f0: T, f1: T) -> T
where
    for<'a> &'a T: Add<&'a T, Output = T>,
    T: 'static,
{
    trampoline(fib_thunk(n, f0, f1))
}

We chose a 'static trait object for simplicity. This prevents using T that borrows non-'static data. If we parameterized Bounce with a lifetime, we could remove the 'static bound.

What does this bound mean?

for<'a> &'a T: Add<&'a T, Output = T>

It says:

references to T can be added together to produce a new T.

This is exactly what large mathematical types do:

• big integers
• rational numbers
• matrices
• vectors

We only read values and create a new result. No mutation required.

This code now works for e.g. num_bigint::BigInt without changing a single line of logic. It's the kind of abstraction Rust’s trait system was designed to express.

Fibonacci is algebra, not arithmetic

At this point we can state the key insight:

The Fibonacci algorithm does not fundamentally operate on integers. It operates on any type whose references support addition. Rust’s trait system allows us to express this algebraic requirement precisely.

Mathematically, Fibonacci works for any structure with an addition operation. Rust lets us encode that idea directly in the type system.

If Fibonacci truly depends only on addition, then numbers should be optional. Let’s test that claim.

A surprising example: Fibonacci over strings

Rust prevents us from implementing:

&String + &String

directly because of the orphan rule:

You may implement a trait for a type only if either the trait or the type is defined in your crate.

If both the trait and the type come from other crates, the implementation is forbidden.

But we can wrap String in our own type.

The Cat type

#[derive(Clone, Debug)]
struct Cat(String);

impl From<&str> for Cat {
    fn from(s: &str) -> Self {
        Self(s.to_owned())
    }
}

impl<'a, 'b> Add<&'b Cat> for &'a Cat {
    type Output = Cat;

    fn add(self, rhs: &'b Cat) -> Cat {
        let mut out =
            String::with_capacity(self.0.len() + rhs.0.len());
        out.push_str(&self.0);
        out.push_str(&rhs.0);
        Cat(out)
    }
}

Addition now means concatenation:

ab + cd = abcd

Fibonacci, but with cats

Let’s compute:

F(0) = me
F(1) = ow

fn main() {
    let result = fib(
        6,
        Cat::from("me"),
        Cat::from("ow"),
    );

    println!("{:?}", result);
}

Step-by-step

The structure follows Fibonacci exactly. Only the meaning of addition changed.

The algebra hiding underneath

Notice that the code doesn't care about numbers. By using the Add trait, we've generalized the algorithm into an algebraic structure:

(T, +)

Any type that defines addition can generate a Fibonacci sequence. Rust’s trait bounds let us express this requirement exactly. This is the FP move: define the algorithm by its required structure, not by a concrete type.

What this costs us

While the trampoline saves your stack, it’s not free. You’re trading stack space for heap allocations by boxing a closure on every single step. If you need a high-performance Fibonacci in Rust, you’d use a for loop. We’re doing this for the conceptual elegance and the TCO workaround.

The future: explicit tail calls

While we can use trampolines today, there is a keyword for this exact purpose: become.

In future versions of Rust, we could potentially replace our Bounce enum and heap-allocated Box closures with a single keyword that guarantees the stack frame is reused:

// Potential future syntax
fn fib_native<T>(n: usize, f0: T, f1: T) -> T
where
    T: Add<Output = T>,
{
    match n {
        0 => f0,
        1 => f1,
        _ => become fib_native(n - 1, f1, f0 + f1),
    }
}

It eliminates the performance penalty of heap allocations.

Landing on four feet

Trampolines began as a workaround for missing tail call optimization. In Rust, they reveal something deeper. A tail-recursive function is really a state machine in disguise. Once the recursion disappears, what remains is algebra: values evolving under an operation.

Fibonacci never depended on integers. We only assumed it did.

Rust’s type system lets us remove that assumption and state exactly what the algorithm requires. And once you see that, Fibonacci stops being a numerical algorithm and becomes a structural one.