問題3.27

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

;(time (fib 35))
; real   3.050
; user   3.010
; sys    0.040
9227465

(define (memorize f)
  (let ((table (make-table)))
    (let ((get (table 'lookup-proc))
          (put (table 'insert-proc!)))
      (lambda (x)
        (let ((previously-computed-result (get (list x))))
          (or previously-computed-result
              (let ((result (f x)))
                (put (list x) result)
                result)))))))

(define memo-fib
  (memorize (lambda (n)
              (cond ((= n 0) 0)
                    ((= n 1) 1)
                    (else (+ (memo-fib (- n 1))
                             (memo-fib (- n 2))))))))

;(time (memo-fib 35))
; real   0.000
; user   0.000
; sys    0.000
9227465

;引数自身以下の計算をすべてそのまま計算しなおすようなアルゴリズムなので、
;メモ化するとすべてそのままルックアップすればすむので。

(define memo-fib
  (memorize fib))

;では働かない。

(define fib
  (memorize fib))

;ならおｋ。