Fibonacci sequence with Rust and Tail Call Optimization

Programming Fibonacci sequence is a famous task, often used for job interviews. Algorithm looks easy, but there are few conditions where we will have to go deeper.

Let’s first create project.

If you have Rust installed, you can start with:

cargo new fibonacci

That will create a directory, called ‘fibonacci’ with Cargo.toml file, which holds project dependencies and ‘src’ directory with single file ‘main.rs’. Now, if we execute:

cargo run

It will just output “Hello, world!”, because that’s default program generated by Cargo.

Next let’s write some Rust!

One of the easiest implementation would be:

fn fib(n: i32, acc: u128, curr: u128) -> u128 {
  if n <= 0 {
    acc
  }else{
    fib(n — 1, &acc + curr, acc)
  }
}

Here is contents of main.rs after we add fibonacci function there:

fn fib(n: i32, acc: u128, curr: u128) -> u128 {
  if n <= 0 {
    acc
  }else{
    fib(n - 1, &acc + curr, acc)
  }
}
fn main() {
  let n = 10;
  println!("{}", fib(n, 0, 1));
}

Now if we do cargo run, it will output “55”, which is the correct value of the 10th number of fibonacci sequence. But what happens if we increase number from 10 to 1000?

thread ‘main’ panicked at ‘attempt to add with overflow’

The reason is that the return value of the function fibonacci is out of range of u128, which is an unsigned 128bit integer. In current state Rust doesn’t have any built in tools for really big numbers, so let’s use crate num_bigint for that. We will also be using num_traits for simplifying syntax.

Let’s add it to Cargo.toml:

[package]
name = “fibonacci”
version = “0.1.0”
authors = [“Eugene Nikolaev <satorsight@gmail.com>”]
[dependencies]
num-bigint = “0.2.3”
num-traits = “0.2.9”

Then let’s rewrite program to use crate data types instead of built in ones:

extern crate num_bigint as bigint;
extern crate num_traits;
use bigint::BigUint;
use num_traits::{Zero, One};
fn fib(n: i32, acc: BigUint, curr: BigUint) -> BigUint {
  if n <= 0 {
    acc
  }else{
    fib(n - 1, &acc + curr, acc)
  }
}
fn main() {
  let n = 1000;
  println!("{}", fib(n, Zero::zero(), One::one()));
}

Now, when we execute cargo run, it will download missing dependencies. And since no overflow will happen anymore, we will get right answer:

“43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875”

Now, let’s go deeper and change the requested number in sequence from 1000 to 100000.

thread ‘main’ has overflowed its stack

fatal runtime error: stack overflow

Error looks similar but the reason is completely different. Because we use recursion, after compilation, Rust compiler will generate a stack of calls that will exceed built in limits, so this error is sort of protection against endless recursion and other similar errors. Most programming languages have that kind of protection, Ruby and JS won’t execute the function with the same “stack overflow” error, PHP will just give up and result as “Infinity”.

There are few ways to exceed stack limitation, but most of them are removed or deprecated and not working as expected.

The correct way to surpass that is to use a technique, called Tail Call Optimization. Tail-call optimization is where you are able to avoid allocating a new stack frame for a function because the calling function will simply return the value that it gets from the called function. The most common use is tail-recursion, where a recursive function written to take advantage of tail-call optimization can use constant stack space.

Not every programming language is capable of performing that optimization and unfortunately, Rust in its current state doesn’t support it. But there is a crate, called tramp, that simulates that optimization.

Let’s try it out!

First, adding new dependency to Cargo.toml:

tramp = “0.3.0”

Then, rewrite function. So, the final version of main.rs will look like:

extern crate num_bigint as bigint;
extern crate num_traits;
#[macro_use] extern crate tramp;
use bigint::BigUint;
use num_traits::{Zero, One};
use tramp::{tramp, Rec};
fn fib(n: i32) -> BigUint {
  tramp(do_fib(n, Zero::zero(), One::one()))
}
fn do_fib(n: i32, acc: BigUint, curr: BigUint) -> Rec<BigUint> {
  if n <= 0 {
    rec_ret!(acc)
  }else{
    let new = &acc + curr;
    let nn = n - 1;
    rec_call!(do_fib(nn, new, acc))
  }
}
fn main() {
  let n = 1000000;
  println!("{}", fib(n));
}

Works perfectly! Even if we increase the number to million, it will still work. In fact, now it’s only limited by the machine’s spec, it’s executed on.

Now we know how to apply Tail Call Optimization with Rust and know how to create really powerful recursions, taking advantage of Rust’s performance.