Exam 3 is an open-book exam. There\'re 10 questions, 10 points each. For each qu
ID: 3917673 • Letter: E
Question
Exam 3 is an open-book exam. There're 10 questions, 10 points each. For each question, make sure to show your work, i.e., how you come up with your answers.
1. (10 pts) Given that the method for finding the Fibonacci number is implemented as follows, how many times is the fib method invoked for fib(6)? Show your work for credits.
/** The method for finding the Fibonacci number */
public static long fib(long index) {
if (index == 0) // Base case
return 0;
else if (index == 1) // Base case
return 1;
else // Reduction and recursive calls
return fib(index - 1) + fib(index - 2);
Explanation / Answer
class Main {
// HAVING a static variable can keep track of the number of times a method is called
static int count = 0;
public static long fib(long index) {
count++; // incrementing each time it is called
System.out.printf("count = %d and index = %d ", count, index);
if (index == 0)
return 0;
else if (index == 1)
return 1;
else
return fib(index - 1) + fib(index - 2);
}
public static void main(String[] args) {
System.out.println(fib(6));
}
}
/*TRACE
count = 1 and index = 6
count = 2 and index = 5
count = 3 and index = 4
count = 4 and index = 3
count = 5 and index = 2
count = 6 and index = 1
count = 7 and index = 0
count = 8 and index = 1
count = 9 and index = 2
count = 10 and index = 1
count = 11 and index = 0
count = 12 and index = 3
count = 13 and index = 2
count = 14 and index = 1
count = 15 and index = 0
count = 16 and index = 1
count = 17 and index = 4
count = 18 and index = 3
count = 19 and index = 2
count = 20 and index = 1
count = 21 and index = 0
count = 22 and index = 1
count = 23 and index = 2
count = 24 and index = 1
count = 25 and index = 0
8
*/
Answer: 25 timesRelated Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.