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.