Коротко о проблемах и решениях.
Проблемы при больших $n$:
- Рекурсивное переполнение стека: в CPython по умолчанию глубина рекурсии ограничена ($\text{max\_depth}\approx 1000$), поэтому получите $\text{RecursionError}$ для $n\gtrsim 1000$.
- Время вычисления: число операций растёт линейно по количеству множителей, т.е. $\Theta (n)$ умножений в модельной единице; при учёте длины чисел умножения становятся дороже.
- Память/размер результата: точный факториал быстро растёт — число битов в $n!$ примерно
$${\log }_{2}n!\approx n{\log }_{2}n-n{\log }_{2}e+O(\log n),$$ т.е. хранение результата требует примерно $\Theta (n\log n)$ бит; для очень больших $n$ возможна $\text{MemoryError}$.
Альтернативы (с оценками):
1) Итеративный (рекомендовано для Python)
- Код:
```
def factorial_iter(n):
r = 1
for i in range(2, n+1):
r *= i
return r
```
- Время: $O(n)$ по числу умножений (в модельной модели). С учётом роста длины чисел — умножения становятся дороже, итоговая битовая сложность зависит от алгоритма умножения больших целых.
- Память: $O(1)$ дополнительной памяти (кроме результата).
2) Хвостовая рекурсия
- Пример:
```
def fact_tail(n, acc=1):
return fact_tail(n-1, acc*n) if n>0 else acc
```
- В Python бесполезна: Python не делает оптимизацию хвостовой рекурсии, глубина стека всё равно $O(n)$ и для больших $n$ будет $\text{RecursionError}$.
- В языках с TCO (tail-call optimization): время $O(n)$, стек $O(1)$.
3) Мемоизация / кэширование
- Идея: сохранять уже вычисленные факториалы, полезно при множественных запросах для разных $n$.
- Пример (итеративное накопление):
```
cache = [1]
def factorial_cached(n):
while len(cache) <= n:
cache.append(cache[-1] * len(cache))
return cache[n]
```
- Время: первое вычисление до $n$ — $O(n)$; последующие вызовы для меньших или равных $n$ — $O(1)$.
- Память: $O(n)$ для хранения всех значений $\mathrm{0..}n$.
4) Использовать стандартную реализацию
- Python: используйте $\text{math.factorial(n)}$ — реализовано на C и использует оптимизации (быстрее чистого Python).
- Часто лучший выбор для практических задач.
5) Алгоритмы для очень больших $n$ - Для экстремально больших $n$ используются быстрые методы (binary splitting, prime-swing и др.), дающие время примерно $O(M(N)\log N)$, где $M(N)$ — стоимость умножения чисел длины $N$ бит. Это нужно при вычислении факториалов с миллионами и более факториалов — в обычных задачах не требуется.
Резюме/рекомендации:
- Для большинства задач — заменить рекурсию на итеративный вариант или вызвать $\text{math.factorial}$.
- Если нужны множественные запросы — храните кеш (итеративно) для $O(1)$ доступа после первого расчёта.
- Не полагайтесь на хвостовую рекурсию в Python — она не избавит от переполнения стека.