Generate Fibonacci Sequence in Compile-Time using generics

In C++ with template metaprogramming you can calculate the fibonacci sequence in compile-time easily in this way.

template<int  N>
constexpr int fibonacci() {return fibonacci<N-1>() + fibonacci<N-2>(); }
template<>
constexpr int fibonacci<1>() { return 1; }
template<>
constexpr int fibonacci<0>() { return 0; }

But in rust you cant just pass a constant through a generic as far as I know, also I know that sometimes rust optimizes some funcions to just constants in assmebly code. Example: https://rosettacode.org/wiki/Compile-time_calculation#Rust

But the conventional recursive approach of the problem is not optimized to a constant.

fn fibo(n: i32) -> i32 {
    match n {
        0 => 0,
        1 => 1,
        n => fibo(n - 1) + fibo(n - 2),
    }
}

// Call it with
fibo(45); // It takes around 5 secs, calculated at runtime

Ok, to this point I can undestand that just the compiler does not know how to optimize this, but I found a way to make this calculated at compile time using Iterators!

struct Fibo(u32, u32);

impl Iterator for Fibo {
    type Item = u32;
    fn next(&mut self) -> Option<Self::Item> {
        *self = Fibo(self.1, self.1 + self.0);
        Some(self.0)
    }
}

fn fibo() -> Fibo {
    Fibo(0, 1)
}

// Call it with
fibo().take(45).collect::<Vec<_>>()[44]; // This gets the 45th element calculated at compile-time, instantly

At this point I just want to know why this happens.

Solution

Algorithmic Complexity

The naive way of computing the Fibonacci sequence has exponential complexity

fn fibo(n: i32) -> i32 {
    match n {
        0 => 0,
        1 => 1,
        n => fibo(n - 1) + fibo(n - 2),
    }
}

You can visualize it like:

fibo(0): 1 call.
fibo(1): 1 call.
fibo(2): 3 calls -- fibo(2), fibo(1), fibo(0).
fibo(3): 5 calls -- fibo(3), fibo(2) (which is worth 3), fibo(1).
fibo(4): 9 calls -- fibo(4), fibo(3) (worth 5) and fibo(2) (worth 3).

The iterator version, however, is completely different. Rewritten as a function it boils down to:

fn fibo(n: i32) -> i32 {
    fn rec(i: i32, current: i32, next: i32) -> i32 {
        if i == 0 { current } else { rec(i - 1, next, current + next) }
    }

    rec(n, 0, 1)
}

Which executes in exactly n + 1 steps... providing n >= 0.

But in C++ it works!

C++ compilers tend to use memoization for both template instantiations and constexpr evaluations. They do not have to, this is strictly an implementation detail, but they do for efficiency reasons.

In this instance, a memoized version of fibo turns exponential complexity into linear complexity, which is much easier to compute.

Doing it in Rust!

It's possible to compute fibonacci in Rust at compile-time with the current beta, which stabilizes branches in const functions.

See the playground:

const fn fibo(n: i32) -> i32 {
    const fn rec(i: i32, current: i32, next: i32) -> i32 {
        if i == 0 { current } else { rec(i - 1, next, current + next) }
    }

    rec(n, 0, 1)
}

fn main() {
    const RESULT: usize = fibo(9) as usize;

    let array: [i32; RESULT] = [
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
        0, 1
    ];
    
    println!("{}", array[0]);
}

There may be a trick to express the computation at compile-time without a branch, allowing to compute fibo at compile-time on stable, however I am not sure rustc wouldn't perform the recursive call regardless.