Exercise 9

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.

solutions