# MAT385 Recursion Examples

## Fibonacci Numbers

The Fibonacci numbers are generally defined via the recursive algorithm

F(1)=1
F(2)=1
F(n)=F(n-1)+F(n-2), $n\ge 3$


These numbers appear all over in nature: in pinecones, pineapples, artichokes, pussywillows, daisys, etc.

But they started out as pairs of immortal bunnies, which mature in a month, and then produce a single new pair every month thereafter: This diagram illustrates why the recursive algorithm works:

• we assume that the number of bunny pairs arising from a single immature pair is given by the sequence F(n), with generations 1, 2, 3, ....
• We notice that at the third generation, the total population of pairs is given by the sum of two new populations: a perfect copy of the original tree, starting from the first generation, and a perfect copy of the original tree starting from the second generation.
• Hence F(3) = F(2) + F(1)

I class I presented the following algorithm in lisp for calculating the nth term in this sequence:

(defun fib(n)
(case n
;; the following two cases are the basis cases:
(1 1)
(2 1)
;; and, if we're not in a basis case, then we should use recursion:
(t (+ (fib (- n 1)) (fib (- n 2))))
)
)


If you calculate the ratio of successive Fibonacci numbers, $\frac{F(n)}{F(n-1)}$, you notice something interesting happening:

           n         ratio
2             1
3             2
4       1.50000
5       1.66667
6       1.60000
7       1.62500
8       1.61538
9       1.61905
10       1.61765
11       1.61818
12       1.61798
13       1.61806
14       1.61803
15       1.61804
16       1.61803
17       1.61803
18       1.61803
19       1.61803
20       1.61803


It appears that the ratio $\frac{F(n)}{F(n-1)} \longrightarrow \approx 1.61803$ as $n \longrightarrow \infty$.

We can use this idea to find the closed form solution of F(n):

1. assume that $\frac{F(n+1)}{F(n)}=\frac{F(n)}{F(n-1)}$
in the limit. Use the recursive step (in the form F(n + 1) = F(n) + F(n - 1)) and solve for the ratio $\frac{F(n)}{F(n-1)}$ to get two solutions for the ratio.
2. You can write F(n) as a linear combination of the two solutions: $F(n)=ar_1^{n-1}+br_2^{n-1}$
Find the closed form solution of F.
3. Check the formula for the first four Fibonacci numbers.

## How many invocations?

As we were talking about computing the Fibonacci numbers via the recursive algorithm

F(1)=1
F(2)=1
F(n)=F(n-1)+F(n-2), $n\ge 3$


we realized that the computations would grow excessively as n gets large. Consequently the time it takes to compute a Fibonacci number this way grows excessively long as n grows:

> (time (fib 20))
The evaluation took 0.02 seconds; 0.00 seconds in gc.
6765
> (time (fib 30))
The evaluation took 2.85 seconds; 0.05 seconds in gc.
832040
> (time (fib 35))
The evaluation took 31.61 seconds; 0.70 seconds in gc.
9227465


We argued this way: as soon as I go to calculate F(n), I need to invoke F two more times -- to compute F(n-1) and F(n-2). So it looks like the number of invocations is going to double each time. In addition, the invocation of F(n-1) is going to be wasteful, because it's going to invoke F(n-2) again (already invoked by F(n)). So we're redoing calculations -- very bad.

In class I asserted that the growth in the number of calculations is not really purely exponential. In this exercise, I want you to find out how bad it is. In order to do so, you need to find a recurrence relation for the number of invocations of F. Use a modified "expand, guess, check" strategy:

1. How many times will you invoke F if n=1?
2. How many times will you invoke F if n=2?
3. How many times will you invoke F if n=3?

4. How many times will you invoke F if n=4?

5. How are the invocations of F at n related to the invocations of F at n-1 and n-2?

6. Now, can you quickly write the first 10 terms in the sequence?