Creating a Fibonacci finder in Rust

May 1, 2021

I’m learning Rust as a way to sharpen my skills as a developer and push into some areas that I don’t normally get to deal with in my web applications.

I’m reading using The Rust Programming Language as my study guide, and one of the first exercises they suggest doing is implementing a Fibonacci finder.

The Fibonacci Sequence, as I understand it, is a logarithmic pattern often observed in nature where each number in the sequence is the sum of the two numbers preceding it. For example the first 10 numbers in the sequence would be:

0, 1, 1, 2, 3, 5, 8, 13, 21

Anyway, I wanted to implement a recursive function to find the number at the nth place in the sequence so I came up with this:

fn get_next_fib(nth: u32, start: u128, next: u128) -> u128 {
    if nth != 0 {
        get_next_fib(nth - 1, next, start + next)
    } else {
        next
    }
}

If Rust allowed default args in their functions I would have defaulted the start and next args as 0 and 1 but I had to use a wrapper like this instead:

fn get_fib(n: u32) -> u128 {
    if n < 3 {
        (n - 1).into()
    } else {
        get_next_fib(n - 2, 0, 1)
    }
}

This method allows me to generate the 187th number (The largest Fibonacci number that can be stored as an unsigned 128-bit integer) in around 14000 nanoseconds.

I’m sure this is pretty slow implementation, but I thought it was a pretty clean solution.