How can I convert this large factorial function to a higher-order function?

Question

The following code uses a cache object outside of the factorial function. The factorial function itself is large which has too many concerns of finding factorial and caching.

How can I convert this code to a higher-order function and generate the same result when I call

console.log(factorial(5));
console.log(factorial(7));

cache = { }

function factorial(n) {
  
  if (n === 0) {
    return 1;
  }
  
  if (cache[n])
  {
    return cache[n];
  }
  
  console.log("Stack Up: " + n);
  
  var value = n * factorial(n - 1);
  
  console.log("Stack Down: " + value);
  
  cache[n] = value;
  
  return value;
}

console.log(factorial(5));
console.log(factorial(7));

Answer 1

There's already other answers out there for memoising recursive functions, but I'll adapt that answer to factorial in javascript so you can see how it works more easily

The secret to writing memoised recursive functions is continuation passing style. A similar technique works when you want to make a non-tail recursive function stack-safe.

I'll leave some console.log statements in this first example so you can see when it's actually computing and when it's just doing a memo lookup.

const memoise = f => {
  const memo = new Map()
  const compute = (x, k) =>
    (console.log('compute', x),
    memo.get(x, memo.set(x, f(x,k))))
  const lookup = x =>
    (console.log('lookup', x),
    memo.has(x) ? memo.get(x) : compute(x, lookup))
  return lookup
}

const factk = (x, k) => {
  if (x === 0)
    return 1
  else
    return x * k(x - 1)
}

const memfact = memoise(factk)

console.log(memfact(5)) // 120
console.log(memfact(7)) // 5040

---

Here I've removed the console.log calls inside of memoise and instead demonstrate a memoised fibonacci function vs an unmemoised one. Compare the dramatic time difference between memoise(fibk) and badfib

const memoise = f => {
  const memo = new Map()
  const compute = (x, k) =>
    memo.get(x, memo.set(x, f(x,k)))
  const lookup = x =>
    memo.has(x) ? memo.get(x) : compute(x, lookup)
  return lookup
}

const fibk = (x, k) => {
  if (x < 2)
    return x
  else
    return k(x - 1) + k(x - 2)
}

const badfib = x => {
  if (x < 2)
    return x
  else
    return badfib(x - 1) + badfib(x - 2)
}

console.time('memoised')
console.log(memoise (fibk) (35)) // 9227465 1.46ms
console.timeEnd('memoised')

console.time('unmemoised')
console.log(badfib(35))          // 9227465 135.85ms
console.timeEnd('unmemoised')