Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

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

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:

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

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 = {})).

Any help?

>Solution :

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 = {}
    ...
Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading