Write a recursive and an iterative function to calculate the nth element in a Fi

Question

Write a recursive and an iterative function to calculate the nth element in a Fibonacci sequence. A Fibonacci sequence is defined as the element 1, followed by another 1, and each element thereafter is the sum of the previous two elements. For example, the first 9 elements of a Fibonacci sequence are: 1 2 3 5 8 13 21 34 This famous sequence was originally used to predict the growth of rabbit populations! Once you have each of the functions working for n equal to 40, determine which method is more efficient by timing the two separate function calls and printing out the time required for each method call to return the 40th element in the sequence. Return the 40th element to main and print it. After that, print out a complete Fibonacci sequence from element 1 to element 40, along with its position number. 1 1 2 3 . . . . This last part should not be timed. The timer function you need for this Project is: Date d1 = new Date(); long milliseconds = D1.getTime(); OR long start = System.currentTimeMillis(); Turn in the source, output, and a short paragraph explaining the reason the two methods took different amounts of time to execute. In Java simplest form with explanation if possible... Thanks!

Explanation / Answer

class Main {
  
// iterative method
public static int iterFib(int n)
{
// declaring initial variables
int f1=1, f2=2, tempf1;
  
// looping for n-1 times since we have first number already
for(int i=2; i<=n; i++)
{
tempf1 = f1;
f1 = f2;
f2 = tempf1 + f2;
}
return f1;
}
  
// recursive method
public static int recurFib(int n)
{
// base cases for first and second numbers
if(n==1)
return 1;
if(n==2)
return 2;
  
// calling recursive with n-1 and n-2
return recurFib(n-1)+recurFib(n-2);
}
  
public static void main(String[] args) {
System.out.println("40th element by iterative method: "+iterFib(40));
System.out.println("40th element by recursive method: "+recurFib(40));
}
}

/*SAMPLE OUTPUT
40th element by iterative method: 165580141
40th element by recursive method: 165580141
*/

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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