(define (memoize f)
  (let ((table (make-hash-table)))
    (lambda (x)
      (let ((previously-computed-result (hash-ref table x #f)))
        (or previously-computed-result
            (let ((result (f x)))
              (hash-set! table x result)
              result))))))
 
(define fib
  (memoize (lambda (n)
    (cond ((= n 1) 1)
          ((= n 2) 1)
          (else (+ (fib (- n 1))
                   (fib (- n 2))))))))
 
 
(display (fib 1))
(newline)
(display (fib 2))
(newline)
(display (fib 3))
(newline)
(display (fib 4))
(newline)
(display (fib 5))
(newline)
(display (fib 100))

KGRlZmluZSAobWVtb2l6ZSBmKQogIChsZXQgKCh0YWJsZSAobWFrZS1oYXNoLXRhYmxlKSkpCiAgICAobGFtYmRhICh4KQogICAgICAobGV0ICgocHJldmlvdXNseS1jb21wdXRlZC1yZXN1bHQgKGhhc2gtcmVmIHRhYmxlIHggI2YpKSkKICAgICAgICAob3IgcHJldmlvdXNseS1jb21wdXRlZC1yZXN1bHQKICAgICAgICAgICAgKGxldCAoKHJlc3VsdCAoZiB4KSkpCiAgICAgICAgICAgICAgKGhhc2gtc2V0ISB0YWJsZSB4IHJlc3VsdCkKICAgICAgICAgICAgICByZXN1bHQpKSkpKSkKCihkZWZpbmUgZmliCiAgKG1lbW9pemUgKGxhbWJkYSAobikKICAgIChjb25kICgoPSBuIDEpIDEpCiAgICAgICAgICAoKD0gbiAyKSAxKQogICAgICAgICAgKGVsc2UgKCsgKGZpYiAoLSBuIDEpKQogICAgICAgICAgICAgICAgICAgKGZpYiAoLSBuIDIpKSkpKSkpKQoKCihkaXNwbGF5IChmaWIgMSkpCihuZXdsaW5lKQooZGlzcGxheSAoZmliIDIpKQoobmV3bGluZSkKKGRpc3BsYXkgKGZpYiAzKSkKKG5ld2xpbmUpCihkaXNwbGF5IChmaWIgNCkpCihuZXdsaW5lKQooZGlzcGxheSAoZmliIDUpKQoobmV3bGluZSkKKGRpc3BsYXkgKGZpYiAxMDApKQ==