Why does this memoized recursive function return stale results after I change the input array?

programming web dev
1

I memoized a recursive sum over an array, but after mutating the array and calling it again, I still get the old answer. I expected the cache to reflect the new values. What is the bug here, and what’s a safe way to memoize this kind of function?

function makeSolver(nums) {
  const memo = new Map();
  function solve(i) {
    if (i >= nums.length) return 0;
    if (memo.has(i)) return memo.get(i);
    const ans = nums[i] + solve(i + 1);
    memo.set(i, ans);
    return ans;
  }
  return solve;
}

Yoshiii

2

The bug is that your cache key is only i, but the result also depends on the current contents of nums, so mutating the array makes the old entries invalid.

Sora