Факториал с мемоизацией

Задача

Вычислите факториал числа. Реализуйте вариант с мемоизацией, чтобы повторные вызовы работали за O(1).

Решение

Оптимальное решение

const factorialMemo = (() => {
    const cache = { 0: 1, 1: 1 };
 
    return function factorial(n) {
        if (cache[n] !== undefined) {
            return cache[n];
        }
        cache[n] = n * factorial(n - 1);
        return cache[n];
    };
})();
 
// Первый вызов: factorialMemo(5) → вычисляет и кеширует 2!, 3!, 4!, 5!
// Второй вызов: factorialMemo(5) → O(1), берет из cache
// Вызов factorialMemo(6) → вычисляет только 6!, использует кеш для 5!

См. также

• fibonacci
• memoize