GATE CS 1991 Q01 — Recursion

Let $C(n)$ denote the total number of times the function fib is called to evaluate $fib(n)$.

Based on the recursive definition:

• For the base cases $n = 0$ and $n = 1$, the function returns immediately without any further recursive calls:
  $C(0) = 1$
  $C(1) = 1$
• For $n \ge 2$, evaluating $fib(n)$ requires $1$ initial call plus the calls made during the evaluation of $fib(n-1)$ and $fib(n-2)$:
  $C(n) = 1 + C(n-1) + C(n-2)$

We can compute the values of $C(n)$ step-by-step:

• $C(2) = 1 + C(1) + C(0) = 1 + 1 + 1 = 3$
• $C(3) = 1 + C(2) + C(1) = 1 + 3 + 1 = 5$
• $C(4) = 1 + C(3) + C(2) = 1 + 5 + 3 = 9$
• $C(5) = 1 + C(4) + C(3) = 1 + 9 + 5 = 15$
• $C(6) = 1 + C(5) + C(4) = 1 + 15 + 9 = 25$
• $C(7) = 1 + C(6) + C(5) = 1 + 25 + 15 = 41$

Thus, the total number of times fib is called to evaluate $fib(7)$ is 41.