]> git.rkrishnan.org Git - sicp.git/blob - src/sicp/ex3_27.rkt
Solution to 4.44. A bit too verbose. Can be improved by better
[sicp.git] / src / sicp / ex3_27.rkt
1 #lang r5rs
2
3 (define (fib n)
4   (cond
5     ((= n 0) 0)
6     ((= n 1) 1)
7     (else (+ (fib (- n 1))
8              (fib (- n 2))))))
9
10 (define memo-fib
11   (memoize (lambda (n)
12              (cond 
13                ((= n 0) 0)
14                ((= n 1) 1)
15                (else (+ (memo-fib (- n 1))
16                         (memo-fib (- n 2))))))))
17
18 (define (memoize f)
19   (let ((previous-output (make-table)))
20     (lambda (x)
21       (let ((lookup-result (lookup x previous-output)))
22         (if lookup-result
23             lookup-result
24             (let ((result (f x)))
25               (insert! x result previous-output)
26               result))))))
27           
28 #|
29
30 If we define memo-fib as
31
32 (define memo-fib
33   (memoize fib))
34
35 and say, call (memo-fib 10), then, we cache the result of calling fib with n=10.
36 But (fib n) calls (fib (- n 1)) and (fib (- n 2)) and this way of calling memo-fib won't cache those intermediate values.
37
38 On the other hand, if we define memo-fib the way it is defined above, all intermediate calls to memo-fib also goes through memoize call and hence will get cached in the results table. Hence this is much more efficient.
39
40 |#