Memoization python function

Question

Here's a little piece of code which converts every function to its memoization version.

def memoize(f): # Memoize a given function f
    def memf(*x):
        if x not in memf.cache:
            memf.cache[x] = f(*x)
        return memf.cache[x]

    memf.cache = {}
    return memf

For instance, if we have a function fib as follows which returns the nth Fibonacci number:

def fib(n):
    if n < 2:
        return 1
    else:
        return fib(n-1) + fib(n-2)

Now, the above function can be memoized by using

fib = memoize(fib)

Everything is fine up to this point but what I can't understand is that if we do something like this, instead of:

fib = memoize(fib)

we instead do:

fib2 = memoize(fib)

the function fib2 isn't a memoized function of fib. When we run fib2 it runs like ordinary fib. Please explain why this memoize function gets applied to say a function f if and only if we use:

f = memoize(f)

The memoization code is taken from 6.00x a MOOC provided by edx.org. It's not running right now that's why I have come here to ask.

Answer 1

Because when fib2 recursively calls

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

that is the original, un-memoized version; you only get the benefit of the decorator on the first call to fib2, not all the recursive calls to vanilla fib.

Here's what happens:

1. When you call fib2, you are really calling memf, which
2. calls fib in turn if the arguments aren't in the cache (as they won't be on the first call), then
3. fib, being recursive calls fib. This is not the decorated version fib2, so all of the rest of the recursive calls aren't being memoized.

If you call fib2 again with the same arguments, that will be returned from the cache, but you have lost most of the benefit.

You can create decorated functions in general using:

decorated = decorator(original)

but as your function being decorated is recursive, you run into problems.

---

Below is a demo example. Create two identical fib functions, fib_dec and fib_undec. Modify the decorator to tell you what it's doing:

def memoize(f): # Memoize a given function f
    def memf(*x):
        print("Memoized call.")
        if x not in memf.cache:
            print("Filling cache.")
            memf.cache[x] = f(*x)
        else:
            print("Cache retrieve.")
        return memf.cache[x]
    memf.cache = {}
    return memf

Then run:

fib_dec = memoize(fib_dec) # fully memoized
fib_undec_1 = memoize(fib_undec) # not fully memoized

print("Calling fib_dec(2)")
print(fib_dec(2))
print("Calling fib_dec(1)")
print(fib_dec(1))
print("Calling fib_undec_1(2)")
print(fib_undec_1(2))
print("Calling fib_undec_1(1)")
print(fib_undec_1(1))
print("Calling fib_undec_1(2)")
print(fib_undec_1(2))

This will give:

Calling fib_dec(2) # fully decorated
Memoized call.
Filling cache.
Memoized call.
Filling cache.
Memoized call. # recusive calls all memoized
Filling cache.
2
Calling fib_dec(1)
Memoized call.
Cache retrieve. # previous recursive result cached
1
Calling fib_undec_1(2) # not fully memoized
Memoized call. # only one memoized call, recursion not memoized
Filling cache.
2
Calling fib_undec_1(1)
Memoized call.
Filling cache. # recursive result not cached
1
Calling fib_undec_1(2)
Memoized call.
Cache retrieve. # but original call is cached
2