Elisp Fibs

fibs.el

;; g'bye stack
(let ()
  (defun f (n)
    (if (< n 2) 1
      (+ (f (- n 1)) (f (- n 2)))))

  (loop for i from 0 upto 20
	collect (f i))
)

;; memoized, little better
(let ((mem (make-hash-table)))
  (puthash 0 1 mem)
  (puthash 1 1 mem)

  (defun f2 (n)
    (let ((has (gethash n mem)))
      (if has
	  has
	(let ((fn (+ (f2 (- n 1)) (f2 (- n 2)))))
	  (puthash n fn mem)
	  fn))))

  (loop for i from 0 upto 20
	collect (f2 i))
)