CODEWITHSUNDEEP
pythonrecursionmemoization
JohnJamesSmith0
JohnJamesSmith0

Reputation: 219

Why does this memoizer work on recursive functions?

I can't figure out why the following code is makes fib run in linear rather than exponential time.

def memoize(obj):
    """Memoization decorator from PythonDecoratorLibrary. Ignores
    **kwargs"""

    cache = obj.cache = {}

    @functools.wraps(obj)
    def memoizer(*args, **kwargs):
        if args not in cache:
            cache[args] = obj(*args, **kwargs)
        return cache[args]
    return memoizer

@memoize
def fib(n):
    return n if n in (0, 1) else fib(n-1) + fib(n-2)

For example, fib(100) doesn't completely blow up like I expected it to.

My understanding is that @memoize sets fib = memoize(fib). So when you call fib(100), seeing that 100 is not in the cache, it will call obj on 100. But obj is the original fib function, so shouldn't it take just as long (on the first evaluation) as if we didn't have memoization at all?

Upvotes: 6

Views: 392

Answers (3)

dragonx
dragonx

Reputation: 15143

"But obj is the original fib function, so shouldn't it take just as long (on the first evaluation) as if we didn't have memoization at all?"

obj (in memoizer) is the indeed original fib function. The trick is that when fib calls itself recursively, it's calling memoize(fib).

def fib(n):
    return n if n in (0, 1) else wrapped(fib(n-1)) + wrapped(fib(n-2))

Where wrapped is the function generated by functools that calls memoize.memoizer. Kinda.

The recursive calls might end up being simple lookups in obj.cache (theoretically O(1)) which is what improves the perf significantly.

Upvotes: 2

shx2
shx2

Reputation: 64308

Names are resolved lexically. Just because you call a function named fib from within a function named fib, that doesn't mean it would necessarilly be the same fib.

A (highly inaccurate) demonstration of what's going on is this:

def fib(n):
    return n if n in (0, 1) else globals()['fib'](n-1) + globals()['fib'](n-2)

Since the decorater affects globals, you get the decorated fib at the time the recursive call occurs.

Upvotes: 4

user395760
user395760

Reputation:

obj in the decorator is indeed the wrapped, unmodified, non-memoized function. However, when said function tries to recurse, it looks up the global name fib, get the memoized wrapper function, and hence also causes the 99th, 98th, ... fibonacci number to be memoized along the way.

Upvotes: 6

Related Questions