DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Snippets has posted 5883 posts at DZone. View Full User Profile

Memoizing Fibonacci Sequence Generator

03.16.2006
| 2256 views |
  • submit to reddit
        Generates a list containting the fibonacci-sequence out to n. It is also a memoizing function so a second call to the same n will be greatly faster.


(let ((cache (make-hash-table :test #'equal)))
	     (defun fibonacci-sequence (n)
	       "Calculates the a Fibonacci Sequence of n integers."
	       (declare (optimize speed))
	       (declare (type number n))
	       (labels ((get-fib (x seq)
			  (if (= x n)
			      (setf (gethash n cache) (nreverse seq))
			      (if (cdr seq)
				  (get-fib (+ x 1) (push (+ (first seq)
							    (second seq))
							 seq))
				  (get-fib (+ x 1) (push 1 seq))))))
		 (or (gethash n cache)
		     (get-fib 0 nil))))
	     (defun fib-hash (n)
	       (gethash n cache))
	     (defun fib-clear ()
	       (setf cache (make-hash-table :test #'equal))))