Вычислите факториал числа

Решение

Факториал n! = 1 × 2 × 3 × ... × n, где 0! = 1 по определению. Разберу несколько подходов.

Подход 1: Рекурсивный (классический)

function factorialRecursive(n: number): number {
  // Граничные случаи
  if (n < 0) throw new Error("Factorial undefined for negative numbers");
  if (n === 0 || n === 1) return 1;
  
  // Рекурсивный случай: n! = n × (n-1)!
  return n * factorialRecursive(n - 1);
}

// Примеры:
console.log(factorialRecursive(5));  // 120
console.log(factorialRecursive(0));  // 1
console.log(factorialRecursive(10)); // 3628800

Как работает:

factorialRecursive(5)
= 5 * factorialRecursive(4)
= 5 * (4 * factorialRecursive(3))
= 5 * (4 * (3 * factorialRecursive(2)))
= 5 * (4 * (3 * (2 * factorialRecursive(1))))
= 5 * (4 * (3 * (2 * 1)))
= 5 * (4 * (3 * 2))
= 5 * (4 * 6)
= 5 * 24
= 120

Анализ:

• Временная сложность: O(n)
• Пространственная сложность: O(n) для стека вызовов
• Легко понять и писать
• Проблема: стек переполнится при больших n

Подход 2: Итеративный (рекомендуемый)

function factorialIterative(n: number): number {
  if (n < 0) throw new Error("Factorial undefined for negative numbers");
  
  let result = 1;
  
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  
  return result;
}

// Примеры:
console.log(factorialIterative(5));  // 120
console.log(factorialIterative(0));  // 1
console.log(factorialIterative(10)); // 3628800

Как работает:

factorialIterative(5):
result = 1
i = 2: result = 1 * 2 = 2
i = 3: result = 2 * 3 = 6
i = 4: result = 6 * 4 = 24
i = 5: result = 24 * 5 = 120
Возвращаем 120

Анализ:

• Временная сложность: O(n)
• Пространственная сложность: O(1) — только переменные
• Не использует стек вызовов
• Очень эффективна для больших чисел

Подход 3: Мемоизация (кэширование)

const cache = new Map<number, number>();

function factorialMemo(n: number): number {
  if (n < 0) throw new Error("Factorial undefined for negative numbers");
  if (n === 0 || n === 1) return 1;
  
  // Проверяем кэш
  if (cache.has(n)) {
    return cache.get(n)!;
  }
  
  // Вычисляем и кэшируем
  const result = n * factorialMemo(n - 1);
  cache.set(n, result);
  
  return result;
}

Использование: если вызываем функцию много раз с одинаковыми аргументами

Подход 4: С использованием reduce

function factorialReduce(n: number): number {
  if (n < 0) throw new Error("Factorial undefined for negative numbers");
  
  return Array.from({ length: n }, (_, i) => i + 1)
    .reduce((acc, num) => acc * num, 1);
}

Анализ: функциональный стиль, создаёт массив (неэффективно)

Подход 5: Хвостовая рекурсия (с аккумулятором)

function factorialTail(n: number, acc: number = 1): number {
  if (n < 0) throw new Error("Factorial undefined for negative numbers");
  if (n === 0 || n === 1) return acc;
  
  // Хвостовой вызов: результат вычисляется сразу
  return factorialTail(n - 1, acc * n);
}

// Использование:
console.log(factorialTail(5));  // 120

Особенность: некоторые языки оптимизируют хвостовую рекурсию (не создают стек). JavaScript это не гарантирует, но V8 может оптимизировать в некоторых случаях.

Подход 6: С проверкой переполнения и BigInt

function factorialBigInt(n: number): bigint {
  if (n < 0) throw new Error("Factorial undefined for negative numbers");
  if (!Number.isInteger(n)) throw new Error("n must be integer");
  
  let result = 1n;
  
  for (let i = 2n; i <= BigInt(n); i++) {
    result *= i;
  }
  
  return result;
}

// Примеры:
console.log(factorialBigInt(20));  // 2432902008176640000n
console.log(factorialBigInt(100)); // огромное число, не переполнится

Использование: когда результат может быть очень большим (> Number.MAX_SAFE_INTEGER = 9×10^15)

Проблема: Переполнение при больших n

// ❌ Проблема: число теряет точность
console.log(factorialIterative(21));
// 51090942171709440000 (неточный результат)
// Правильный: 51090942171709440000n

// ✓ Решение: используй BigInt
console.log(factorialBigInt(21));
// 51090942171709440000n (точный)

// ✓ Или ограничь n
if (n > 20) throw new Error("n too large");

Тестирование

const testCases = [
  [0, 1],
  [1, 1],
  [2, 2],
  [3, 6],
  [4, 24],
  [5, 120],
  [6, 720],
  [10, 3628800],
];

testCases.forEach(([n, expected]) => {
  const result = factorialIterative(n as number);
  console.log(`factorial(${n}) = ${result}, expected ${expected} ${result === expected ? '✓' : '✗'}`);
});

Сравнение подходов

Что происходит при больших n?

// Рекурсия: максимум ~15000 (зависит от памяти)
try {
  factorialRecursive(50000);
} catch (e) {
  console.log("RangeError: Maximum call stack size exceeded");
}

// Итерация: работает с любым n, но результат теряет точность > 20
console.log(factorialIterative(21));  // неточный

// BigInt: работает с любым n
console.log(factorialBigInt(1000)); // работает, но долго

Рекомендация для интервью

Начните с итеративного подхода — он показывает:

• Эффективность O(1) памяти
• Понимание оптимизации
• Практичность

Потом упомяните:

• Рекурсия: понятнее математически, но проблема стека
• BigInt: для больших результатов
• Мемоизация: если функция вызывается много раз

Ключевые моменты:

• 0! = 1 по определению
• Итерация лучше чем рекурсия для факториала
• Максимальное точное число: 20! (Number.MAX_SAFE_INTEGER)
• Для больших n используй BigInt