Учебник по информатике и математике
Темы
C++
Основы языка
Рекурсия: как функция вызывает сама себя
Оглавление:
Ты стоишь в длинной очереди в столовой и хочешь узнать, какой ты по счету. Начала очереди не видно, поэтому ты спрашиваешь соседа впереди. Он тоже не знает и спрашивает своего соседа. Так вопрос доходит до первого человека: он стоит у кассы и точно знает, что он первый. Дальше ответ идет обратно — каждый прибавляет единицу к номеру соседа, пока цепочка не дойдет до тебя.
Каждый в очереди узнает свой номер через такой же вопрос соседу. Это и есть рекурсия: функция вызывает сама себя для задачи попроще.
Базовый случай и шаг рекурсии
У правильной рекурсивной функции две части:
- базовый случай — ситуация, в которой ответ известен сразу и новый вызов не нужен (первый в очереди знает свой номер);
- шаг рекурсии — функция сводит задачу к такой же, но поменьше, и вызывает себя (спросить соседа и прибавить единицу).
Простейший пример — обратный отсчет:
def countdown(n):
if n == 0: # базовый случай
print("Старт!")
return
print(n)
countdown(n - 1) # шаг рекурсии: задача на единицу меньше
countdown(3)
# 3
# 2
# 1
# Старт!
Ключевая идея: Каждый шаг рекурсии должен приближать задачу к базовому случаю. Если базового случая нет или до него невозможно дойти, функция будет вызывать себя снова и снова.
Функция, которая возвращает результат
Рекурсия особенно удобна, когда ответ для большой задачи легко собрать из ответа для маленькой. Посчитаем сумму цифр числа. Сумма цифр 472 — это последняя цифра 2 плюс сумма цифр числа 47. А у однозначного числа сумма цифр равна ему самому — это базовый случай.
def digit_sum(n):
if n < 10: # базовый случай: одна цифра
return n
return n % 10 + digit_sum(n // 10) # последняя цифра + сумма остальных
print(digit_sum(472)) # 13
print(digit_sum(2026)) # 10
Здесь n % 10 — последняя цифра числа, а n // 10 — число без последней цифры: 472 // 10 равно 47.
Стек вызовов
Что происходит при вызове digit_sum(472)? Сразу вернуть ответ функция не может: ей нужен результат digit_sum(47). Поэтому она замирает и ждет, а Python запускает новый вызов. Тот тоже ждет следующего:
| Вызов | Что делает | Возвращает |
|---|---|---|
digit_sum(472) |
ждет digit_sum(47), потом прибавит 2 |
$2 + 11 = 13$ |
digit_sum(47) |
ждет digit_sum(4), потом прибавит 7 |
$7 + 4 = 11$ |
digit_sum(4) |
базовый случай, отвечает сразу | $4$ |
Таблицу читай сверху вниз — так вызовы «спускаются», а потом снизу вверх — так возвращаются ответы.
Незавершенные вызовы Python хранит в стеке вызовов. Стек устроен как стопка тарелок: новый вызов кладется сверху, а снимается первым тот, что положили последним. Для каждого вызова Python помнит, где тот остановился, и хранит его собственную копию n, поэтому вызовы друг другу не мешают.
Ограничение глубины
Каждый ожидающий вызов занимает память, поэтому Python ограничивает глубину рекурсии — по умолчанию около 1000 вложенных вызовов. Вот что будет, если забыть базовый случай:
import sys
print(sys.getrecursionlimit()) # 1000
def countdown(n):
print(n)
countdown(n - 1) # базового случая нет
countdown(3)
# 3
# 2
# 1
# 0
# ... и так почти тысячу строк, а затем:
# RecursionError: maximum recursion depth exceeded...
Предел можно поднять командой sys.setrecursionlimit(5000), но при очень глубокой рекурсии программа может аварийно завершиться. Для десятков тысяч вложенных вызовов надежнее цикл.
Рекурсия или цикл
Любую рекурсию можно заменить циклом, и часто цикл даже проще. Зачем тогда рекурсия?
Она выручает, когда задача сама устроена «вложенно»: папки внутри папок, разделы книги с подразделами. Посчитаем сумму чисел в списке, внутри которого могут быть другие списки:
def nested_sum(items):
total = 0
for x in items:
if isinstance(x, list): # внутри снова список - та же задача
total += nested_sum(x)
else: # базовый случай: просто число
total += x
return total
print(nested_sum([1, [2, 3], [4, [5, 6]]])) # 21
isinstance(x, list) проверяет, является ли x списком. Сколько уровней вложенности встретится, заранее неизвестно, поэтому простым циклом тут не обойтись. На рекурсии построены и многие быстрые алгоритмы: сортировка слиянием, быстрая сортировка, обход деревьев.
Частые ошибки
Частая ошибка: Забытый
returnперед рекурсивным вызовом. Если вdigit_sumнаписать простоn % 10 + digit_sum(n // 10), функция посчитает сумму и выбросит ее, вернувNone. Уровнем выше Python попробует сложить число сNoneи упадет сTypeError.
- Нет базового случая — функция вызывает себя, пока не упрется в предел глубины, и падает с
RecursionError. - Шаг не приближает к базовому случаю. Вызов
countdown(-1)с проверкойif n == 0до нуля не дойдет: -1, -2, -3 и дальше вниз. Надежнее проверятьif n <= 0.
Проверь себя
Что произойдет, если у рекурсивной функции нет базового случая?
Что вернет вызов digit_sum(9081) для функции из статьи?
Соедини понятие и его смысл.
Базовый случай
Здесь Python хранит вызовы, которые ждут ответа
Шаг рекурсии
Ошибка при превышении глубины рекурсии
Стек вызовов
Вызов функции для задачи поменьше
RecursionError
Ответ известен сразу, без нового вызова