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 turns out to be an especially interesting environment for this discussion, because it forces us to confront an important realization. More on that later.

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.

Yes, 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.

Therefore:

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.

The trampoline idea revisited

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(v) => return v,
            Bounce::More(step) => step(),
        };
    }
}

Nothing magical happens here:

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

The loop replaces recursion.

Tail-recursive Fibonacci as state

Recall the tail-recursive formulation:

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

Instead of building stack frames, we carry forward state.

A generic Fibonacci

Here is the crucial observation: Fibonacci only requires addition. Not integers, not ordering, not multiplication. Just addition.

In Rust, we can express this precisely.

use std::ops::Add;

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

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

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. This is one of the selling points of Rust's trait system.

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 that supports 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.

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 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.

Algebraic truths

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. Neither more nor less. This is functional programming expressed through Rust’s type system.

A note on performance

The trampoline prevents stack overflow, but allocates one closure per step.

Therefore:

• excellent for teaching TCO concepts
• not ideal for high-performance Rust
• idiomatic Rust would use iteration internally

The important point here is conceptual clarity, not speed.

Landing on four feet

Trampolines were a workaround for missing TCO. In this article, they become something more interesting: a bridge between functional programming ideas and algebraic abstraction.

We started with recursion. We removed stack growth. We generalized Fibonacci beyond numbers. And we discovered that Fibonacci is not really about integers at all, only about addition.

Rust allows us to encode that idea precisely and safely.