Fibonacci Numbers:

The Fibonacci sequence is given by : 0, 1, 1, 2, 3, 5, 8, 13, 21, ..... By definition the Fibonacci sequence starts at 0 and 1 and each subsequent number is the sum of the previous two. In mathematical terms, the sequence Fn of Fibonacci number is defined by the recurrence relation

Fn = Fn-1 + Fn-2 with F0=0 and F1=1

An algorithm for calculating the nth Fibonacci number can be implemented either recursively or iteratively.

Example Recursive:

fib (n) { if (n = 0) { return 0; } else if (n = 1) { return 1; } else { return fib(n-1) + fib(n-2); } }

Example Iterative:

fib (n) { fib = 0; a = 1; t = 0; for(k = 1 to n) { t = fib + a; a = fib; fib = t; } return fib; }

a) Implement both recursive and iterative algorithms to calculate Fibonacci Numbers in the programming language of your choice. Provide a copy of your code with your HW pdf. We will not be executing the code for this assignment. You are not required to use the flip server for this assignment.

b) Use the system clock to record the running times of each algorithm for n = 5, 10, 15, 20, 30, 50, 100, 1000, 2000, 5000, 10,000, .... You may need to modify the values of n if an algorithm runs too fast or too slow to collect the running time data. If you program in C your algorithm will run faster than if you use python. The goal of this exercise is to collect run time data. You will have to adjust the values of n so that you get times greater than 0.

c) Plot the running time data you collected on graphs with n on the x-axis and time on the y-axis. You may use Excel, Matlab, R or any other software.

d) What type of function (curve) best fits each data set? Again you can use Excel, Matlab, any software or a graphing calculator to calculate the regression curve. Give the equation of the function that best "fits" the data and draw that curve on the data plot. Why is there a difference in running times?