Fibonacci in Rust

I've started 2018 learning yet another programming language: Rust. I love learning new languages. They expose you to new ideas, paradigms, and (in the case of Rust) even new types of programs you can build.

Rust pitches itself as:

...a systems programming language that runs blazingly fast, prevents segfaults, and guarantees thread safety.

So far, it seems to blend the low-level power and access of a language like C, with the type system of Elm or Haskell, and the pragmatism of JavaScript or Python.

I'll be documenting my progress of learning Rust by writing some walk-throughs of what I've been building. First up is a program to generate the nth Fibonacci number.

Getting started

Assuming you've installed Rust, you get started with a simple command in whatever directory you're in:

cargo new --bin fibonacci

This will generate the base project to get started. Go ahead and clear out the main function in src/main.rs and let's get started writing our code!

Fibonacci sequence

According to the trusty Wikipedia, the Fibonacci sequence is

characterized by the fact that every number after the first two is the sum of the two preceding ones.

So, let's write a function that handles that:

fn fibonacci(n: u32) -> u32 {
    match n {
        0 => 1,
        1 => 1,
        _ => fibonacci(n - 1) + fibonacci(n - 2),
    }
}

Alright, there's a lot going on in those 7 lines! Let's start at the top.

n is the parameter to our function, so the number we want to generate the fibonacci number of. I annotated it as an unsigned, 32-bit integer (u32) because we are only using positive integers. And the -> u32 is annotating the return type of this function, which is also an unsigned, 32-bit integer.

Next up is a match expression, which allows us to do something cool called "pattern matching". I love languages that have some variation of this because I find it to be an expressive way to write functions. Each line that has the => symbol is a "match arm". It functions like a switch statement in JavaScript, or a case statement in Elm. It returns the first arm to match n.

So 0 and 1 would return 1. The _ arm says that any other integer that gets passed in will match. In this function, it does all the logic of the Fibonacci sequence by recursively calling the same function with smaller integers.

Note: While I took a recursive approach here because it's what I would do in a functional language, I don't think it is the best way to solve this problem in Rust. When entering larger integers it takes a long time. We'll come back to this at the end.

Running the function

Let's test if this works. Let's add some console output and generate a few numbers.

fn fibonacci(n: u32) -> u32 {
    match n {
        0 => 1,
        1 => 1,
        _ => fibonacci(n - 1) + fibonacci(n - 2),
    }
}

fn main() {
    println!("Fibonacci generator");
    println!("{}", fibonacci(1));
    println!("{}", fibonacci(3));
    println!("{}", fibonacci(5));
}

If you run the command

cargo run

You should see 1, 3, and 8 printed out.

println! does what you'd expect, prints a line. And each argument after the initial string replaces a corresponding {}.

User input

While we can calculate a Fibonacci number, it's not very useful if we don't allow users to interact with it. So let's update our main function to allow a user to enter their own integers .

use std::io;

fn fibonacci(n: u32) -> u32 {
    match n {
        0 => 1,
        1 => 1,
        _ => fibonacci(n - 1) + fibonacci(n - 2),
    }
}

fn main() {
    println!("Fibonacci generator");
    println!("Type \"quit\" to end the program");

    loop {
        let mut n = String::new();

        println!("\nEnter a positive integer:");

        io::stdin().read_line(&mut n).expect("Failed to read line");

        if n.trim() == "quit" {
            break;
        }

        let n: u32 = match n.trim().parse() {
            Ok(num) => num,
            Err(_) => continue,
        };

        println!("{}", fibonacci(n));
    }
}

Note first that we imported the standard library IO functions at the top. Then we use a loop which works like loops in most languages. In this case, it is equivalent to while (true), where it will keep running until you break out of the loop.

In this case, we break if the user types in the word "quit", allowing them to exit the program.

Each time through the loop, we create a new mutable variable called n (Rust variables are immutable by default, hence why the mut is added after let). We read a line of input from the user with io::stdin().read_line(&mut n) and store it in n.

We then parse that string into an unsigned integer, which gives us a Result type. A Result type is an Enum type that either is Ok with the corresponding value, or an Error with a corresponding error message.

If the user typed in a number, we get Ok and store the number in n. If not, we call continue and instruct the user to pass in a positive integer again. Not the most sophisticated error handling, but it gets the job done. If we wanted to, we could add more match arms to handle different error cases, but for now, this works.

Once we have the number, we print its corresponding number in the Fibonacci sequence. Then we start the loop again until the user decides to exit the program.

Refactor Time

If you try this out, you'll quickly find that the recursive approach I took does not scale well. If given a large number, this program will make your fan spin and your CPU very hot.

This recursive approach is nice in functional languages that have tail call optimizations to make this fast. But part of what Rust gives us is a powerful ownership model that makes mutable variables not so scary, contrary to what functional languages will have you believe.

So, let's try again with a much more optimized version, leveraging the powers Rust gives us.

fn fibonacci(n: u64) -> u64 {
    let mut a = 1;
    let mut b = 0;
    let mut count = 0;
    
    while count < n {
        let tmp = a + b;
        b = a;
        a = tmp;
        count += 1;
    }
    
    b
}

By using an iterative loop, instead of recursive function calls, this can now actually run in a reasonable amount of time without crashing your computer!

Note that the input and output were changed to a u64. This allows us to compute bigger fibonacci numbers without an overflow now that we can actually compute them in a reasonable time.

You'll see though that even u64 isn't big enough to handle fibonacci(100). Do you have any ideas for how we might be able to change this to handle that?

Conclusion

I hope this was somewhat helpful to you as you start exploring Rust yourself. To get started I've been working through the "Rust Book", which has been really helpful.

I'm looking forward to writing more Rust code in the future and will keep documenting as I go! I'd may even do some live coding if that's of interest to anyone :) Happy New Year!