# SICP Solutions

### Chapter 3, Modularity, Objects, and State

#### Exercise 3.27

This is little tricky to understand. Lets break it down piece by piece:

1. memoize is straightforward.
• It takes a procedure ‘f’ and returns another procedure.
• The returned procedure is bound to the environment created by the call to memoize, where a table was created.
• This returned procedure takes an argument x and first checks, if there value available in the table for the key x. If yes, it returns the value.
• If not, it calls the procedure f with x as an argument and saves the result in the table as well as returns the result. Note that f is also available to this returned procedure by the environment.
• Thats it!
2. memo-fib is nothing but the procedure returned by memoize. And f is the lambda function that we passed to memo-fib and which contains the code for fibonacci.
• It may seems a bit tricky that f(the lamda function we passed) is itself calling memo-fib.
• But this is nothing but indirect recursion! ‘memo-fib’ –calls–> f(the lambda function passed to memoize) –calls–> ‘memo-fib’.
• As we can see the recursion calls are for lower values of n and we have a base case at n = 0 and 1.
• The important thing to note that all these recursive calls of memo-fib are executed in the environment where parent environment points to the environment in which memo-fib was created.
• Well, technically mem-fib is created in global environment. When speaking of memo-fib, I am referring to the procedure which the variable memo-fib points to. Thus even if the mem-fib variable belongs to global-env the procedure it points to is created/bound to a different environment.
• Thats it!

Now th last past - Would the scheme still work if we had simply defined memo-fib to be (memoize fib)?

No.

Here things will not work because fib itself calls fib recursively thus no table lookups happen.