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