Рекурсивное вычисление факториала в Python
В этом уроке вы напишете рекурсивную функцию для вычисления факториала и разберётесь, зачем нужен базовый случай.
Введение
Какую задачу это решает
Некоторые задачи естественно описываются через свою меньшую версию: папка содержит папки, генеалогическое дерево содержит меньшие деревья, n! равен n, умноженному на (n - 1)!. Рекурсия позволяет писать код, который прямо следует таким определениям.
Пример из жизни
Рекурсия похожа на очередь людей, которые передают друг другу вопрос. Чтобы узнать 6!, первый человек спрашивает у соседа, сколько будет 5!, и ждёт. Тот спрашивает про 4!, и так далее, пока кого-то не спросят про 1!: на это можно ответить сразу. Потом ответы идут обратно по очереди, и каждый умножает ответ на своё число.
factorial(6)🙋 Первый человек: 6 × ответ, которого он ждётnumber * factorial(number - 1)➡️ Задать соседу тот же вопрос, но с числом поменьшеif number <= 1: return 1🛑 Последний отвечает сразу: 1720⬅️ Ответы возвращаются по очереди назад: 720Рекурсивная функция вызывает себя с меньшим входом, пока не дойдёт до базового случая, на который может ответить сразу; здесь factorial(n) = n × factorial(n - 1) и factorial(1) = 1.
Главное
if number <= 1: return 1- базовый случай; без него вызовы никогда не остановились бы.return number * factorial(number - 1)вызывает ту же функцию с меньшим числом.factorial(6)ждётfactorial(5), который ждётfactorial(4), и так доfactorial(1).raise ValueError(...)отклоняет отрицательные числа, которые иначе никогда не дошли бы до базового случая.
Когда это нужно?
- Задачи, определённые через меньшие версии: деревья, папки, вложенные данные.
- Алгоритмы «разделяй и властвуй», такие как сортировка слиянием.
- Понимание того, как работает стек вызовов.
Когда это не нужно
- Простое повторение, как факториал в настоящем коде: цикл или
math.factorialбыстрее и не ограничены глубиной. - Очень глубокие входные данные: Python останавливается примерно на 1000 вложенных вызовах с RecursionError.
Как это работает
Нажимайте Шаг, чтобы следить за каждым вызовом. Новые вызовы попадают в стек вызовов, и каждый возвращает значение тому, кто его вызвал.
Пример кода
def factorial(number):
if number < 0:
raise ValueError("Factorial is undefined for negative numbers")
if number <= 1:
return 1
return number * factorial(number - 1)
print(factorial(6))
Результат выполнения
720
Разбор кода
Когда number равно 0 или 1, функция сразу возвращает 1. Это базовый случай, который не даёт рекурсии продолжаться бесконечно. Для остальных значений функция возвращает number, умноженное на factorial(number - 1). Каждый рекурсивный вызов добавляется в стек вызовов (call stack), поэтому глубина рекурсии O(n).
Измените значения и запустите программу в онлайн-компиляторе Python CodeUtility без локальной установки Python.
Упражнения для практики
Попробуйте изменить код по подсказкам ниже. Если менять код и смотреть на результат, урок запомнится гораздо лучше, чем при простом чтении.
- Проверьте работу на пустом списке, списке из одного элемента и списке с повторами.
- Выводите состояние после каждого шага, чтобы увидеть алгоритм в действии.
- Измерьте время работы на 100, 1 000 и 10 000 элементах и сравните с другим решением.
Частые ошибки
Забытый базовый случай
Функция вызывает себя бесконечно, пока Python не выбросит RecursionError.
def factorial(number):
return number * factorial(number - 1)
def factorial(number):
if number <= 1:
return 1
return number * factorial(number - 1)
Закончили этот урок?
Отметьте его как изученный, чтобы следить за прогрессом.
Попрактикуйтесь на задаче
Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.
- Факториал Перемножьте все положительные целые числа до n. Легко
- Recursive Power Compute a power recursively by halving the exponent. Средне