The Fibonacci sequence is defined as follows: fib(0) = 0 fib(1) = 1 fib(N) = fib

Question

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 */

Explanation / Answer

here is your program : ------------>>>>>>>>

class Fibonacci{
public static long rec = 0;
public static int FibRec(int n){
  rec++;
  if(n <= 0){
   return 0;
  }
  if(n == 1){
   return 1;
  }
  return FibRec(n-1)+FibRec(n-2);
}
public static int FibIter(int n){
  if(n <= 0){
   return 0;
  }
  int n1 = 0;
  int n2 = 1;
  int r = 0;
  for(int i = 0;i<n;i++){
   r = n1 + n2;
   n2 = n1;
   n1 = r;
  }
  return r;
}
public static void main(String[] args) {
  System.out.println("time is in nanosec");
  System.out.println("For n = 5 : ");
  int answer;
  long rect,itrt;
  long time1,time2;
  rec = 0;
  time1=System.nanoTime();
  for(int i = 0;i<1000;i++){
   answer = FibRec(5);
  }
  time2 = System.nanoTime();
  rect = time2 - time1;
  time1=System.nanoTime();
  for(int i = 0;i<1000;i++){
   answer = FibIter(5);
  }
  time2 = System.nanoTime();
  itrt = time2 - time1;
  System.out.println("Recursive time = "+rect/1000);
  System.out.println("Iterative Time = "+itrt/1000);
  System.out.println("Recursive Call = "+rec);
  System.out.println("For n = 10 : ");
  rec = 0;
  time1=System.nanoTime();
  for(int i = 0;i<1000;i++){
   answer = FibRec(10);
  }
  time2 = System.nanoTime();
  rect = time2 - time1;
  time1=System.nanoTime();
  for(int i = 0;i<1000;i++){
   answer = FibIter(10);
  }
  time2 = System.nanoTime();
  itrt = time2 - time1;
  System.out.println("Recursive time = "+rect/1000);
  System.out.println("Iterative Time = "+itrt/1000);
  System.out.println("Recursive Call = "+rec);
  System.out.println("For n = 20 : ");
  rec = 0;
  time1=System.nanoTime();
  for(int i = 0;i<1000;i++){
   answer = FibRec(20);
  }
  time2 = System.nanoTime();
  rect = time2 - time1;
  time1=System.nanoTime();
  for(int i = 0;i<1000;i++){
   answer = FibIter(20);
  }
  time2 = System.nanoTime();
  itrt = time2 - time1;
  System.out.println("Recursive time = "+rect/1000);
  System.out.println("Iterative Time = "+itrt/1000);
  System.out.println("Recursive Call = "+rec);
  System.out.println("For n = 30 : ");
  rec = 0;
  time1=System.nanoTime();
  for(int i = 0;i<1000;i++){
   answer = FibRec(30);
  }
  time2 = System.nanoTime();
  rect = time2 - time1;
  time1=System.nanoTime();
  for(int i = 0;i<1000;i++){
   answer = FibIter(30);
  }
  time2 = System.nanoTime();
  itrt = time2 - time1;
  System.out.println("Recursive time = "+rect/1000);
  System.out.println("Iterative Time = "+itrt/1000);
  System.out.println("Recursive Call = "+rec);
  System.out.println("For n = 40 : ");
  rec = 0;
  time1=System.nanoTime();
  for(int i = 0;i<1000;i++){
   answer = FibRec(40);
  }
  time2 = System.nanoTime();
  rect = time2 - time1;
  time1=System.nanoTime();
  for(int i = 0;i<1000;i++){
   answer = FibIter(40);
  }
  time2 = System.nanoTime();
  itrt = time2 - time1;
  System.out.println("Recursive time = "+rect/1000);
  System.out.println("Iterative Time = "+itrt/1000);
  System.out.println("Recursive Call = "+rec);
}
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.