4.29 Exercise 4.29

A simple program that performs much more slowly without memoization:

(define (fib n)

(cond ((= n 0) 1)

((= n 1) 1)

(else (+ (fib (- n 1)) (fib (- n 2))))))

(define (square x) (* x x))

(square (fib 10))

Now consider the following program:

(define count 0)

(define (id x)

(set! count (+ count 1))

x)

(define (square x) (* x x))

(square (id 10))

count

With memoization, the result is 1 – (id 10) gets evaluated, and increments count, only once, even though square references its value twice. However, without memoization, count is actually 2, because x is referenced by name twice in the body of square.