# Exercise 9

## Fibonacci numbers

Write a function that computes the nth Fibonacci number. Your function
should be called `fib()`

and should take as input a single integer
value `n`

, and should return a single integer value representing the
nth Fibonacci number.

Use a loop to accomplish this. Count how many arithmetic operations take place for computing the 10th Fibonacci number, and count also for the 20th.

**Bonus**: write a second version of your function that uses recursion
instead of a loop. Note how much more succint the code is. Count how
many arithmetic operations take place for computing the 10th Fibonacci
number, and for the 20th as well. Now you see the potential downside
of recursive algorithms.

**Bonus 2**: incorporate memoization to make your recursive version more
efficient. Count again the number of arithmetic operations for the
10th and 20th Fibonacci numbers.