0

I'm following a course on dynamic programming using recursion and memoization to reduce the time complexity of the algorithm. I have found that when running two different examples serialised in the same python process, the results are not the one expected, showing some kind of memory between function calls. I paste the code here:

def can_sum(target_sum, numbers, memo={}):
    if target_sum in memo: return memo[target_sum]
    if target_sum == 0: return True
    if target_sum < 0: return False

    for num in numbers:
        remainder = target_sum - num
        if can_sum(remainder, numbers, memo) == True:
            memo[target_sum] = True
            return True
    
    memo[target_sum] = False
    return False

if __name__ == "__main__":
    print(can_sum(7, [2, 3]))  # True
    print(can_sum(7, [2, 4]))  # False

The output is:

True
True

when in fact, should be:

True
False

Does someone has an idea about what is going on here? If I comment the first call, then the result obtained for the second call is the one expected.

Many thanks in advance,

jordi
  • 1
  • 2
  • Both "root" calls share the same cache, not just the non-root recursive calls. – chepner Jan 02 '22 at 22:00
  • you are memoizing on target sum .... its the same sum of 7 so it clearly exists – Joran Beasley Jan 02 '22 at 22:00
  • Thanks for the comments. After some more investigation, I also find out the `functools.lru_cache` decorator can be used to cleanly memoinize the algorithm, avoiding the explicit modification of the method shown in my example. – jordi Jan 03 '22 at 13:24
  • You are leaking memo dictionary between calls. For the intended purpose you can think of memo={} argument as being a global variable. But that's not your "real" problem. In fact that is probably your intention. The actual problem is that what you store in the memo cache is incomplete. In your example you are just storing the number 7 as key when in fact the key to memo should probably be `(target_sum, tuple(numbers))` – Tiago Coutinho Jan 03 '22 at 18:05

0 Answers0