Problem when calling memoized recursive method in python

31 views Asked by At

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,

0

There are 0 answers