# Go4Fun - Functional programming and more # Rust Interview Puzzles: Fibonacci number

### Problem

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

#### Examples:

 Input `n` Output `0` `0` `1` `1` `2` `1` `3` `2` `4` `3` `5` `5` `6` `8`

### 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