Рекурсия в Python: как функции вызывают сами себя

Освоение рекурсии в Python

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

Что такое рекурсия?

Рекурсия — это техника определения проблемы в терминах более мелкого экземпляра той же проблемы.

Классическая иллюстрация включает два параллельных зеркала, обращенных друг к другу; каждое изображение является рекурсивным отражением другого.

---

Рекурсивная функция в Python

В Python функция может вызывать другие функции, и она может даже вызывать саму себя. Такие конструкции называются рекурсивными функциями.

На изображении ниже показан стек вызовов для простой рекурсивной функции с именем recurse:

Ниже приведен классический пример: рекурсивная реализация функции факториала, возвращающей произведение всех положительных целых чисел до x.

Пример рекурсивной функции

def factorial(x):
    """Рекурсивно вычисляет факториал положительного целого числа."""
    if x == 1:
        return 1
    return x * factorial(x - 1)

num = 3
print("The factorial of", num, "is", factorial(num))

Вывод

The factorial of 3 is 6

Здесь factorial() — рекурсивная функция, потому что она вызывает саму себя до достижения базового случая x == 1.

При вызове с положительным целым числом функция многократно вызывает себя с уменьшающимся значением:

factorial(3)  # 1-й вызов с 3
3 * factorial(2)  # 2-й вызов с 2
3 * 2 * factorial(1)  # 3-й вызов с 1
3 * 2 * 1  # возврат из 3-го вызова
3 * 2  # возврат из 2-го вызова
6  # возврат из 1-го вызова

Ниже приведено визуальное представление этого пошагового процесса:

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

Python устанавливает максимальную глубину рекурсии (по умолчанию 1000) для предотвращения аварийного завершения интерпретатора из-за бесконечной рекурсии. Превышение этого лимита вызывает RecursionError:

def recursor():
    recursor()

recursor()

Вывод

Traceback (most recent call last):
  File "<string>", line 3, in <module>
  File "<string>", line 2, in a
  File "<string>", line 2, in a
  File "<string>", line 2, in a
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

Вы можете программно настроить лимит рекурсии с помощью sys.setrecursionlimit(), но делайте это с осторожностью, чтобы избежать переполнения стека.

---

Преимущества рекурсии

1. Рекурсивные решения часто более лаконичны и легче для чтения, особенно для проблем, естественно выражаемых в рекурсивных терминах.
2. Они позволяют элегантно разлагать сложные задачи на более простые подзадачи.
3. Генерация последовательностей (например, Фибоначчи, перестановки) с рекурсией проще, чем с вложенными циклами.

---

Недостатки рекурсии

1. Рекурсивная логика может быть труднее для понимания и рассуждения новичкам.
2. Каждый рекурсивный вызов потребляет память стека; глубокие рекурсии могут быть затратными по памяти и медленнее итеративных альтернатив.
3. Отладка рекурсии может быть сложной из-за многослойного стека вызовов.

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