The following behaviour happened when I was trying to memoize a function and I can’t quite wrap my head around it. For the sake of presenting a MWE here is a function that computes (integer, non-negative) powers of 2 in an unnecessarily recursive way:
def power2(n):
if n == 0: return 1
return 2 * power2(n-1)
And here is my attempt to memoize it with a dictionary:
def power2(n, memo={}):
if n in memo: return memo[n]
if n == 0: return 1
memo[n] = 2 * power2(n-1, memo)
return memo[n]
This works like a charm, but for the sake of debugging I’d also like the function to print what it’s doing upon calling. So here is a very talkative function that does the same:
def power2(n, memo={}):
print("Computing 2 **", n)
if n in memo:
print(" I have 2 **", n, "in my memo! Returning.")
return memo[n]
print(" I don't have 2 **", n, "in my memo. Computing...")
if n == 0:
print(" The base case for induction has been reached. Returning.")
return 1
p = 2 * power2(n-1, memo)
print("2 **", n, "=", p)
memo[n] = p
return memo[n]
Now if I call
power2(6)
the console prints
Computing 2 ** 4
I don't have 2 ** 4 in my memo. Computing...
Computing 2 ** 3
I don't have 2 ** 3 in my memo. Computing...
Computing 2 ** 2
I don't have 2 ** 2 in my memo. Computing...
Computing 2 ** 1
I don't have 2 ** 1 in my memo. Computing...
Computing 2 ** 0
I don't have 2 ** 0 in my memo. Computing...
The base case for induction has been reached.
Returning 2 ** 0 = 1
Returning 2 ** 1 = 2
Returning 2 ** 2 = 4
Returning 2 ** 3 = 8
Returning 2 ** 4 = 16
Which is what I expected: the memo here serves absolutely no purpose because we always pass a different argument to the function everytime we call it.
What I don’t understand is that, if I call the function twice on the same argument, eg:
power2(4)
power2(4)
what I get is the following:
Computing 2 ** 4
I don't have 2 ** 4 in my memo. Computing...
Computing 2 ** 3
I don't have 2 ** 3 in my memo. Computing...
Computing 2 ** 2
I don't have 2 ** 2 in my memo. Computing...
Computing 2 ** 1
I don't have 2 ** 1 in my memo. Computing...
Computing 2 ** 0
I don't have 2 ** 0 in my memo. Computing...
The base case for induction has been reached.
Returning 2 ** 0 = 1
Returning 2 ** 1 = 2
Returning 2 ** 2 = 4
Returning 2 ** 3 = 8
Returning 2 ** 4 = 16
Computing 2 ** 4
I have 2 ** 4 in my memo! Returning.
Similarly if the second time I call the function I pass, as an argument, a lower number (it just fetches the value from memo
) or a higher number (it performs recursion only until it finds the corresponding key in memo
).
Questions:
- Why does the function
power2
remember the content ofmemo
? If I call it without passing the argumentmemo
, why doesn’t it default at{}
? - If
power2
remembersmemo
, does it mean that I can also access its content after calling the function the first time? If so, how? - Suppose the intended behaviour is for the function to actually forget the dictionary unless I pass one as second argument. Is there a smart/standard way to implement it, or should I just keep calling functions explicitly passing
memo={}
? (In this case it does not seem very useful to even assign a default empty dictionary tomemo
in the function definition!)
Thanks for any help