Rust

Fibonacci in Rust

Ben Brandt

Ben Brandt

— 4 min read
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. Once I learn more about dynamic data types in Rust, I'm sure I'd have a better solution that would take less computation on larger integers.

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.

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!

Read more