Lab-Recursion-Handout-2.pdf (?1?, ?3?) Q?? Case Study 1: Analyzing the Fibonacci
ID: 3698506 • Letter: L
Question
Lab-Recursion-Handout-2.pdf (?1?, ?3?) Q?? Case Study 1: Analyzing the Fibonacci Sequence Recall that the Fibonacci sequence is a recursively defined sequence such that each term is the sum of the sequence's two previous terms. That is, the sequence 1, 1,2, 3, 5, 8, 13, 21, 34, 55, A recursive method to compute the Fibonacci sequence has been provided for you (see unl.cse.recursion.Fibonacci). The main method of this class also provides code to compute the execution time of the recursive method. Run the program for several input instances. This recursive method is highly inefficient: the method is called many times on the same input. Your task will be to directly observe this by adding code to count the exact number of times the method is called for each input n. Hint: declare a private integer array and increment entries on each call to the recursive method depending on the input n. You may assume that an array no larger than 50 will be needed.Explanation / Answer
import java.util.HashMap;
import java.util.Map;
public class Fibonacci {
static Map<Integer, Integer> cache = new HashMap<Integer, Integer>();
public static int fibonacci2(int number) {
if (number == 1 || number == 2) {
return 1;
}
int fibo1 = 1, fibo2 = 1, fibonacci = 1;
for (int i = 3; i <= number; i++) {
fibonacci = fibo1 + fibo2;
fibo1 = fibo2;
fibo2 = fibonacci;
}
return fibonacci;
}
public static int improvedFibo(int number) {
Integer fibonacci = cache.get(number);
if (fibonacci != null) {
return fibonacci;
}
fibonacci = fibonacci2(number);
cache.put(number, fibonacci);
return fibonacci;
}
public static void main(String[] args) {
int result,n=6;
long start,end;
start=System.nanoTime();
result=improvedFibo(n);
end=System.nanoTime();
double ms=(end-start)/1000000.0;
System.out.println("fibonacci ("+n+") ="+result);
System.out.println("execution time = "+ms+"ms");
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.