Exercise 4.29.  Exhibit a program that you would expect to run much more 
slowly without memoization than with memoization. Also, consider the 
following interaction, where the id procedure is defined as in exercise 
4.27  and count starts at 0:

(define (square x)
  (* x x))
;;; L-Eval input:
(square (id 10))
;;; L-Eval value:
<response>
;;; L-Eval input:
count
;;; L-Eval value:
<response>

Give the responses both when the evaluator memoizes and when it does 
not.

————————————————————————————————————————————————————————————————————————

(define (f x)
  (if (= x 0)
      1
      (* x (f (- x 1)))))

This should be slower without memoization, as x is used three times in 
the body of the function, and will be calculated again each time.

This is a more dramatic example:

(define (repeat f n x) ;; apply function f to argument x, n times
  (if (= n 0)
      x
      (repeat f (- n 1) (f x))))

(define (power-of-two n)
  (repeat double n 1))

(define (double x) (+ x x))

If we evaluate:

(power-of-two 3)

The recursive call in the body of repeat will evaluate to:

(repeat double (- n 1) (double 1))

The (- n 1) expression is a primitive application and will be strict, 
but the (double 1) will be a thunk.  If it is evaluated every time it 
is used, instead of stored, then what looks like an iterative process 
above will actually have exponential runtime and memory usage.

Without memoization:

(define (square x)
  (* x x))
;;; L-Eval input:
(square (id 10))
;;; L-Eval value:
100
;;; L-Eval input:
count
;;; L-Eval value:
2 ;; count was incremented twice because (id 10) was evaluated twice

With memoization:

(define (square x)
  (* x x))
;;; L-Eval input:
(square (id 10))
;;; L-Eval value:
100
;;; L-Eval input:
count
;;; L-Eval value:
1