Вычислить n! рекурсией, помня про переполнение
Реализуйте Factorial(n), возвращающую n! для n >= 0, причём Factorial(0) == 1. Требования: используйте рекурсию. Тип результата — long, так как значение растёт быстро — 20! уже близко к пределу long, поэтому упомяните, что арифметика checked или более широкий тип защищает от тихого переполнения.
public static long Factorial(int n)
{
// ваш код здесь
return 0;
}Допишите реализацию.
Рекурсия: базовый случай n <= 1 возвращает 1 (покрывает 0 и 1), иначе n * Factorial(n - 1). Приведите к long, чтобы произведение расширялось рано. Поскольку 21! переполняет long, оберните умножение в checked, чтобы бросить исключение, а не тихо переполниться. O(n) вызовов.
- ✗Возвращать
0в базовом случае вместо1, обнуляя всё произведение - ✗Считать в
int, так что произведение переполняется задолго до пределаlong - ✗Полагать, что
longне переполняется —21!уже переполняет, тихо безchecked
- →При каком
nFactorialпереполняетlongи какBigIntegerэто меняет? - →Как переписать это итеративно, чтобы избежать глубокой рекурсии?
Задача
Вернуть n! рекурсивно для n >= 0, причём 0! = 1.
public static long Factorial(int n)
{
if (n <= 1) return 1; // базовый случай: 0! = 1! = 1
return checked(n * Factorial(n - 1)); // checked ловит переполнение
}Как это работает
Рекурсия опирается на определение: n! = n * (n-1)!, а 0! = 1!= 1. Базовый случай n <= 1 возвращает 1 — он останавливает рекурсию и корректно покрывает оба «дна» (0 и 1).
Тип результата — long, потому что факториал растёт очень быстро: 20! ≈ 2.4·10¹⁸ уже близко к пределу long, а 21! его переполняет. Обёртка checked превращает тихое переполнение в OverflowException, чтобы ошибка не прошла незамеченной. Для произвольно больших n нужен System.Numerics.BigInteger.
Глубина рекурсии и число умножений линейны, поэтому сложность — O(n).
