[plt-scheme] Dr.Scheme freezes on (fib 100) recursion

On Jan 8, 2009, at 1:45 AM, laa laa wrote:

> my son and i coded a program to compute fibonacci sequences. it  
> works fine for low numbers, but when you try to do something higher  
> like (fib 100) Dr.Scheme freaks out and freezes up. we're wondering  
> what's going on? is there a reason for this. . . .
>
> (define (fib n)
>   (if (< n 3)
>       1
>   (+ (fib (- n 1)) (fib (- n 2)))))

This is one of my favorite (for classroom use) examples of algorithm  
(in)efficiency.  It is obviously a "correct" definition, but think  
about how long it takes.  The only number it actually knows is 1, and  
the only operation it does is +, and it never uses a computed result  
more than once, so if the right answer is (say) 350 quintillion, it  
has to do around 350 quintillion "+" operations to add up to that  
answer.  At a billion operations per second, that's eleven thousand  
years.  (Interestingly enough, it only requires a stack depth of 100,  
so stack overflow isn't a problem: if you can keep the computer  
running DrScheme for eleven thousand years without anybody tripping  
over the power cord or cosmic rays disrupting the RAM, it WILL  
produce the right answer.)

John posted an alternative definition, using the technique of "memo- 
ization": in a nutshell, every time the function computes the answer  
to a question, it stores the answer in a table (indexed by the  
function input) so the next time it is asked the same question, it  
just re-uses the answer from the table rather than re-computing it.   
All of that is happening behind the scenes in the "memoize" package,  
although you could easily write your own memoized version of the  
function.  With this simple transformation, the algorithm becomes  
linear-time in n, so it takes approximately 100 "+" operations rather  
than 350 quintillion.

Here's another approach which doesn't require a look-up table.  When  
you say "Fibonacci sequences", you're more right than you may  
realize: there is not ONE Fibonacci sequence but infinitely many,  
each sequence determined by a different first two elements.  If you  
start with F(1)=1, F(2)=1, you get "the usual" Fibonacci sequence,  
but you can also start from F(1)=17, F(2)=-4 or any other starting  
place you wish.  So we define

; fib : nat-num -> nat-num

(check-expect (fib 1) 1)
(check-expect (fib 2) 1)
(check-expect (fib 3) 2)
(check-expect (fib 4) 3)
(check-expect (fib 5) 5)
(check-expect (fib 6) 8)

(define (fib n)
   (general-fib 1 1 n))

; general-fib : num (prev2) num (prev1) nat-num(n)
; computes the n-th Fibonacci number in the sequence whose 1st and  
2nd elements are prev2 and prev1

(check-expect (general-fib 17 -4 1) 17)
(check-expect (general-fib 17 -4 2) -4)
(check-expect (general-fib 17 -4 3) 13)
(check-expect (general-fib 17 -4 4) 9)
(check-expect (general-fib 17 -4 5) 22)

Now, how to define this?  Consider the sequence starting with the  
numbers x and y, then chop off the first number.  You still have a  
Fibonacci sequence, but now it starts with y and x+y, and the nth  
element of the old sequence is the n-1-th element of the new  
sequence.  This gives us a natural recursive definition:

(define (general-fib prev2 prev1 n)
   (cond [(<= n 1) prev2]
         [(= n 2) prev1]
         [else (general-fib prev1 (+ prev2 prev1) (- n 1))]))

This version turns out to be much more efficient (all times are in  
milliseconds):
 > (time (fib 10))
cpu time: 3 real time: 4 gc time: 0
55
 > (time (fib 100))
cpu time: 4 real time: 5 gc time: 0
354224848179261915075
 > (time (fib 1000))
cpu time: 34 real time: 49 gc time: 0
434665576869374564356885276750406258025646605173717804024817290895365554 
179490518904038798400792551692959225930803226347752096896232398733224711 
61642996440906533187938298969649928516003704476137795166849228875


Moral of the story: sometimes generalizing the problem makes it  
easier to solve.

Stephen Bloch
sbloch at adelphi.edu