how can i calculate how many repeated calls occur in a fib recursive function.
fib(n):
if n = 0 : ret 0
if n = 1 : ret 1
ret fib(n - 1) + fib(n - 2)
ex) if n = 5 how many times fib(3), fib(2), fib(1) are repeated in total ? We know that fib(5) and fib(4) are only called once.
See here for analysis that shows that the number of function calls to compute $F(n)$ is $2F(n)-1$: https://zhu45.org/posts/2017/Jan/22/num-of-function-calls-in-recursive-fibonacci-routine/
Now, since $F(n) = F(n-1) + F(n-2)$ with $F(0)=F(1)=1$ is a homogeneous second-order linear recurrence with constant coefficients, it has a solution of the form $$ F(n) = c_1 r_1^n + c_2r_2^n $$ where $c_1$ and $c_2$ are constants and $r_1, r_2$ are the roots of the characteristic polynomial $x^2 - x -1 $. Solving, we find that $r_1 = \frac{1}{2} \left(1-\sqrt{5}\right)$, $r_2= \frac{1}{2} \left(1+\sqrt{5}\right)$, and from the initial conditions we have \begin{align} 1 &= F(0) = c_1\left(\frac{1}{2} \left(1-\sqrt{5}\right)\right)^0 + c_2\left(\frac{1}{2} \left(1+\sqrt{5}\right)\right)^0 = c_1+c_2\\ 1 &= F(1) = c_1\left(\frac{1}{2} \left(1-\sqrt{5}\right)\right)^1 + c_2\left(\frac{1}{2} \left(1+\sqrt{5}\right)\right)^1\\ &\implies c_2 = 1-c_1\\ &\quad\implies c_1 = \frac{1}{10} \left(5-\sqrt{5}\right),\quad c_2 = \frac{1}{10} \left(\sqrt{5}+5\right). \end{align} Hence the number of function calls to compute $F(n)$ is $$ \frac{1}{50}\left( \left(\frac{1}{2} \left(1-\sqrt{5}\right)\right)^n +\left(\frac{1}{2} \left(1+\sqrt{5}\right)\right)^n \right) -1. $$
(Note that there are vastly more efficient algorithms for computing the Fibonacci numbers!)