Problem

For a provided non-negative number n calculate the n-th Fibonacci number.

Examples:

Solution

fn fibonacci_number(n: u32) -> u32 {
    if n <= 1 {
        return n;
    }

    (2..=n)
        .fold((0, 1), |(prev, curr), _| (curr, prev + curr))
        .1
}

Explanation

A conventional mathematically beautiful way to solve the puzzle is to use recursion:

fn fibonacci_number(n: u32) -> u32 {
    if n <= 1 {
        return n;
    }

    fibonacci_number(n - 2) + fibonacci_number(n - 1)
}

This way however is very inefficient since it takes exponential time to continuously recalculate previous sums again and again.

Luckily, there is an easy way to replace the recursion with a simple iteration. In our implementation, we use fold method on (2..=n) range inclusive iterator to iterate and maintain the previous Fibonacci number prev and the current one curr. In the end, we return the current number, which is accessible from the result tuple's second field .1.

Complexity

The time complexity of the solution is O(n) (where n is the n-th Fibonacci number we calculate).

---

Rust Playground with this code