# 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\geq 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 $n^{th}$ 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\geq 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?

So why is it so easy to "recursively" write the first 10 terms? Because you're storing pairs.