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.