The recurrence relation for the number of calls is $$T(n) = T(n-1) + T(n-2) + 1$$ where $1$ is for the current called function.
- $T(0) =T(1) = 1$ (for $\textsf{fib}(0)$ and $\textsf{fib}(1)$, there are no recursive calls and only current function call is there).
- $T(2) = 3$
- $T(3) = 5$
- $T(4) = 9$
- $T(5) = 15$
- $T(6) = 25$
- $T(7) = 41$
Answer: $41$
We can also calculate the number of calls excluding the current function call or the number of recursive calls initiated by a given function as follows:
$$T(n) = T(n-1) + T(n-2) + 2$$ $(2$ recursive calls one each for $T(n-1)$ and $T(n-2))$
- $T(0) = T(1) = 0$ (no recursive calls happen here)
- $T(2) = 2$
- $T(3) = 4$
- $T(4) = 8$
- $T(5) = 14$
- $T(6) = 24$
- $T(7) = 40$
Now, we can add the initial call for $\textsf{fib}(7)$ and get answer as $40+1 = 41.$