# How many repeated steps in a Fibonacci recursive function [closed]

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.

• Any thoughts? Can you, say, solve the example case you set?
– lulu
Commented Feb 19, 2020 at 22:49
• Just do the first few cases by hand. You should be able to spot the almost comically apt pattern pretty quickly. Commented Feb 19, 2020 at 22:59
• @lulu when i draw out the recursive tree it seems only the root node and one of its child node is not repeated but rest are repeated. Now the issue im having is that the last level of the tree is not always full so how can i factor that into my calculation? Commented Feb 19, 2020 at 23:33
• Question has surely been asked & answered on this site many times before. See, for example, the questions listed under "Related". Commented Feb 20, 2020 at 0:32
• See here: zhu45.org/posts/2017/Jan/22/… Commented Feb 20, 2020 at 0:51

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.$$