Nth Fibonacci Number

Each term in the Fibonacci sequence is generated by adding the previous two terms. By definition, the first Fibonacci number is 1 and the second Fibonacci number is 2. The rest of the sequence unfolds according to the rule of adding the previous two terms.

So the first 10 Fibonacci numbers are thus:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

We can use the notation Fib(n) to denote the nth Fibonacci number. So Fib(1)=1 and Fib(2)=2, and Fib(10)=89.

Write a function called Fib() that takes as input n, and produces as output Fib(n), the nth Fibonacci number.

Test your program against these examples:

Fib(5) should return 8

Fib(10) should return 89

Fib(40) should return 165580141

Bonus challenges

  1. Write two versions of your function—one that uses recursion and a second that uses iteration.
  2. The recursive version will be much slower at computing Fib(n) for large values of n. Why?
  3. Think about how you might speed up the recursive version. Hint: consider memoization.