Write a prgram that compares the two ways of computing the (n)th Fibonacci numbe
ID: 3627526 • Letter: W
Question
Write a prgram that compares the two ways of computing the (n)th Fibonacci number. It should include one function that computes it recursively, and another that implements an iterative algorithm. Each function should also count the number of iterations it does.The input for your program should be n, where n indicates which Fibonacci number is to be computed.
The output should be the Fibonacci number, the number of additions required for the iterative method, and the number of iterations required for the recursive method.
Explanation / Answer
public class Fibonacci
{
public static void main(String[] args)
{
// output[0] is nth fibonacci number, output[1] is number of iterations
int[] recursively = recursively(8);
int[] iteratively = iteratively(8);
System.out.println(recursively[0]+" "+iteratively[0]);
System.out.println("Recursively: "+recursively[1]+" iterations");
System.out.println("Iteratively: "+iteratively[1]+" iterations");
}
public static int[] iteratively(int n)
{
if(n < 2)
return new int[]{1, 1};
int[] memoize = new int[n];
// base case
memoize[0] = 1;
memoize[1] = 1;
int iterations = 2;
for(int i = 2; i < n; i++)
{
memoize[i] = memoize[i-1] + memoize[i-2];
iterations++;
}
return new int[]{memoize[n-1], iterations};
}
public static int[] recursively(int n)
{
// base case
if(n <= 2)
return new int[]{1, 1};
int[] temp1 = recursively(n-1);
int[] temp2 = recursively(n-2);
return new int[]{temp1[0]+temp2[0], temp1[1]+temp2[1]};
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.