0

I just learned about memoization for optimizing recursive functions. The solution for memoizing a Fibonacci function was provided as:

def fib_memo(n, memo={}):
    if n in memo : return memo[n]  
    if n in [1,2]: return 1
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

print(fib_memo(50))

>>> 12586269025

However, I have found that the following variation (which does not pass memo in the recursive calls) also works as expected, but I am unable to explain how/why:

def alt_memo(n, memo={}):
    if n in memo : return memo[n]  
    if n in [1,2]: return 1
    memo[n] = alt_memo(n-1) + alt_memo(n-2)
    return memo[n]

print(alt_memo(50))

>>> 12586269025

When I run alt_memo(n), is my compiler optimizing the code behind the scenes and adding memo in the recursive calls, or is it in fact not necessary to include memo in the recursive calls?

If not necessary, how is it that the recursive calls are receiving/passing-along the memo object (being as that the function initially sets the memo parameter to an empty dictionary, when otherwise unspecified)?

ZwiTrader
  • 195
  • 1
  • 2
  • 12
  • It works because you're modifying the dictionary in place, and all the calls share that same default value. – Barmar Dec 23 '21 at 16:53
  • Thanks @match -- but if the function definition specifies that `memo={}` when undeclared, why does a recursive call that fails to pass memo not cause memo to become an empty dictionary during the subsequent execution of the call? – ZwiTrader Dec 23 '21 at 16:54
  • Sorry I misread the code. It's actually a different issue - see this related question: https://stackoverflow.com/questions/26320899/why-is-the-empty-dictionary-a-dangerous-default-value-in-python – match Dec 23 '21 at 16:54
  • 1
    @ZwiTrader The default value is only evaluated once, when the function is defined, not every time the function is called. – Barmar Dec 23 '21 at 16:55
  • @Barmar -- thanks this is very helpful to know (and completely clarifies the issue). – ZwiTrader Dec 23 '21 at 16:57

0 Answers0