(You need to have first completed Programming Project 13.1 to work on this project.) In this exercise, you will compare the efficiency of a recursive and an iterative function to compute the Fibonacci number.

a. Examine the recursive function computation of Fibonacci numbers. Note that each Fibonacci number is recomputed many times. To avoid this recomputation, do Programming Project 13.1 iteratively, rather than recursively; that is, do the problem with a loop. You should compute each Fibonacci number once on the way to the number requested and discard the numbers when they are no longer needed.

b. Time the solution for Programming Project 13.1 and Part a of this project in finding the 1st, 3rd, 5th, 7th , 9th, 11th, 13th , and 15th Fibonacci numbers. Determine how long each function takes. Compare and comment on your results.

Hints: If you are running Linux, you can use the bash time utility. It gives real time (as in wall clock time), user time (time measured by cpu cycles devoted to your program), and sys time (cpu cycles devoted to tasks other than your program). If you are running in some other environment, you will have to read your manual, or ask your instructor, in order to find out how to measure the time a program takes to run.