CS 2401 Assignment #4

Due Date: Monday, October 4 or Tuesday, October 5, depending on the day of your lab.

Objective: The goal of this assignment is to compare the efficiency of recursive and non-recursive approaches for one specific problem.

Assignment: Write two methods for computing Fibonacci numbers: a method based on recursion (without memorization) and an iterative method that uses a simple for loop; the ideas behind both methods have been explained in the class and in the book.

Now, the goal is to compare the speed of these two approaches. Both will run very fast (e.g., take less than 5 seconds of computation time) for small values of n. However, we can estimate the time accurately by using a system method that will return the current system time in milliseconds as a long integer: System.currentTimeMillis(). To estimate the time taken, call this method once before running your method and record the value. Then run your method, and when it is complete call System.currentTimeMillis() again to get the current time. The difference between the two values is the total number of milliseconds taken by your method. To get a more accurate estimate you can run your method several times in a row and compute the average time taken.

Run your program and compare the times taken to compute the Fibonacci numbers with the two different approaches for n=5, n=10, and n=15. Record your observations and be able to explain what is happening to your TA when you demo your program.