SICP Exercise 3.27

Question

Memoization (also called tabulation) is a technique that enables a procedure to record, in a local table, values that have previously been computed. This technique can make a vast difference in the performance of a program. A memoized procedure maintains a table in which values of previous calls are stored using as keys the arguments that produced the values. When the memoized procedure is asked to compute a value, it first checks the table to see if the value is already there and, if so, just returns that value. Otherwise, it computes the new value in the ordinary way and stores this in the table. As an example of memoization, recall from 1.2.2 the exponential process for computing Fibonacci numbers:

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

The memoized version of the same procedure is

(define memo-fib
  (memoize
   (λ (n)
     (cond ((= n 0) 0)
           ((= n 1) 1)
           (else
            (+ (memo-fib (- n 1))
               (memo-fib (- n 2))))))))

where the memoizer is defined as

(define (memoize f)
  (let ((table (make-table)))
    (λ (x)
      (let ((previously-computed-result
             (lookup x table)))
        (or previously-computed-result
            (let ((result (f x)))
              (insert! x result table)
              result))))))

Draw an environment diagram to analyze the computation of (memo-fib 3). Explain why memo-fib computes the \(n^{th}\) Fibonacci number of steps proportional to \(n\). Would the scheme still work if we had simply defined memo-fib to be (memoize fib)?

Answer

The memoize method works by maintaining a table with all previously computed results. If a result exists for value x, it is returned. Otherwise, the result of (f x) is added to the table and then returned.

As to the time requirement, we are going to assume that lookup and insert! are going to operate in constant time. In that case, we have half the number of recursive calls per iteration of the fib function, which will bring our complexity down to \(\Theta(n)\).

If we simply define memo-fib as (memoize fib), it will still work (i.e. output a correct result), but it will not actually be memoized, since the recursive call actually goes to fib and not to memo-fib.