Function composition vs decorators, in a memoized recursive Fibonacci sequence generator

Question

I'm practicing memoization to improve recursive functions, so I wrote this memoized Fibonacci generator:

memo = {}
def memo_fibo(n):
    if n not in memo:
        if n < 2:
            memo[n] = n
        else:
            memo[n] = memo_fibo(n - 2) + memo_fibo(n - 1)
    return memo[n]

And this actually works well! Next I wanted to generalize the idea of memoization, I wanted to write a function that basically adds memoization to some other function, so I wrote this:

def memoize(f):
    cache = {}
    def memoized(x):
        if x not in cache:
            cache[x] = f(x)
        return cache[x]
    return memoized

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

mf = memoize(fibo)

But this just doesn't work for some reason, even though I'm just putting one function inside of another. What's even weirder to me is that if you do:

@memoize
def fibo(n):
    if n < 2:
        return n
    return fibo(n - 2) + fibo(n - 1)

Then it works fine. But why? Why is simple function composition not working properly and giving a different result? Is there a syntax error in the way I compose those 2 functions? Or maybe the memoize(f) function is just not built correctly for composition?

I'm asking because I still don't understand decorators very well and if I knew how to make those 2 versions equivalent that'd help me a lot with them.

Answer 1

Your memoize function decorator returns a new function (that you called memoized) that "wraps" the function you give in. The issue is that doing mf = memoize(fibo) you save the new decorated function in the mf function, but since it is recursive, when it does fibo(n - 2) + fibo(n - 1), it still calls the non-decorated original function.

To make it work as expected, you have to overwrite the original function writing fibo = memoize(fibo)

I've found a similar question as your with other explanations, hope that helps: https://stackoverflow.com/a/10757994/19288094