# MAT385 Recursion Examples

### From www.norsemathology.org

## 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),

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, , 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 as .

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

- assume that
*F*(*n*+ 1) =*F*(*n*) +*F*(*n*- 1)) and solve for the ratio to get two solutions for the ratio. - You can write
*F*(*n*) as a**linear combination**of the two solutions:*F*. - 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),

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:

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

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

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

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