Assignment #9 - First Recursion Assignment



The Fibonacci sequence is defined as follows:

fib(0)  = 0
fib(1)   = 1
fib(N) = fib(N-1) + fib(N-2)  if N>=2

You are to write two versions to calculate the Fibonacci sequence; one is recusive (recursiveFib) and the other is iterative (iterativeFib) . Both accept one integer parameter. We want to calculate the time differential between these two methods for N=5,10,20,30,40 , as well as the number of times recursiveFib is called to calculate each. You must complete the following table (you can fill in the numbers manually):


N      Iterative Time      Recursive Time      Recursive Calls
 5                x                              x                              x
10               x                              x                              x
20               x                              x                              x
30               x                              x                              x
40               x                              x                              x


Recall that we can approximate times with the call:

long time1;
time1=System.currentTimeMillis();


To see how long a particular calculation of recursiveFib() takes, we might do something like the following:

long time1,time2;
int answer;

t1=System.currentTimeMillis();
answer=recursiveFib(30);
t2=System.currentTimeMillis();
/*  t2-t1 contains the elapsed time  */

we discussed in class how to determine the number of times a particular method is called; you may wish to review static variables.