Рекурсия.

"Чтобы понять рекурсию, нужно сначала понять рекурсию!" (расхожая шутка).

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

def factorial(n):
    if n <= 0:
        return 1
    return n * factorial(n - 1)

Эта функция, вычисляет факториал числа n через умножение числа на факториал числа n - 1.

Условие завершения рекурсии.

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

В определениях рекурсивных функций практически всегда присутствует подобное условие. Оно позволяет вычислению пойти по одной из веток: по рекурсивной — в этой ветке произойдёт вызов себя (а то и не один!), и терминальной, которая закончит вычисление и вернёт результат.

Есть даже такое правило: какой-то из аргументов рекурсивной функции должен обязательно "убывать". Убывание может означать уменьшение счётчика, отбрасывание "головы" списка при движении к его хвосту, вызов себя для части исходной структуры при обработке древовидных структур данных. К сожалению, в общем случае понять, что программа не зациклится, можно только методом "пристального взгляда" и применением тестов. Особенно важно проверять срабатывание условия завершения рекурсии!

Переполнение стека.

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

Стек (stack) — структура данных, похожая на стопку монет: монета, положенная последней, будет снята первой (при снятии монет порядок получается обратным порядку складывания).

В этом же стеке сохраняются значения аргументов функции, а иногда и другая служебная информация. При этом память, выделенная для стека при запуске программы, конечна и довольно ограничена. Что же произойдёт, если функция будет вызывать себя снова и снова и не возвращать результат? Эта память когда-нибудь закончится! Когда заканчивается память, выделенная для стека вызовов, случается так называемое "переполнение стека".

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

>>> factorial(1000)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 4, in factorial
  File "<stdin>", line 4, in factorial
  File "<stdin>", line 4, in factorial
  [Previous line repeated 995 more times]
  File "<stdin>", line 2, in factorial
RecursionError: maximum recursion depth exceeded in comparison

Заметьте, сообщение говорит, что "превышена максимальная глубина рекурсии". Глубиной рекурсии называется количество последовательных вызовов "себя" без возврата значения. В Python максимальная длина искусственно ограничена, потому что проще считать количество вызовов, чем предсказывать окончание памяти.

Зачем рекурсия нужна.

Вы можете подумать, почему же программисты не перестают использовать рекурсивные функции и не переходят на итеративные? Дело в том, что некоторые алгоритмы реализуются сильно проще, если использовать именно рекурсию, а не циклы. Часто такие алгоритмы работают с рекурсивными же структурами данных — деревьями, "словарями словарей словарей" и подобными. При реализации таких алгоритмов нужно помнить, что память для стека не бесконечна. Впрочем, обычно не бесконечны и сами обрабатываемые структуры данных, поэтому отказываться полностью от рекурсии не стоит!

Рекурсия прямая, косвенная, линейная, каскадная.

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

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

Рекурсия в этой функции (которая проверяет Гипотезу Коллатца) — линейная:

def collatz(n):
    if n == 1:
        return True
    if not n % 2:
        return collatz(n // 2)
    return collatz(n * 3 + 1)

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

А вот рекурсия в этой функции (которая вычисляет очередное Число Фибоначчи) — каскадная:

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

Здесь функция всегда вызывает себя два раза. Сначала будет два вызова себя, которые превратятся в четыре (два раза по два вызова), затем в восемь — количество вызовов растёт "каскадно", отсюда и название рекурсии.

Заключение.

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

Мы учим программированию с нуля до стажировки и работы. Попробуйте наш бесплатный курс «Введение в программирование» или полные программы обучения по Node, PHP, Python и Java.

Хекслет

Подробнее о том, почему наше обучение работает →