Рекурсия в Python

Рекурсия — это процесс определения чего-либо через само себя.

Пример из реального мира — поставить два параллельных зеркала друг напротив друга. Любой объект между ними будет рекурсивно отражаться.

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

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

Следующее изображение показывает работу рекурсивной функции recurse.

Ниже приведён пример рекурсивной функции для нахождения факториала целого числа.

Факториал числа — это произведение всех целых чисел от 1 до этого числа. Например, факториал 6 (обозначается как 6!) равен 1*2*3*4*5*6 = 720.

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

def factorial(x):
    """Это рекурсивная функция
    для нахождения факториала целого числа"""

    if x == 1:
        return 1
    else:
        return (x * factorial(x-1))

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

Вывод

The factorial of 3 is 6

В приведённом примере factorial() — это рекурсивная функция, так как она вызывает саму себя.

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

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

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

Посмотрим на изображение, показывающее пошаговый процесс:

Наша рекурсия заканчивается, когда число уменьшается до 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

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

Рекурсивные функции делают код понятным и элегантным.
Сложную задачу можно разбить на более простые подзадачи с помощью рекурсии.
Генерация последовательностей с рекурсией проще, чем с использованием вложенных итераций.

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

Иногда логику рекурсии трудно проследить.
Рекурсивные вызовы затратны (неэффективны), так как занимают много памяти и времени.
Рекурсивные функции трудно отлаживать.