Рекурсия в Python: функция вызывает себя

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

Обратный отсчёт: база и шаг

def countdown(n):
    if n == 0:
        print('Старт!')
        return
    print(n)
    countdown(n - 1)

countdown(3)

3
2
1
Старт!

У каждой рекурсии две части: базовый случай, который останавливает вызовы, и шаг, приближающий задачу к базе. В примере базой служит условие n == 0: дойдя до нуля, функция печатает «Старт!» и выходит через return — никаких новых вызовов. Шаг — строка countdown(n - 1): каждый следующий вызов получает число на единицу меньше и потому гарантированно когда-нибудь упрётся в базу. Вызовы выстраиваются цепочкой: countdown(3) зовёт countdown(2), тот — countdown(1), тот — countdown(0), где цепочка и обрывается.

Что будет без базы

# Базы нет — остановки тоже нет
def endless(n):
    print(n)
    endless(n - 1)

endless(5)

Факториал: рекурсивное решение

Классика рекурсии — факториал: произведение всех чисел от единицы до n. Определение само рекурсивно: n факториал — это n, умноженное на (n - 1) факториал, а единица факториал равен единице. Формула почти дословно переписывается в код:

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

print(factorial(5))

120

База — n <= 1: факториал единицы и нуля равен единице, дальше дробить нечего. Шаг — return n * factorial(n - 1): ответ для пяти живёт внутри ответа для четырёх. Цепочка раскрутится вниз до базы, а затем ответы начнут подниматься обратно: единица, дважды два, трижды шесть, четыре раза двадцать четыре, пять раз сто двадцать. Обратите внимание: return стоит на каждой ветке — рекурсивная ветка обязана вернуть своё значение наверх, иначе результат не доедет до первого вызова:

# Так не работает: рекурсивная ветка ничего не возвращает
def broken(n):
    if n <= 1:
        return 1
    n * broken(n - 1)

print(broken(3))

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

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

for i in [1, 2, 3, 4, 5, 6]:
    print(i, factorial(i))

1 1
2 2
3 6
4 24
5 120
6 720

Ещё шаг: сумма цифр числа

Рекурсия удобна везде, где задача распадается на маленькую часть и ту же задачу для остатка. Разбирая число на цифры, мы откусываем последнюю цифру — n % 10 — и повторяем то же для оставшегося n // 10:

def digit_sum(n):
    if n < 10:
        return n
    return n % 10 + digit_sum(n // 10)

print(digit_sum(2947))

22

База здесь — однозначное число: её сумма равна ей самой. Дальше цепочка: семь плюс сумма 294, четыре плюс сумма 29, девять плюс сумма 2 — и двойка упирается в базу. В сумме двадцать два. Ни один вызов не знает всей картины — каждый откусывает по цифре и доверяет остальное следующему вызову себя же.

Рекурсия по данным: вложенные списки

Самое родное применение рекурсии — данные, вложенные сами в себя. Список может содержать списки, а те — свои списки, и заранее неизвестно, сколько уровней вложенности принесёт реальная задача. Цикл не знает числа вложений; рекурсия просто повторяет себя для каждого встреченного списка:

def flatten(items):
    out = []
    for item in items:
        if isinstance(item, list):
            out.extend(flatten(item))
        else:
            out.append(item)
    return out

data = [1, [2, [3, 4], 5], 6]
print(flatten(data))

[1, 2, 3, 4, 5, 6]

Функция перебирает элементы циклом, а встретив вложенный список, вызывает себя — и вся глубина разглаживается: список внутри списка внутри списка. Глубина вложенности здесь не число в коде, а свойство данных, и рекурсия следует за данными. Тот же приём работает для содержимого словарей, каталогов файловой системы, разделов документа: где структура повторяет саму себя, там уместен вызов себя.

Рекурсия или цикл

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

acc = 1
for i in [1, 2, 3, 4, 5]:
    acc *= i
print(acc)

120

• разглаживание вложенных списков и словарей — глубина известна только данным, не коду;
• обход каталогов файловой системы: папки содержат папки, и заранее неизвестно, насколько глубоко;
• деревья: разделы документа, комментарии с ответами, структуры вроде DOM;
• математические определения, которые сами рекурсивны: факториал, числа Фибоначчи, сумма цифр.

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

Дерево: структура, созданная для рекурсии

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

def count_comments(node):
    total = 1
    for reply in node['replies']:
        total += count_comments(reply)
    return total

tree = {
    'text': 'корень',
    'replies': [
        {'text': 'ответ 1', 'replies': []},
        {'text': 'ответ 2', 'replies': [
            {'text': 'ответ 2.1', 'replies': []}
        ]}
    ]
}

print(count_comments(tree))

4

Функция считает узел и прибавляет подсчёт каждого потомка. Потомок — это такой же словарь с полями text и replies, поэтому функция вызывает себя без всякой проверки типа: структура гарантирует, что рекурсия закончится на листьях, где replies пуст и цикл не сделает ни шага. Четыре узла — корень и три ответа — четыре и получилось.

Так же считают файлы в каталоге (внутри папки бывают папки), разделы документа, комментарии с ответами, элементы JSON неизвестной вложенности. Общее у всех этих задач одно: структура повторяет саму себя, и код, который это повторение отражает, читается почти так же коротко, как сама структура.

Чек-лист из четырёх пунктов

Четыре строчки чек-листа — и рекурсия перестаёт быть лотереей. Пункт первый ловит вечную цепочку, второй — цепочку, ушедшую не туда, третий — потерянный результат, четвёртый — переполнение глубины.

# Так не запускается: база на единице, а стартуем с нуля
def total(n):
    if n == 1:
        return 1
    return n + total(n - 1)

total(0)

Глубину рекурсии можно поднять командой sys.setrecursionlimit(...), но мы этого не советуем: лимит стоит там не просто так, а глубокая рекурсия съедает память стека, и на реальных данных вместо красивого RecursionError вы получите падение всего процесса. Если задача упирается в глубину — скорее всего, её надо решать циклом.

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