An almost infinite Fibonacci Iterator

Rust provides a nice way to create an iterator based on a struct. In this example we are creating an iterator that will allow us to iterate over the Fibonacci numbers.

Some iterators have a clear range of things they iterate over, this one is unbounded. That is it will never stop unless we break out from the iteration rule.

While theoretically this could go on forever there is one issue that we have to solve. What happens if the series outgrowth the variables that supposed to store the value? What should happen when we reach the maximum value and the variable is about to overflow. There are number of ways to handle number overflow. In this implementation I decided I'd like to stop the iteration.

I also used the u8 value type to store the Fibonacci numbers so it will be easy to demonstrate the overflow as the max value of u8 is 255. In a real implementation I'd probably use u64 or u128 or maybe a generic numeric type, but I did not want to complicate thie example.

In order to implement the iterator we need the struct that will hold the parameters of the iterator. e.g. the current value, or current values, the limit, if there is one. In our case we needed two attributes for the last two values of the Fibonacci series and we don't have a limit.

#[derive(Debug)]
struct Fibonacci {
    current: u8,
    previous: u8,
}

It is also recommended to implement the new method of the struct. This is not a requirement, but it is a cleaner way to initialize the attributes and thus the whole iterator. Self here represents the current struct which is Fibonacci, but it is cleaner to write Self as it allows us to rename the struct without changing in the definition of the function as well.

impl Fibonacci {
    fn new() -> Self {
        Self {
            current: 0,
            previous: 0,
        }
    }
}

The most important part is to implement the Iterator trait for the struct. Inside the trait we need to define the type Item and we need to implement the next function that will calculate the next element of the iteration.

The nextfunction must return an Option<Self::Item> that must contain either the next value in Some(value) form or None if the iterator ran out of values. In this example we don't have a user-provided upper limit, but we wanted to gracefully end the iteration just before the value overflows. So we used the checked_add method that returns and Option containing either the sum of the two numbers or None if there would be an overflow.

We also had to start the next method with a special case for when the current value is 0. This made it easier to start returning the first 1 of the Fibonacci series.

impl Iterator for Fibonacci {
    type Item = u8;

    fn next(&mut self) -> Option<Self::Item> {
        if self.current == 0 {
            self.current = 1;
            return Some(self.current);
        }

        let next_value = self.previous.checked_add(self.current)?;
        self.previous = self.current;
        self.current = next_value;
        Some(self.current)
    }
}

How to use the iterator?

There are two examples showing how to use the iterator. In both we use the for in loop to iterate over the values, but in the first case we break out if we read a limit. In the second case we let it run till the overflow.

    for fb in Fibonacci::new() {
        println!("{fb}");
        if fb > 30 {
            break;
        }
    }

    for fb in Fibonacci::new() {
        println!("{fb}");
    }

The full code

examples/iterators/fibonacci/src/main.rs

#[derive(Debug)]
struct Fibonacci {
    current: u8,
    previous: u8,
}

impl Fibonacci {
    fn new() -> Self {
        Self {
            current: 0,
            previous: 0,
        }
    }
}

impl Iterator for Fibonacci {
    type Item = u8;

    fn next(&mut self) -> Option<Self::Item> {
        if self.current == 0 {
            self.current = 1;
            return Some(self.current);
        }

        let next_value = self.previous.checked_add(self.current)?;
        self.previous = self.current;
        self.current = next_value;
        Some(self.current)
    }
}

fn main() {
    for fb in Fibonacci::new() {
        println!("{fb}");
        if fb > 30 {
            break;
        }
    }
    println!("------");
    for fb in Fibonacci::new() {
        println!("{fb}");
    }
}

Output

$ cargo run -q
1
1
2
3
5
8
13
21
34
------
1
1
2
3
5
8
13
21
34
55
89
144
233