a) without DP
recurrence relation for #calls is T(n) = T(n-1) + T(n-2) + 2 (becoz here 2 Distinct recursive calls T(n-1) and T(n-2))
T(0) = 0
T(1) = 0
(here no recursive calls for T(0) and T(1))
T(2 )= T(1) + T(0) + 2 = 2
T(3 )= T(2) + T(1) + 2 = 4
T(4 )= T(3) + T(2) + 2 = 8
so total # calls including first call(T(4)) = 8+1=9
b) with DP
in DP we have to evaluate every function call exactly once.
so for fib(4) we have to evaluate fib(3),fib(2),fib(1) and fib(0),,,,,,,ie n+1 function call
so total 5 function call.