Pitfalls while memoization

As practicing dynamic programming, I was implementing a function that returns the binomial coefficient nCr given n and r.

Naive formula:

function binomial_naive(n, r) {
  if (n < 0 || r < 0 || r > n) {
    return 0;
  }
  if (r === 0 || r === n) {
    return 1;
  }
  return binomial_naive(n-1, r-1) + binomial_naive(n-1, r);
}

We can memoize this function to get O(r(n-r)) running time.

I was using Map<number, Map<number, number>>s but encountered a problem.

My initial memoization implementation had cache updating code and cache retrieval code interleaved, which made subtle bugs that only occurs only when some cache is computed.

I threw it away and coded a more straightforward implementation:

const cache = new Map();

function binomial(n, r) {
  if (!cache.has(n)) {
    cache.set(n, new Map());
  }
  if (!cache.get(n).has(r)) {
    cache.get(n).set(r, binomial_naive(n, r));
  }
  return cache.get(n).get(r);
}

function binomial_naive(n, r) {
  if (n < 0 || r < 0 || r > n) {
    return 0;
  }
  if (r === 0 || r === n) {
    return 1;
  }
  return binomial(n - 1, r) + binomial(n - 1, r - 1);
}

Now I see that we could implement this using 2d arrays which makes it a little more straightforward.