Рекурсия

Вспомните матрёшку. Вы открываете большую куклу, а внутри такая же, только меньше. Открываете её — внутри ещё меньше. Так продолжается, пока не дойдёте до самой маленькой: она цельная и не открывается.

Некоторые задачи устроены так же: большую задачу можно свести к такой же, но поменьше. Факториал числа n — произведение всех целых чисел от 1 до n. Например, факториал 4 равен 1 * 2 * 3 * 4, то есть 24.

Его определяют двумя правилами:

• факториал 0 равен 1;
• факториал n равен n, умноженному на факториал n - 1.

Функция на Python повторяет это определение дословно, вызывая саму себя:

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


print(factorial(4))  # 24
print(factorial(0))  # 1

Давайте посмотрим, как она считает factorial(4), глазами матрёшки:

1. factorial(4) не знает ответа сразу и открывает куклу поменьше — вызывает factorial(3).
2. factorial(3) так же вызывает factorial(2), тот — factorial(1), а тот — factorial(0).
3. factorial(0) — самая маленькая кукла: она сразу возвращает 1.
4. Дальше куклы закрываются в обратном порядке, и каждый вызов досчитывает своё умножение.

Две ветки рекурсивной функции

Рекурсия — это вызов функцией самой себя. В рекурсивной функции всегда две ветки. Разберём каждую.

Базовый случай

Ветку, в которой функция возвращает результат без рекурсии, называют базовым случаем. В factorial это if n == 0: return 1. Это самая маленькая матрёшка: она не открывается.

Без базового случая вызовы не закончились бы. Он должен быть достижим: каждый шаг рекурсии обязан приближать аргумент к нему.

Рекурсивный шаг

Строка return n * factorial(n - 1) вызывает ту же функцию с аргументом на единицу меньше. Вызов factorial(4) ждёт результата factorial(3), тот ждёт factorial(2), и так до factorial(0).

Затем результаты идут обратно по цепочке: 1, 1, 2, 6 и, наконец, 24.

Стек вызовов

У каждого вызова свой параметр n, как у любой локальной переменной. Поэтому вызовы друг другу не мешают. Пока вызов ждёт, Python хранит его переменные и место, куда вернуть результат, в отдельной записи — кадре.

Незавершённые кадры складываются в стек вызовов. Он похож на стопку тарелок:

• новый вызов кладёт тарелку сверху;
• завершённый вызов снимает верхнюю тарелку.

Самая нижняя тарелка — <module>: так Python называет код, написанный в файле вне функций. Нажмите «Следующий шаг» и следите, как стопка растёт до factorial(0), а потом разбирается сверху вниз. Виджет считает factorial(3), чтобы стопка поместилась на экране.

Каждая рамка в виджете — это кадр. Обратите внимание на две вещи. У каждого кадра своя n, и значения не смешиваются. А результаты возвращаются в обратном порядке: первым заканчивается вызов, который начался последним.

Здесь аналогия с матрёшкой перестаёт работать. Настоящих кукол понадобилось бы пять, а функция в программе одна. Для каждого вызова отдельно хранятся только его данные.

Как собирается результат

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

def digits_up(n):
    if n == 0:
        return ""
    return digits_up(n - 1) + str(n)


print(digits_up(3))  # 123

Разберём, как собирается строка:

1. digits_up(0) возвращает пустую строку, и цифра 0 в результат не попадает.
2. digits_up(1) даёт "" + "1".
3. digits_up(2) даёт "1" + "2".
4. digits_up(3) даёт "12" + "3", то есть "123".

Если поставить str(n) перед вызовом, цифры пойдут в обратном порядке: "321".

Глубина рекурсии

Пока вызов не закончился, его кадр лежит на стеке. Поэтому число вложенных вызовов ограничено: примерно после 1000 программа останавливается с ошибкой RecursionError.

Некоторые языки превращают в цикл рекурсивный вызов, стоящий последним действием функции, и стек не растёт. Такую замену называют оптимизацией хвостовых вызовов. Этот вопрос часто задают на собеседовании: «Есть ли она в Python?» Ответ:

• нет, Python её не делает;
• каждый вложенный вызов, даже в строке return, занимает свой кадр;
• когда вложенных вызовов может быть больше тысячи, вместо рекурсии пишут цикл.

Тот же факториал циклом:

def factorial_loop(n):
    result = 1
    for i in range(2, n + 1):
        result = result * i
    return result


print(factorial_loop(4))  # 24

Цикл не вызывает новых функций: переменные result и i меняются в одном кадре. Сколько бы ни было шагов, стопка тарелок не растёт.

Частая ошибка

Рекурсивную функцию вызвали с аргументом, из которого базовый случай недостижим:

print(factorial(-1))  # ✗

RecursionError: maximum recursion depth exceeded

От -1 цепочка идёт к -2, -3 и дальше, и условие n == 0 не выполняется никогда. Кадры копятся, пока не упрутся в предел. Проверяйте, что базовый случай достижим из каждого допустимого аргумента. Недопустимые аргументы отсекайте до рекурсии: например, при n < 0 сразу возвращайте None.

Главное

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