<< Previous exercise (3.26) | Index | Next exercise (3.28) >>
The number of steps is not proportional to n. It is O(n^2) due to assoc procedure. This is confirmed experimentally. The order of growth is very similar to quadratic. With an increase in n by 10 times, the calculation time increased by about 100 times. You can easily check it yourself.
sam
(define memo-fib (memoize fib))willl not work because when evaluating code for (memoize fib); (fib x) will be evaluated whose enclosing envrionment is the global environment and thus memoization is lost.
Manu Halvagal
(define memo-fib (memoize fib))will actually work but not very well. For example, the call (memo-fib 3) would memoize fib(3), but not fib(1) or fib(2) because these are recursive calls to the unmemoized version of the function. The proper implementation memoizes even the recursive calls.
John-Gaines
Instead of recoding fib into memo-fib as shown in SICP (which seems like a very error-prone way of adding memoize to an existing function). The following works in DrRacket using #lang racket
(set! fib (memoize fib))It sets fib in the global environment to (memoize fib) which also causes the recursive calls within fib to call the redefined version.
sam
This will not work under the environment model for evaluation as described in the book. This is because f in memoize will be bound to procedure object that was created via lambda expression for fib; and this procedure object still has global envrionment as the enclosing environment. (note, all procedures can be created only via lambda expressions).
ericwen229
This WILL work as the fib in global environment HAS CHANGED. When f in memoize gets invoked and searches for fib it will find the redefined version of fib (in global environment as its enclosing environment), which is decorated by memoize.