Consider the recursive version of the fib method from the textbook shown below:
Public static long fib(int n)
{
If (n

Question

Consider the recursive version of the fib method from the textbook shown below:
Public static long fib(int n)
{
If (n <= 2)
{
Return 1;
}
Else
{
Return fib(n - 1) + fib(n - 2);
}
}
How many total recursive calls (not counting the original call) to fib will be made from the original call of fib(6)?
A) 6
B) 12
C) 14
D) 20

Quizplus · Accepted Answer

The original call to fib(6) will generate recursive calls for fib(5) and fib(4). Then, the call to fib(5) will generate recursive calls for fib(4) and fib(3), and the call to fib(4) will generate recursive calls for fib(3) and fib(2). The call to fib(3) will not generate any further recursive calls, as it will hit the base case. Thus, the total number of recursive calls (not counting the original call) from the original call of fib(6) is 2 + 2 + 1 + 1 + 1 + 1 = 8. However, we also need to count the recursive calls made to duplicate calls (e.g. fib(4) is called twice), which will add 6 more recursive calls. Therefore, the total number of recursive calls is 8 + 6 = 14. Therefore, the best choice is C.

Consider the Recursive Version of the Fib Method from the Textbook