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

Question

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?

Answer 1

Unwrap it:

$$F[4]$$ $$= F[3] + F[2]$$ $$= F[2] + F[1] + F[1] + F[0] $$ $$= F[1]+F[0]+ F[1] + F[1] + F[0]$$ $$= 3F[1]+2F[0]$$

So, it gets called three times.

Answer 2

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