Name: Anonymous 2008-04-17 14:00
We all enjoy showing off how elegant our implementation of the Fibonacci sequence is in Haskell or Scheme or whatever. But, frankly, they suck. Even if you're using tail recursion to avoid fucking up the stack it's still terribly inefficient.
Here is the correct way to implement the Fibonacci sequence (in Scheme):
Here is the correct way to implement the Fibonacci sequence (in Scheme):
(define (fibonacci x)
(let ((phi (/ (+ 1 (sqrt 5)) 2)))
(+ (/ (+ (expt phi x) (expt (- 1 phi) (- x 2))) (+ (expt phi 2) 1)) (/ (- (expt phi (- x 1)) (* phi (expt (- 1 phi) (- x 2)))) (+ (expt phi 2) 1)))))