Implement two separate programs that generate the n-th Fibonacci number. The programs should both take n as command line input. The first one should implement the recursive algorithm (Page 3 of the textbook), and the second one should implement the iterative algorithm (Page 4), except that it (the second algorithm only) should compute the n-th Fibonacci number one million (10^6) times (although you only need to print it out once). You'll see the reason for this once you execute the program - it is so fast that it's hard to get a meaningful difference in times for different n without repeating the process many times!
Once the two programs are implemented, measure the time it takes for each of these versions to calculate the n-th Fibonacci number (for the iterative implementation, divide the time it takes your program to run by 10^6) for the following values of n: 1, 5, 10, 15, 20, 25, 30, 35, 40, 41, 42, 43.
To measure running times, you can for example use the "time -p" command (typically in a bash shell generated by cygwin, Mac OS X or some other Unix-like distribution). For example, if the name of the executable is fib, then the following command would give you the running time for calculating the 10th number in the Fibonacci series:
$ time -p ./fib 10
Finally, create a table of all your results and use your favorite plotting software to create two scatter plots of the time taken to compute the Fibonacci numbers using the two different algorithms.
Show your code and results to your TA during your assigned lab section to receive credit. Please make sure that the TA records your grade: do not leave the lab section before the TA records your name and grade.