Write a program recursive_fibonacci.py that includes a recursive function fib(n) that returns the nth Fibonacci number.
For the purposes of this activity, we'll use the Fibonacci sequence that starts with fib(0) = 0, fib(1) = 1, and all the other Fibonacci values the sum of the previous two. So:
fib(2) = fib(0) + fib(1) = 0 + 1 = 1
fib(3) = fib(1) + fib(2) = 1 + 1 = 2
fib(4) = fib(2) + fib(3) = 1 + 2 = 3
fib(5) = fib(3) + fib(4) = 2 + 3 = 5 ...
Example Output
fib(0) --> 0
fib(5) --> 5
fib(10) --> 55
fib(40) --> 102334155 How long does it take your computer to calculate the 40th Fibonacci value?
While it's easy to define the Fibonacci sequence recursively, and it's relatively simple to write a program to solve for Fibonacci values recursively, using recursion for this calculation is not very efficient. Every time we have to calculate a new value, our recursive function has to go back and recalculate all the values down to the beginning. This places some limitations on our calculations.
To improve our ability to calculate Fibonacci values, add a function fib_loop(n) to your program that uses a loop (rather than recursion) to calculate the nth value. How does this function's speed compare with the recursive version?