Why does this memoized recursive coin-change function return stale results across calls?

programming web dev
1

I wrote a recursive coin-change helper with memoization. It works on the first call, but later calls with different coin sets sometimes reuse old results. I expected each top-level call to start fresh. What exactly is causing the stale cache here, and what’s the cleanest fix without removing memoization?

function minCoins(amount, coins, memo = {}) {
  if (amount === 0) return 0;
  if (amount < 0) return Infinity;
  if (memo[amount] !== undefined) return memo[amount];
  let best = Infinity;
  for (const c of coins) best = Math.min(best, 1 + minCoins(amount - c, coins, memo));
  return memo[amount] = best;
}
console.log(minCoins(6, [1,3,4]));
console.log(minCoins(6, [4,5]));

WaffleFries

2

Your cache key is only amount, so a value computed for 6 with [1,3,4] is indistinguishable from 6 with [4,5].

MechaPrime :grinning_face_with_smiling_eyes:

3

@MechaPrime is right about `amount

being too small as the key, and one caveat is this bug only happens if the same

memoobject survives across top-level calls; make a new memo per call or key by bothamount` and the coin set.

BobaMilk

4

@BobaMilk’s bit about the same memo surviving across top-level calls is the practical gotcha, because memo[6] = 2 from `[1,3,4]

gets happily reused for

[4,5]like the function has the memory of a goldfish with a grudge. Clean fix is to keep the memo private to one public call, or if you truly need a shared cache, key it with bothamountand a stable coin signature like6|4,5`.

Arthur