Рекурсия

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

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

Для примера, попробуем вычислить произведение всех элементов списка рекурсивно:

1
2
3
4
def multiply_all(array):
    if not array:
        return 1
    return array[0] * multiply_all(array[1:])

И примеры использования:

>>> print(multiply_all([10]))
10
>>> print(multiply_all([1, 2, 3, 4]))
24
>>> print(multiply_all([0, 2, 3]))
0

Что делает данный код?

  1. Определение функции. Если вдруг кто не знает, что это такое, читаем курс Основы Python с нуля, статью про функции в Python
  2. Если массив пустой
  3. Возвращаем 1 (произведение 0 элементов считаем равным единице)
  4. Иначе возвращаем результат выражения

Разберём это выражение подробнее. array[0] * multiply_all(array[1:]) — это произведение первого элемента массива (array[0]) на multiply_all(array[1:]). multiply_all(array[1:]), в свою очередь, результат той же самой функции multiply_all, но применённый к массиву без первого элемента.

Другими словами, из функции мы рекурсивно вызываем её же саму (но с другим аргументом). То есть, функция multiply_all - рекурсивная.

Условие остановки

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

Если убрать условие остановки, то рекурсивные вызовы будут выполняться бесконечно.

def example(array):
    return example(array)

print(example([10]))

Traceback (most recent call last):
  File "", line 6, in <module>
    print(multiply_all([10]))
          ^^^^^^^^^^^^^^^^^^
  File "", line 3, in multiply_all
    return multiply_all(array)
           ^^^^^^^^^^^^^^^^^^^
  File "", line 3, in multiply_all
    return multiply_all(array)
           ^^^^^^^^^^^^^^^^^^^
  File "", line 3, in multiply_all
    return multiply_all(array)
           ^^^^^^^^^^^^^^^^^^^
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

На самом деле, как мы видим, Python не позволяет бесконечно вызывать рекурсивную функцию. В Python есть счётчик глубины, при превышении которого происходит исключение. В разных реализациях Python это значение разное, в Python 3.12 это, например, 1000.

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

Узнать и изменить это значение можно с помощью sys.getrecursionlimit и sys.setrecursionlimit.

>>> import sys
>>> print(sys.getrecursionlimit())
1000
>>> sys.setrecursionlimit(2000)
>>> print(sys.getrecursionlimit())
2000

На самом деле, проще и производительнее будет НЕ использовать рекурсию, и написать multiply_all через цикл:

def multiply_all(array):
    result = 1
    for element in array:
        result *= element
    return result

Для чего полезна рекурсия

Для рекурсивных определений. Рекурсивное определение — определение какого-либо объекта внутри самого этого объект, то есть ситуация, когда объект является частью самого себя. Рассмотрим хрестоматийный пример.

Числа Фибоначчи — это последовательность чисел, которые задаются по определённому правилу. Оно звучит так: каждое следующее число равно сумме двух предыдущих. Первые два числа заданы сразу и равны 0 и 1.

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

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(10))  # 55

Производительность рекурсии

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

Даже в примере с числами Фибоначчи можно заметить, что код уже для fibonacci(40) выполняется крайне долго.

Это связано не только с фактом наличия рекурсии, а с тем, что мы выполняем рекурсивный вызов дважды каждый раз. Из-за этого количество вызовов растёт экспоненциально.

На самом деле, вычисления чисел Фибоначчи также можно переписать через цикл:

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    fibonacci1 = 0
    fibonacci2 = 1

    for i in range(2, n+1):
        fibonacci1, fibonacci2 = fibonacci2, fibonacci1 + fibonacci2
    return fibonacci2

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

Сложная рекурсия

Возможна чуть более сложная схема: функция A вызывает функцию B, а та в свою очередь вызывает A. Это называется сложной рекурсией.

Сложно привести разумный пример; просто знайте, что такое тоже существует.

Если кто-то не до конца понял рекурсию, есть отличная статья про неё.