# Re: Fibonacci Recursion, What??

• From: Raffael Cavallaro <raffaelcavallaro@pas-d'espam-s'il-vous-plait-mac.com>
• Date: Wed, 26 Sep 2007 01:39:40 -0400

Finally, here's a version by Bradley Lucier, translated by Nicholas Neuss from scheme into common lisp, and only slightly modified by yours truly to handle bogus inputs. It runs faster than any of the other versions posted here so far, and only conses a bit more, but then, it returns two values at every recursive call, fib(n) and fib(n + 1):

(defun fib (n) "Returns f_n f_{n+1}."
(cond ((not (and (integerp n) (>= n 0)))
(error "fibonacci numbers are only defined for integers 0 and greater"))
((zerop n) (values 0 1))
((= n 1) (values 1 1))
((= n 2) (values 1 2)) (t (let ((m (floor n 2))) (multiple-value-bind (f_m f_m+1) (fib m) (let ((f_m^2 (* f_m f_m)) (f_m+1^2 (* f_m+1 f_m+1))) (if (evenp n) (values (- (* 2 f_m+1^2) (* 3 f_m^2) (if (oddp m) -2 2)) (+ f_m^2 f_m+1^2)) (values (+ f_m^2 f_m+1^2) (- (* 3 f_m+1^2) (* 2 f_m^2) (if (oddp m) -2 2))))))))))