Коротко — три подхода, точность и удобство.
1) Формула включений‑исключений (точно)
$!n=n!{\sum }_{k=0}^n\frac{(-1{)}^k}{k!}$.
Плюсы: даёт точное значение и очевидное доказательство. Минусы: при вычислениях в плавающей точке сильная вычитательная потеря точности из‑за чередующихся больших членов; надо либо работать с целыми (через факториалы) либо с высокой точностью. Вычислительная сложность — $O(n)$ операций.
2) Рекуррентное соотношение (практично для точных значений)
$!0=1,!1=0,!n=(n-1)(!(n-1)+!(n-2))$.
Плюсы: простой, стабильный, требует $O(n)$ целочисленных умножений/сложений, мало памяти (хранить последние два значения). Лучший выбор для получения точного $!n$ для больших $n$ с использованием больших целых (bigint). Минусы: значением растёт как $n!$, поэтому требуется память/время для работы со многозначными целыми при очень больших $n$.
3) Приближение (очень удобно для оценок)
Основное приближение
$!n\sim \frac{n!}{e}$,
и более точно
$!n=\lfloor \frac{n!}{e}+\frac{1}{2}\rfloor$ (для $n\ge 1$).
Абсолютная погрешность оценена так:
$|!n-\frac{n!}{e}|\le \frac{1}{n+1}$,
поэтому для умеренно больших $n$ абсолютная ошибка крайне мала; относительная ошибка ещё меньше (поскольку $n!/e$ огромно). Для грубой оценки можно также использовать формулу Стирлинга для $n!$.
Рекомендация
- Если нужен точный результат для большого $n$: использовать рекурренту и big integers.
- Если нужна быстрая оценка или порядок величины: взять $\frac{n!}{e}$ (или Стирлинг для логарифма), и при необходимости округлить по формуле выше (даёт точное значение для большинства $n$).
- Формула включений полезна теоретически и для вывода оценок, но для численных вычислений уступает рекурренте по устойчивости.