Факториал через рекурсию — объяснение и примеры

Человек печатает на ноутбуке за столом

Что такое факториал числа

Факториал положительного целого n — это произведение всех положительных целых чис, не превышающих n. Обозначение: n!. Примеры:

5! = 5 × 4 × 3 × 2 × 1 = 120
1! = 1
0! = 1 (определение, удобное для комбинаторики и рекурсии)

Краткое определение: факториал n — количество перестановок из n различных предметов.

В одной строке: факториал показывает, сколько способов можно упорядочить n объектов.

Почему используют рекурсию для факториала

Рекурсия естественно отражает математическое определение факториала: n! = n × (n-1)!. Рекурсивная реализация компактна и наглядна. Однако у неё есть ограничения: глубина рекурсии и потребление стека. Для больших n лучше использовать итерацию или специальную библиотеку для больших целых.

Важно: рекурсия — это метод, при котором функция вызывает саму себя. В рекурсивных алгоритмах всегда нужен базовый случай, чтобы завершить вычисление.

Основные шаги при проектировании рекурсивной функции

Найти базовый случай — условие остановки. Для факториала это n == 0 (или n == 1).
Найти отношение между задачей и подзадачами — как получить n! из (n-1)!.
Обобщить отношение для произвольного n.

Эти три шага работают для множества задач: суммирование первых n чисел, вычисление НОД, генерация последовательности Фибоначчи (с оптимизацией), обходы деревьев и др.

Псевдокод факториала с рекурсией

function Fact(n)  
    If n == 0 then               // base case  
        Return 1  
    Return n * Call Fact(n - 1)  // generalized relation

Рекурсивная реализация: C

C — процедурный язык с явным управлением стеком и типами. Ниже — минимальный пример, который выводит факториал числа 5.

Подключаем заголовочный файл ввода-вывода:

#include

Определяем функцию fact:

int fact(int n) {
    if (n == 0)
        return 1;
    return n * fact(n - 1);
}

main с примером вызова:

int main() {  
    int num = 5;
    printf("Factorial of %d is %d", num, fact(num));  
    return 0;  
}

Примечание: для больших n результат выйдет за пределы диапазона int; используйте long long или библиотеки для больших чисел.

Рекурсивная реализация: Java

Java — объектно-ориентированный язык с строгой типизацией. Пример рекурсивной функции в классе Main:

class Main {
    static int fact(int n) {
        if (n == 0)
            return 1;
        return n * fact(n - 1);
    }
    public static void main(String[] args) {
        int num = 5;
        System.out.println("Factorial of " + num + " is " + fact(num));
    }
}

Совет: при больших n используйте BigInteger для безопасного результата.

Рекурсивная реализация: Python

Python удобен для коротких примеров и учебных задач.

def fact(n):
    if n == 0:
        return 1
    return n * fact(n-1)

num = 5;  
print("Factorial of", num, "is", fact(num))

Python автоматически растягивает целые числа, но глубина рекурсии по умолчанию ограничена (sys.getrecursionlimit()). Для больших n используйте итерацию или увеличьте лимит осторожно.

Итеративная альтернатива

Рекурсия красива, но итерация лучше по памяти и предсказуема по производительности. Пример на Python:

def fact_iter(n):
    result = 1
    for i in range(2, n+1):
        result *= i
    return result

Итеративный подход избегает глубокого стека и часто выполняется быстрее за счёт отсутствия накладных расходов на вызовы функций.

Хвостатая рекурсия и оптимизация

Хвостатая рекурсия (tail recursion) — когда рекурсивный вызов является последней операцией в функции. В некоторых компиляторах/интерпретаторах хвостатая рекурсия оптимизируется в цикл, экономя стек. Пример хвостатой версии на Python (логика, но в CPython хвостатая оптимизация отсутствует):

def fact_tail(n, acc=1):
    if n == 0:
        return acc
    return fact_tail(n-1, acc * n)

Важно: не все среды выполняют оптимизацию хвостатой рекурсии (например, CPython — не выполняет). Java и C обычно не обеспечивают автоматическое преобразование хвостатой рекурсии в цикл, хотя некоторые компиляторы и оптимизаторы в специфичных режимах могут применить оптимизации.

Когда рекурсия не подходит

Очень большие n: риски переполнения стека и ограничений времени/памяти.
Требуется предсказуемая производительность и минимальная память — предпочтительна итерация.
В средах без оптимизации хвостатой рекурсии рекурсивные вызовы приводят к дополнительным накладным расходам.

Контрпример: для вычисления факториала числа 100000 рекурсия, скорее всего, приведёт к переполнению стека; итерация или специальная библиотека для факториалов — правильный выбор.

Сложность и использование ресурсов

