1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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... $\endgroup$ Jul 13 '13 at 1:49
  • $\begingroup$ This shows that $F_n = F_n \cdot 1$> $\endgroup$ Jul 13 '13 at 1:55
  • 1
    $\begingroup$ ... 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. $\endgroup$
    – A.E
    Jul 13 '13 at 5:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.