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

From: John Clements (clements at brinckerhoff.org)
Date: Thu Jan 8 02:46:16 EST 2009

On Jan 7, 2009, at 11:00 PM, Richard Cleis wrote:

> (fib 100) is a big number for that function; it'll take awhile to  
> compute.  Are you sure it is freezing? When you click the stop sign,  
> does the program stop?

Actually, the problem is that you turned a linear computation into an  
exponential one.  Here's one way to solve it:

(require (planet dherman/memoize))

(define/memo (fib n)
  (if (< n 3)
  (+ (fib (- n 1)) (fib (- n 2)))))

(fib 100)



John Clements

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 2484 bytes
Desc: not available
URL: <http://lists.racket-lang.org/users/archive/attachments/20090107/a8ed1115/attachment.p7s>

Posted on the users mailing list.