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));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)) // 5040Here 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')Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments