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