Временная сложность: O(n) — функция выполняет n шагов (рекурсивных или итеративных умножений).
Пространственная сложность рекурсивной версии: O(n) по стеку вызовов. Итеративная версия требует O(1) дополнительной памяти (помимо результата).

Выбор между рекурсией и итерацией часто сводится к компромиссу простоты реализации и требований к ресурсам.

Тесты и критерии приёмки

Критерии приёмки:

Корректность для n = 0, 1, 2, 5, 10.
Корректное поведение при негативных входных данных — определите контракт (ошибка/исключение).
Обработка больших n: если формат результата не поддерживает большие числа, тест должен фиксировать переполнение.
Производительность: для n порядка 10^5 рекурсивная версия должна провалиться или быть явно помечена как непригодная.

Примеры тест-кейсов:

input: 0 -> output: 1
input: 1 -> output: 1
input: 5 -> output: 120
input: -3 -> ожидается ValueError/ошибка аргумента
input: 20 -> output: 2432902008176640000 (проверьте тип результата)

Чеклист для ревью кода (роль: разработчик/тестировщик/ревьюер)

Разработчик:
- Проверил базовые случаи (0 и 1).
- Документировал допустимый диапазон входных данных.
- Добавил обработку ошибок для отрицательных n.
- Написал итеративную альтернативу, если нужны большие n.
Тестировщик:
- Написал юнит-тесты для граничных и типичных случаев.
- Проверил поведение при переполнении типов.
- Замерил потребление памяти для рекурсивной версии.
Ревьюер:
- Проверил ясность кода и комментариев.
- Убедился в соответствии контракта функции и обработки ошибок.
- Оценил необходимость хвостатой рекурсии или итерации.

Мини-методология: как выбрать реализацию

Если n <= 10^4 и код читается ради обучения — рекурсия допустима.
Если n может быть большим или код будет выполняться в продакшне — используйте итерацию или библиотеки для работы с большими целыми.
Если среда поддерживает оптимизацию хвостатой рекурсии, рассмотрите хвостатый вариант.

Факты и числа (фактбокс)

Временная сложность обеих стандартных реализаций (рекурсивной и итеративной): O(n).
Пространственная сложность: рекурсия O(n) по стеку, итерация O(1).
Для n > 20 результат не поместится в 64-битный signed integer.

Риски и способы их снижения

Риск переполнения стека при рекурсии: снизить, используя итерацию.
Риск переполнения целочисленного типа: использовать большие типы (long long, BigInteger) или библиотеки для больших чисел.
Риск неверной обработки отрицательных входных значений: явно проверять аргументы и бросать исключение или возвращать ошибку.

Миграция и совместимость

При переносе кода между языками убедитесь, что поведение при переполнении и ограничения глубины стека учтены.
В языках со статической типизацией (C, Java) используйте типы с нужной вместимостью.
В интерпретируемых средах (Python) учитывайте ограничение глубины рекурсии.

Диаграмма принятия решения (Mermaid)

flowchart TD
  A[Нужно считать факториал?] --> B{Будут ли большие n?}
  B -- Да --> C[Использовать итерацию или библиотеку больших чисел]
  B -- Нет --> D{Нужна ли лаконичность кода?}
  D -- Да --> E[Рекурсивная реализация]
  D -- Нет --> C
  E --> F[Проверить глубину рекурсии и типы]
  C --> F

Примеры альтернатив и расширений

Вычисление факториала по модулю m (часто в задачах на комбинаторику и криптографию).
Табличный подход (dynamic programming) для часто пересчитываемых факториалов — кэширование результатов для повторяющихся запросов.
Использование факториала в формулах сочетаний C(n, k) и пермутаций.

Короткий глоссарий

Базовый случай: условие, при котором рекурсивные вызовы прекращаются.
Хвостовая рекурсия: рекурсивный вызов как последняя операция функции.
Переполнение стека: ошибка из-за слишком большого числа вложенных вызовов.

Заключение

Рекурсивная реализация факториала — отличный учебный пример для понимания рекурсии и базовых принципов программирования. Для учебных задач и небольших входных значений рекурсия удобна и читаема. Для продакшна и больших n предпочитайте итеративные подходы или проверенные математические/числовые библиотеки. Всегда документируйте допустимый диапазон входных данных и покрывайте код тестами на граничные случаи.

Важно

Всегда проверяйте входные данные (отрицательные числа, нулевой случай).
Для больших n используйте итерацию или библиотеки работы с большими целыми.

Краткое резюме в двух предложениях: факториал — фундаментальная математическая функция, которую удобно реализовать рекурсивно, опираясь на базовый случай 0! = 1 и соотношение n! = n × (n−1)!. В продакшн-коде учитывайте ограничения стека и диапазона типов, выбирая итерацию или специальные библиотеки при необходимости.