What is the total number of invocations of fib (counting the initial call to…
2026
What is the total number of invocations of fib (counting the initial call to fib(8) itself) that occur when fib(8) is computed using the C function below?
int fib(int n){
if (n == 1) return 1;
else if(n == 2) return 1;
else return(fib(n-1)+fib(n-2));
}Answer: D. 41 — Concept: when a recursive function is expanded without memoisation, the number of times it is entered obeys a recurrence of its own. Every entry into the…
- A.
13
- B.
21
- C.
30
- D.
41
Attempted by 253 students.
Show answer & explanation
Correct answer: D
Concept: when a recursive function is expanded without memoisation, the number of times it is entered obeys a recurrence of its own. Every entry into the function costs one; an entry that stops at a base case adds nothing further, while an entry that recurses adds the entries consumed by each sub-call it makes.
Here the base cases are n = 1 and n = 2. Writing T(n) for the total number of entries into fib needed to evaluate fib(n): T(1) = 1, T(2) = 1, and T(n) = 1 + T(n−1) + T(n−2) for n > 2, where the leading 1 is the entry itself.
Applying the recurrence step by step:
T(3) = 1 + T(2) + T(1) = 1 + 1 + 1 = 3
T(4) = 1 + T(3) + T(2) = 1 + 3 + 1 = 5
T(5) = 1 + T(4) + T(3) = 1 + 5 + 3 = 9
T(6) = 1 + T(5) + T(4) = 1 + 9 + 5 = 15
T(7) = 1 + T(6) + T(5) = 1 + 15 + 9 = 25
T(8) = 1 + T(7) + T(6) = 1 + 25 + 15 = 41
Cross-checks:
Closed form: with these two base cases the expanded call tree always holds T(n) = 2 × fib(n) − 1 entries. Since fib(8) = 21, T(8) = 2 × 21 − 1 = 41, which matches the step-by-step tally.
Shape of the tree: of those 41 entries, 21 stop at a base case and return 1, and the remaining 20 each perform one addition; the 20 additions combine the twenty-one 1s into the returned result 21.
Value versus work: fib(7) returns 13 and fib(8) returns 21. Those are the results the recursion produces, not counts of how many times fib is entered to produce them — reading 21 as the tally is the usual confusion here.
Where the initial call sits: the tally of 41 includes the outermost entry fib(8) itself. Only 40 of the entries are made from inside another entry, so a stricter reading that excludes the outermost call would give 40; the tally asked for here includes it.
Total number of invocations of fib while fib(8) is computed: 41.