Wrong result if a recursive function is called twice successively with different parameters

Question

I have this recursive function:

def coinChange(coins, amount: int, minimum = float('inf'), memo={}) -> int:
  if amount in memo: return memo[amount]

  if amount < 0: return -1
  if amount == 0: return 0
  for coin in coins:
    x = coinChange(coins, amount - coin, minimum - 1, memo)
    minimum = min(x, minimum) if x != -1 else minimum
    if minimum == 0: break

  memo[amount] = -1 if minimum == float('inf') else minimum + 1
  return -1 if minimum == float('inf') else minimum + 1

When I print this:

print(coinChange([2], 3)) #-1

It shows -1, which is correct. But, when I print this:

print(coinChange([1,2,5], 11)) #3
print(coinChange([2], 3)) #the correct answer is -1 but it's showing 2

It shows 3 then 2. As you can see, the result of print(coinChange([2], 3)) weirdly changed from -1 to 2.

The memo is the reason for causing that wrong answer. But I don't know how to update the function so that memo is re-initiated before each first call of coinChange, and I don't want to do it manually like this: print(coinChange([2], 3, memo = {})).

Answer 1

The issue you mention isn't given with the code you share because of the following

x = coinChange(coins, amount - coin, minimum - 1, memo={})

To use your memo, you need pass it to the recursive calls

x = coinChange(coins, amount - coin, minimum - 1, memo=memo)

---

Effectivly you shouldn't use a mutable object as default variable, because multiple calls will share the same instance, the issue is to use a None

def coinChange(coins, amount: int, minimum=float('inf'), memo=None) -> int:
    if memo is None:
        memo = {}
    ...