Suppose that a recursive routine were invoked to calculate F(4). How many times would a recursive call of F(1) occur?

The definition of a Fibonacci number is as follows:

$$F_0=0\\F_1=1\\F_n=F_{n-1}+F_{n-2}\text{ for } n\geq 2$$ Suppose that a recursive routine were invoked to calculate $F_4$. How many times would a recursive call of $F_1$ occur?

Do I use n=1?

For small $n$ the most straightforward way to answer the question is the one suggested by Orangutango: unwrap the recurrence. However, as the comments under that answer may suggest, there’s a general result almost ready to hand.

Suppose that the recursive routine requires $c_n$ calls of $F_1$ to evaluate $F_n$. Clearly $c_0=0$ and $c_1=1$. For $n>1$ we have $F_n=F_{n-1}+F_{n-2}$, where evaluating $F_{n-1}$ requirse $c_{n-1}$ calls of $F_1$, and evaluating $F_{n-2}$ requirse $c_{n-2}$ calls of $F_1$. Thus, evaluation of $F_n$ will require $c_{n-1}+c_{n-2}$ calls of $F_1$, and we must have $c_n=c_{n-1}+c_{n-2}$ for all $n\ge2$. But all of this just says that the sequence $\langle c_n:n\ge 0\rangle$ satisfies the same recurrence and has the same initial values as the Fibonacci sequence $\langle F_n:n\ge 0\rangle$, so it must be the same sequence: $c_n=F_n$ for all $n\ge 0$.

Unwrap it:

$$F$$ $$= F + F$$ $$= F + F + F + F$$ $$= F+F+ F + F + F$$ $$= 3F+2F$$

So, it gets called three times.

• Which, not coincidentally, is $F_4$ - it's pretty obvious that computing $F_n$ in this way must ultimately call $F_1$ exactly $F_n$ times... Jul 13 '13 at 1:49
• This shows that $F_n = F_n \cdot 1$> Jul 13 '13 at 1:55
• ... and I think it is a good illustration of how many calls a naïve recursive algorithm would make to the bottom out case, and it is a method that generalizes for other recurrences, not just the Fibonacci sequence. Mentally unwrapping a recurrence helped me understand the principle of recursion when I first learned this type of material. If you have something more insightful, please do share.
– A.E
Jul 13 '13 at 5:32