Javascript factorial function memoization

I’m trying to use the factorial function with memoization. I have taken the max value from the object to reduce the number of recursive calls made. But the problem is the first call is I don’t know whether this is optimized or not since the first call is pretty expensive. Any insights on this will be great.

let cache = {0: 1};
function factMemoize(key) {
    if (!cache[key]) {
        let maxVal = Object.keys(cache).reduce(function (a, b) {
            return Math.max(a, b);
        });
        console.log(maxVal);
        while (key >= maxVal) {
            cache[key] = key * factMemoize(key - 1);
            maxVal++;
        }
    }
    return cache[key];
}

Answer

You don’t buy much from memoizing this since you only use each value once. After you’ve called the function you do have the cache for a second call, but we often think of memoizing as something that happens in a cache that only exists during the function. For something like that, calculating Fibonacci numbers is a classic example where memoizing is a huge improvement over the naive recursive function.

Having said that, in your function it’s not clear why you are using an object for your cache and then searching it. You can just use an array where the indexes will be the number you’re looking for calculate. You don’t need to search it, just start with the number and recursively call the next lower one. If there’s a cache it, it will return. For example:

let cache = [1];
function factMemoize(key) {
    if (!cache[key]) {
      cache[key] = key * factMemoize(key - 1)
    } else { // just to demo cache:
        console.log("cache hit:", key)
    }
    return cache[key]
}

// only hits cache at the end 
console.log("6! = ", factMemoize(6))

// second call benefits from cache:
console.log("8! = ", factMemoize(8))