Memoization Python Function

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.cach

Solution 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:

defmemoize(f): # Memoize a given function fdefmemf(*x):
        print("Memoized call.")
        if x notin 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