memoizeというのを使ってみた。

(asdf:oos 'asdf:load-op 'memoize)

(defun fib (n)
  (if (<= n 1)
      1
      (+ (fib (- n 1))
          (fib (- n 2)))))

(memoize:def-memoized-function fibm (n)  (if (<= n 1)
      1                    
      (+ (fibm (- n 1))
          (fibm (- n 2)))))

実行

* (fib 40) ; 結構待たされる

165580141
* (fibm 40) ; 一瞬

165580141

SBCLでベンチマークの取り方がわからん。