Алгоритмы на Python

Рекурсивное вычисление факториала в Python

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

  • Средний
  • Чтение: 2 мин
  • Примеров для запуска: 1

Введение

Какую задачу это решает

Некоторые задачи естественно описываются через свою меньшую версию: папка содержит папки, генеалогическое дерево содержит меньшие деревья, n! равен n, умноженному на (n - 1)!. Рекурсия позволяет писать код, который прямо следует таким определениям.

Пример из жизни

Рекурсия похожа на очередь людей, которые передают друг другу вопрос. Чтобы узнать 6!, первый человек спрашивает у соседа, сколько будет 5!, и ждёт. Тот спрашивает про 4!, и так далее, пока кого-то не спросят про 1!: на это можно ответить сразу. Потом ответы идут обратно по очереди, и каждый умножает ответ на своё число.

От очереди людей к коду
factorial(6)🙋 Первый человек: 6 × ответ, которого он ждёт
number * factorial(number - 1)➡️ Задать соседу тот же вопрос, но с числом поменьше
if number <= 1: return 1🛑 Последний отвечает сразу: 1
720⬅️ Ответы возвращаются по очереди назад: 720
Каждый вызов ждёт меньший вызов, пока базовый случай не даст ответ.
Одним предложением

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

Главное

  1. if number <= 1: return 1 - базовый случай; без него вызовы никогда не остановились бы.
  2. return number * factorial(number - 1) вызывает ту же функцию с меньшим числом.
  3. factorial(6) ждёт factorial(5), который ждёт factorial(4), и так до factorial(1).
  4. raise ValueError(...) отклоняет отрицательные числа, которые иначе никогда не дошли бы до базового случая.

Когда это нужно?

  • Задачи, определённые через меньшие версии: деревья, папки, вложенные данные.
  • Алгоритмы «разделяй и властвуй», такие как сортировка слиянием.
  • Понимание того, как работает стек вызовов.

Когда это не нужно

  • Простое повторение, как факториал в настоящем коде: цикл или math.factorial быстрее и не ограничены глубиной.
  • Очень глубокие входные данные: Python останавливается примерно на 1000 вложенных вызовах с RecursionError.

Как это работает

Нажимайте Шаг, чтобы следить за каждым вызовом. Новые вызовы попадают в стек вызовов, и каждый возвращает значение тому, кто его вызвал.

Пример кода

Запустить код →
main.py
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.

Упражнения для практики

Попробуйте изменить код по подсказкам ниже. Если менять код и смотреть на результат, урок запомнится гораздо лучше, чем при простом чтении.

  1. Проверьте работу на пустом списке, списке из одного элемента и списке с повторами.
  2. Выводите состояние после каждого шага, чтобы увидеть алгоритм в действии.
  3. Измерьте время работы на 100, 1 000 и 10 000 элементах и сравните с другим решением.
Запустить в компиляторе Python →

Частые ошибки

Забытый базовый случай

Функция вызывает себя бесконечно, пока Python не выбросит RecursionError.

Ошибка
def factorial(number):
    return number * factorial(number - 1)
Исправление
def factorial(number):
    if number <= 1:
        return 1
    return number * factorial(number - 1)

Закончили этот урок?

Отметьте его как изученный, чтобы следить за прогрессом.

Попрактикуйтесь на задаче

Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.

Все задачи