(load "table.txt") (define (memoize f) (let ((table (make-table))) (lambda (x) (let ((previously-computed-result (lookup x table))) (or previously-computed-result (let ((result (f x))) (insert! x result table) result)))))) (define (fib n) (display "fib ") (display n) (newline) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (fib (- n 1)) (fib (- n 2)))))) ; 1 ]=> (fib 5) ; fib 5 ; fib 3 ; fib 1 ; fib 2 ; fib 0 ; fib 1 ; fib 4 ; fib 2 ; fib 0 ; fib 1 ; fib 3 ; fib 1 ; fib 2 ; fib 0 ; fib 1 ; ;Value: 5 (define incorrect-memo-fib (memoize fib)) ; Memoizing a function in this way memoizes calls from the repl, but does not ; not memoize the recursive calls a function makes to itself. ; 1 ]=> (incorrect-memo-fib 5) ; fib 5 ; fib 3 ; fib 1 ; fib 2 ; fib 0 ; fib 1 ; fib 4 ; fib 2 ; fib 0 ; fib 1 ; fib 3 ; fib 1 ; fib 2 ; fib 0 ; fib 1 ; ;Value: 5 ; ; 1 ]=> (incorrect-memo-fib 5) ; ; ;Value: 5 (define memo-fib (memoize (lambda (n) (display "memo-fib ") (display n) (newline) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (memo-fib (- n 1)) (memo-fib (- n 2)))))))) ; 1 ]=> (memo-fib 5) ; memo-fib 5 ; memo-fib 3 ; memo-fib 1 ; memo-fib 2 ; memo-fib 0 ; memo-fib 4 ; ;Value: 5 ; In computing fib(n), the lambda is only called n + 1 times before the memo ; contains values of fib for 0 ... n. Each of these calls does constant work ; excluding the recursive calls to itself. This includes at most two calls to ; memo-fib which may be answered in constant time from the memo. Thus the total ; time is O(n).