(defun fib (n) (if (< n 2) 1 (+ (fib (1- n)) (fib (- n 2))))) > (fib 19) 6765 > (time (fib 19)) cpu time (non-gc) 13134 msec user, 617 msec system cpu time (gc) 483 msec user, 0 msec system cpu time (total) 13617 msec user, 617 msec system real time 14453 msec 6765というように14秒程度の時間がかかっている. このfibの定義を見るとわかるように,(fib 19)をするために (fib 18)と(fib 17)が呼ばれ,(fib 18)をするために(fib 17)が また呼ばれる.しかし,それぞれの(fib 17)では定義どおりの 計算をそれぞれ実行してしまう. そこで,(fib 17)の計算結果が 出たところでその値を保存し,次に(fib 17)が呼ばれるとその 記憶値を利用するという方法をとれば 計算時間の大幅な短縮が期待される. ここで記憶するデータは,引数と計算結果の対である.