Рекурсия — это цикл

Рекурсия — это цикл

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

Но «функция вызывает саму себя» описывает только то, как записан код. Оно не объясняет, что код делает. А делает он очень знакомую вещь.

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

Ниже мы пройдём этот путь по шагам. Сначала на массиве, где рекурсия не нужна и это хорошо видно. Потом на данных с развилками, где список дел действительно пригодится. И в конце покажем трюк, который рекурсия даёт сверх обычного цикла.

Шаг 1. Сумма массива тремя способами

Возьмём самую скучную задачу: сложить числа в массиве. Будем специально писать с индексами, чтобы во всех трёх версиях двигалась одна и та же переменная i.

Цикл for

def array_sum(nums: list[int]) -> int:
    total = 0
    for i in range(len(nums)):
        total += nums[i]
    return total

Переменная i идёт от 0 до len(nums) - 1, и на каждом шаге мы знаем, куда идти дальше: на i + 1.

Цикл while со списком дел

Теперь перепишем то же самое странным способом. Заведём список дел todo, в котором лежат индексы, которые ещё предстоит обработать. Достали индекс, прибавили число, положили следующий индекс.

def array_sum(nums: list[int]) -> int:
    total = 0
    todo = [0]               # с какого индекса начинать

    while todo:
        i = todo.pop()
        if i == len(nums):   # дошли до конца — для этого индекса работы нет
            continue
        total += nums[i]
        todo.append(i + 1)   # следующий индекс — в список дел

    return total

Здесь append() добавляет дело в конец списка, а pop() достаёт последнее. Пока выбирать не из чего: в todo никогда не лежит больше одного элемента. Мы достали i, положили i + 1. Вместо целого списка хватило бы одной переменной, поэтому здесь он выглядит избыточно: обычный for справляется без него.

Рекурсия

А теперь рекурсия. Напишем её так, чтобы она была максимально похожа на цикл: ничего не возвращает, ничего не передаёт между вызовами, кроме индекса i, и прибавляет числа во внешнюю переменную total. Чтобы вложенная функция могла менять total, нужно слово nonlocal.

def array_sum(nums: list[int]) -> int:
    total = 0

    def todo(i: int) -> None:
        nonlocal total
        if i == len(nums):   # дошли до конца — для этого индекса работы нет
            return
        total += nums[i]
        todo(i + 1)          # вместо append — вызов для следующего индекса
        return               # вложенный вызов закончился — завершаем этот

    todo(0)                  # запускаем «цикл» с индекса 0
    return total

Пустой return завершает текущий вызов, не передавая вычисленный результат наверх: сумма копится в total. В конце функции его можно не писать, Python завершит вызов и без него, но здесь оставим явно, чтобы видеть момент возвращения на предыдущий уровень.

Имя todo осталось тем же, но теперь это функция, а не список. В первой версии мы записывали дело «обработать индекс i», а здесь сразу поручаем функции обработать этот индекс. Сравни основные действия строчка в строчку:

Куда делся список дел? Строка todo.append(i + 1) превратилась в todo(i + 1): вместо того чтобы положить индекс в свой список, мы просим Python выполнить работу для этого индекса. При этом Python запоминает текущий вызов, чтобы после вложенного продолжить с того же места. Каждый незавершённый todo остаётся со своим i.

Если смотрел «Начало» (Inception), вот образ, который дальше будет помогать. Вызов функции — это уснуть и провалиться на уровень сна глубже. todo(0) засыпает и видит сон todo(1), тот засыпает и видит todo(2), и так далее. Пока нижний уровень не закончился, все верхние стоят на паузе и ждут, как фургон, который падает с моста половину фильма. А return — это проснуться: ты возвращаешься на уровень выше ровно в то место, где уснул, и продолжаешь оттуда.

То есть рекурсия ничего не добавила к задаче: мы убрали явный while и список дел, а продолжение работы теперь обеспечивают вызовы. На массиве это чистая избыточность.

Одна оговорка, которую нужно принять

Если запустить обе версии в визуализаторе вроде Python Tutor, картинки будут разные. В нашем todo всегда один элемент: достали i, положили i + 1. А незавершённые вызовы Python копятся до самого конца: вызов todo(0) не может закончиться, пока не закончится todo(1), а тот ждёт todo(2), и так далее. Картинка из Python Tutor — это стопка уровней сна, и все они открыты одновременно. Поэтому рекурсивная сумма массива тратит O(n) памяти там, где цикл for обходится O(1).

То есть под капотом происходит не совсем то же самое. Но результат тот же, порядок обработки тот же, и код совпадает строчка в строчку. Для того, чтобы понять рекурсию и научиться решать на ней задачи, этого достаточно. Предлагаю на этом месте просто поверить: «добавить дело через append можно заменить вызовом для этого дела», и ехать дальше. Это округление, и оно безопасное для наших примеров: ответы сходятся, а версия с явным списком на массиве даже экономнее, потому что не хранит незавершённые вызовы, которым нечего доделывать. Кому интересно, как написать цикл, который повторяет картинку из Python Tutor буквально, посмотрит приложение в конце статьи.

Небольшое замечание про LeetCode: там решение пишется внутри класса, и вместо nonlocal можно использовать self.total. Это тот же внешний накопитель, только хранится он в объекте.

Зачем тогда рекурсия вообще нужна?

Шаг 2. Где цикл for ломается

Цикл for — это транспорт по прямой дороге. У массива дорога прямая: за i всегда идёт i + 1, развилок нет. Поэтому отдельный список дел в нём не нужен и переменной i достаточно.

Нелинейные структуры данных — это не «какие-то более сложные данные». Это дорога с развилками. Пришёл в точку, а дальше ведут две дороги или пять. По одной ты сейчас поедешь, а остальные надо где-то запомнить, чтобы вернуться. Вот зачем нужен список дел.

массив: дорога без развилок

3 ── 4 ── 5 ── конец

вложенный список: дорога с развилками

      список
     /  |   \
    1  ...  ...

Рекурсия — это цикл-вездеход. Она умеет то же, что for, плюс одно: проходить развилки и возвращаться к отложенным. И ровно то же самое умеет while со списком дел: можно записать знакомое движение по-другому.

Самый простой пример дороги с развилками — вложенный список.

Шаг 3. Вложенный список: цикл с развилками

Задача: сложить все числа в списке, внутри которого могут быть другие списки, а в них ещё списки, и так на любую глубину.

numbers = [1, [2, 3], [4, [5]]]   # сумма 15

Почему нельзя написать заранее

Попробуем честно, циклами:

total = 0
for item in numbers:
    if isinstance(item, list):
        for inner in item:
            if isinstance(inner, list):
                for deeper in inner:
                    ...   # а если там ещё список?

Сколько уровней for писать? Неизвестно: глубина вложенности станет понятна только когда мы в неё залезем. Заранее предусмотреть маршрут нельзя. Нужен список дел, в который мы складываем то, что встретили, и разбираемся по мере продвижения.

while со списком дел

В todo лежат элементы, которые ещё предстоит разобрать. Достали элемент, посмотрели, что это. Число — прибавляем. Список — добавляем его содержимое в список дел и идём дальше.

def nested_sum(numbers: list) -> int:
    total = 0
    todo = [numbers]

    while todo:
        item = todo.pop()
        if isinstance(item, list):
            for new_item in item:    # развилка: все ветки — в список дел
                todo.append(new_item)
        else:
            total += item            # число — считаем

    return total

Какое дело берём следующим? Последнее добавленное: pop() достаёт элемент с конца списка. Представь гору тарелок: берёшь верхнюю, а не вытаскиваешь ту, которая под ней. Наш список дел работает так же: новые дела кладём сверху, следующее берём оттуда же.

Вот трассировка для [1, [2, 3], [4, [5]]]. В записи списка верх стопки справа, поэтому содержимое списков разбирается справа налево; для суммы это не важно.

Теперь в todo действительно лежит по несколько элементов: это отложенные ветки, к которым мы вернёмся. Здесь список дел впервые делает настоящую работу.

Рекурсия

Переписываем тем же приёмом, что и массив: внешний накопитель total, вложенная функция без возвращаемого результата, а todo.append(new_item) превращается в todo(new_item). Название снова оставим тем же: в функцию передаём элемент, с которым нужно разобраться.

def nested_sum(numbers: list) -> int:
    total = 0

    def todo(item) -> None:
        nonlocal total
        if isinstance(item, list):
            for new_item in item:    # та же развилка
                todo(new_item)       # вместо append — вызов
        else:
            total += item            # число — считаем
        return                       # всё для этого элемента сделали

    todo(numbers)
    return total

Положи две версии рядом: обработка элемента в функции todo и в теле while совпадает дословно, кроме одной строки. Вместо append теперь вызов, а в конце функции явно написан return. Исчезли while и отдельный список дел, потому что продолжение работы теперь обеспечивают вызовы Python. А for остался: рекурсия заменила не цикл по элементам, а внешний цикл «пока есть работа» вместе со списком дел.

А где отдельное условие выхода из рекурсии, как if i == len(nums) в массиве? Здесь оно не нужно: всё определяется тем, что лежит в item. Если это число, мы прибавляем его к total, новых вызовов не делаем и доходим до return. Если это пустой список, цикл for не выполнится ни разу, и мы тоже сразу дойдём до return. Если список непустой, сначала обработаем его элементы, а когда for закончится, завершим текущий вызов.

То есть выход есть, просто он не записан отдельной проверкой в начале. Ветка заканчивается там, где больше нечего передавать в новые вызовы. В версии с явным списком дел происходит то же самое: число ничего не добавляет в todo, а пустой список ничего не добавляет через for.

Вот как выглядят вызовы для того же примера. Каждый вызов для списка порождает вызовы для своих элементов, а вызовы для чисел меняют total:

                    todo([1, [2, 3], [4, [5]]])
                  /            |               \
          todo(1)         todo([2, 3])         todo([4, [5]])
        total = 1        /          \          /           \
                   todo(2)      todo(3)    todo(4)      todo([5])
                  total = 3    total = 6  total = 10        |
                                                         todo(5)
                                                        total = 15

Это дерево. Мы его не вводили как понятие и не писали для него класс, оно само проявилось из вложенности данных. Вложенный список и есть дерево: каждый список — узел, его элементы — дети, числа — листья.

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

          список
        /   |    \
       1  список  список
          /  \    /   \
         2    3  4   список
                       |
                       5

Сравни две картинки: дерево вызовов повторяет дерево данных один в один. Рекурсия просто прошла по структуре, которая там и так была.

Теперь можно назвать это стеком

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

Его правило называется LIFO: Last In, First Out, «последним пришёл, первым вышел». Это та самая стопка тарелок: новую кладём сверху, следующую берём сверху. Не любой список дел устроен так, но наш todo работал именно по этому правилу.

В Python мы реализовали стек обычным списком. append(x) кладёт элемент на вершину, а pop() снимает верхний элемент; в записи списка вершина находится справа.

todo = [1, 2, 3]       ← 3 сейчас наверху
todo.append(4)
todo = [1, 2, 3, 4]    ← новой верхней стала 4
todo.pop()             → забрали 4
todo = [1, 2, 3]       ← снова наверху 3

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

У Python тоже есть стек, но в нём лежат не будущие дела, а незавершённые вызовы. Последним вызвали функцию, первой она должна завершиться, прежде чем выполнение продолжится в вызвавшей её функции. Это стек вызовов: стопка уровней сна из нашей аналогии с «Началом». Отдельную запись об одном вызове называют кадром, или фреймом; подробнее разберём это ниже.

Шаг 4. Бинарное дерево: та же развилка, два пути

Раз вложенный список оказался деревом, перейдём к дереву настоящему. У узла есть значение и два ребёнка, левый и правый. Пустое место обозначено None.

class Node:
    def __init__(self, val: int, left: "Node | None" = None, right: "Node | None" = None):
        self.val = val
        self.left = left
        self.right = right

while со стеком

Достали узел, прибавили значение, положили детей в список дел. Для None работы нет.

def tree_sum(root: Node | None) -> int:
    total = 0
    stack = [root]

    while stack:
        node = stack.pop()
        if node is None:         # пустое место — пропускаем
            continue
        total += node.val
        stack.append(node.left)  # две ветки развилки
        stack.append(node.right)

    return total

Рекурсия

Теперь и внутренней функции дадим привычное имя dfs: так часто называют обход в глубину, Depth-First Search. Раньше она называлась todo, потому что мы объясняли её через список дел; механизм от переименования не изменился. Можно встретить и имя helper: оно просто означает вспомогательную функцию, а не другой способ обхода.

def tree_sum(root: Node | None) -> int:
    total = 0

    def dfs(node: Node | None) -> None:
        nonlocal total
        if node is None:         # пустое место — выходим
            return
        total += node.val
        dfs(node.left)           # вместо append — вызов
        dfs(node.right)
        return                   # оба вложенных вызова закончились

    dfs(root)
    return total

Соответствие с вложенным списком:

Переход тот же: stack.append(node.left) стало dfs(node.left). Проверка на таком дереве:

        1
       / \
      2   3
     / \
    4   5

root = Node(1, Node(2, Node(4), Node(5)), Node(3))
print(tree_sum(root))  # 15

То, что мы сейчас написали, и есть обход дерева в глубину, DFS, в его шаблонном виде. Любая задача «пройти по дереву и что-то сделать с каждым узлом» решается этой же заготовкой: меняется только строка total += node.val. Хочешь найти максимум — сравнивай с текущим максимумом. Хочешь посчитать листья — проверяй, что у узла нет детей. Хочешь собрать значения в список — добавляй в список. Каркас обхода не меняется, и у него две записи, рекурсивная и со стеком, которые совпадают строчка в строчку.

Одна деталь про порядок. В версии со стеком мы кладём node.left, потом node.right, а pop() достаёт последний, поэтому правый ребёнок обрабатывается раньше левого. Рекурсия обходит левого первым. Для суммы разницы нет, но если порядок важен, в стек кладут детей в обратном порядке: сначала node.right, потом node.left. Тогда и порядок обработки совпадёт с рекурсивным.

Шаг 5. Граф: развилки, которые ведут назад

В дереве дороги только расходятся. В графе они могут сходиться обратно и даже вести в точку, где мы уже были. Если ничего не менять, цикл будет ходить по кругу вечно. Поэтому появляется одна новая деталь: множество visited, где мы отмечаем, где уже были.

Граф запишем как словарь: вершина и список её соседей. Задача: посчитать, до скольких вершин можно добраться из стартовой.

graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["D"],
    "D": ["A"],   # дорога назад
    "E": [],      # недостижима из A
}

    ┌─────────┐
    ▼         │
    A ──▶ B   │
    │     │   │
    ▼     ▼   │
    C ──▶ D ──┘        E

Из A в D ведут две дороги, через B и через C, а из D дорога возвращается в A. В дереве такого не бывает.

while со стеком

def count_reachable(graph: dict[str, list[str]], start: str) -> int:
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()
        if node in visited:            # уже были — пропускаем
            continue
        visited.add(node)
        for neighbor in graph[node]:   # развилка
            stack.append(neighbor)

    return len(visited)

Рекурсия

def count_reachable(graph: dict[str, list[str]], start: str) -> int:
    visited = set()

    def dfs(node: str) -> None:
        if node in visited:            # уже были — выходим
            return
        visited.add(node)
        for neighbor in graph[node]:
            dfs(neighbor)              # вместо append — вызов
        return                         # всех соседей обработали

    dfs(start)
    return len(visited)

Здесь внешний накопитель — само множество visited, и nonlocal не нужен: мы не присваиваем переменную заново, а меняем множество через add.

Форма не изменилась: проверка, обработка, развилка. Добавилось только «уже были». Очень многие задачи, которые на первый взгляд не про графы, устроены именно так: есть состояние, из него можно перейти в несколько других, и нужно обойти все достижимые. Лабиринт, острова на карте, раскраска области, слова, которые получаются из других слов заменой буквы. Везде один и тот же цикл с развилками.

Шаг 6. Фибоначчи: развилка без данных

Числа Фибоначчи обычно показывают как первый пример рекурсии, и это сбивает: где тут вложенность? Входное число n плоское, никаких списков и узлов.

Развилка здесь не в данных, а в формуле: F(n) = F(n - 1) + F(n - 2). Чтобы посчитать F(n), нужно сходить по двум дорогам. Это та же структура, что и в дереве, только дерево строится по ходу вычисления, а не лежит в памяти заранее.

while со стеком

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

def fibonacci(n: int) -> int:
    result = 0
    stack = [n]

    while stack:
        k = stack.pop()
        if k == 0:
            continue                # F(0) = 0, вклада нет
        if k == 1:
            result += 1             # F(1) = 1
            continue
        stack.append(k - 1)         # развилка из формулы
        stack.append(k - 2)

    return result

Рекурсия

def fibonacci(n: int) -> int:
    result = 0

    def helper(k: int) -> None:
        nonlocal result
        if k == 0:
            return                  # F(0) = 0, вклада нет
        if k == 1:
            result += 1             # F(1) = 1
            return
        helper(k - 1)               # вместо append — вызов
        helper(k - 2)
        return                      # обе ветки обработали

    helper(n)
    return result

Снова один и тот же переход: stack.append(k - 1) стало helper(k - 1). Здесь мы назвали вспомогательную функцию helper, но по сути это тоже DFS: мы обходим дерево вычислений в глубину, проходя одну ветку до конца перед переходом к следующей.

Вот дерево вызовов для fibonacci(5). Ответ — число листьев F(1), их пять:

                        F(5)
                 /               \
             F(4)                 F(3)
           /      \             /      \
        F(3)      F(2)       F(2)      F(1)
       /    \     /  \       /  \
    F(2)  F(1) F(1) F(0)  F(1) F(0)
    /  \
 F(1) F(0)

Версия со стеком делает заметным то, что обычная рекурсивная запись прячет: F(3) в этом дереве встречается два раза, F(2) три раза, и так далее. Дерево вызовов растёт как 2^n, а почти вся работа в нём повторяется. Отсюда вырастает мемоизация и динамическое программирование, но это отдельный разговор. Для нас важно другое: Фибоначчи — не особая «математическая» рекурсия, а всё тот же цикл с развилками.

Шаг 7. Трюк: рекурсия умеет возвращать

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

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

Посмотрим, как это меняет наши функции. Начнём с массива.

def array_sum(nums: list[int], i: int = 0) -> int:
    if i == len(nums):
        return 0                            # сумма пустого хвоста
    return nums[i] + array_sum(nums, i + 1) # моё число плюс сумма остального

Ни total, ни nonlocal, ни вложенной функции. Вызов для индекса i отвечает на вопрос «чему равна сумма от i до конца?» и для этого спрашивает следующего: «а от i + 1?». Вложенный список:

def nested_sum(item) -> int:
    if not isinstance(item, list):
        return item                         # число — оно и есть своя сумма
    total = 0
    for new_item in item:
        total += nested_sum(new_item)       # сумма каждой ветки
    return total

Дерево:

def tree_sum(node: Node | None) -> int:
    if node is None:
        return 0
    return node.val + tree_sum(node.left) + tree_sum(node.right)

И Фибоначчи в том виде, в каком его обычно пишут:

def fibonacci(n: int) -> int:
    if n < 2:
        return n                            # F(0) = 0, F(1) = 1
    return fibonacci(n - 1) + fibonacci(n - 2)

Что изменилось по сути. В версии с накопителем вызов для [4, [5]] ничего не знал о своём результате: он просто добавлял числа в общий total. В версии с return этот же вызов возвращает девятку: сумму своего поддерева. Информация стала локальной. Каждый вызов отвечает за свой кусок структуры и отдаёт готовый ответ тому, кто его позвал.

В «Начале» в сон спускаются не ради прогулки: оттуда выносят чужой секрет. return со значением — это ровно то, что ты вынес с нижнего уровня. Вызов для [4, [5]] ушёл на уровень глубже, всё там сложил и проснулся с девяткой в руках. В версии с накопителем ты просыпался с пустыми руками, а результат лежал где-то снаружи, в общей переменной.

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

          [1, [2, 3], [4, [5]]] → 15
          /          |           \
       1 → 1    [2, 3] → 5    [4, [5]] → 9
                /       \      /       \
             2 → 2   3 → 3  4 → 4   [5] → 5
                                       |
                                     5 → 5

Вот почему это именно трюк, а не просто другая запись. Когда задача сводится к «ответ для узла складывается из ответов для его детей» (глубина дерева, сумма поддерева, число путей, сбалансированность), рекурсия с return решает её без единой внешней переменной: всё состояние живёт в кадрах вызовов. В простом явном стеке так не получится: там после pop узел уже обработан, и чтобы «вернуться» к нему с результатами детей, пришлось бы держать его в стеке дальше и помнить, что осталось доделать. Рекурсия делает это за нас. Как это выглядит, если всё-таки делать руками, показано в приложении.

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

Что такое стек вызовов

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

Функция одна, а её выполнений в один момент может быть несколько: todo(0) ещё не закончился, а внутри него уже идёт todo(1), а внутри того todo(2). Для каждого такого выполнения Python заводит отдельную запись: кадр (frame). В кадре лежат локальные переменные этого конкретного выполнения (i, item, node, k) и место в коде, где оно сейчас находится. Это не метафора для объяснения, а настоящее понятие языка: в документации Python оно называется execution frame. Кадры лежат стопкой: сверху тот, который выполняется сейчас, под ним тот, кто его вызвал, и так до самого первого. Эта стопка и есть стек вызовов.

В терминах «Начала» кадр — это уровень сна. У каждого уровня своё место действия и свои герои (локальные переменные), и он замирает, пока идёт сон уровнем ниже. Уровней одновременно открыто столько, сколько кадров в стопке.

Когда вызов завершается, его кадр снимается, и выполнение продолжается в кадре под ним с сохранённого места: с dfs(node.right) после возврата из dfs(node.left) или со сложения nums[i] + ... после того, как вернулся результат. Это пробуждение: ты оказываешься на уровне выше ровно в тот момент, на котором уснул.

Теперь видно, чем наш стек отличался от настоящего. В наш стек мы клали будущую работу: индекс или узел, который ещё предстоит обработать. Обработали — забыли. Python хранит незавершённые выполнения: кадр остаётся, пока не закончится всё, что он запустил, даже если самому ему делать уже нечего. Отсюда картинка в Python Tutor с растущей стопкой кадров и отсюда же O(n) памяти у рекурсивной суммы массива.

Из этого следуют три практических момента.

Без выхода волчок не остановится. Условие вроде if node is None: return или if i == len(nums): return — это толчок, который будит. Но выход не обязательно оформлен отдельным if: во вложенном списке число просто не порождает новых вызовов, а пустой список не даёт ни одного прохода for, и функция доходит до завершающего return. Если же новые вызовы создаются бесконечно и до завершения дело не доходит, функция проваливается всё глубже, уровень за уровнем, как волчок из фильма, который крутится и не падает: ты так и не проснулся. Поэтому первое, что проверяют в рекурсивной функции: где перестают создаваться новые вызовы и дойдём ли мы до этого на допустимых входных данных.

Глубина ограничена. Вечно падать Python не даст: по умолчанию он разрешает около тысячи вложенных вызовов, дальше RecursionError. Это принудительное пробуждение, и чаще всего оно означает, что выхода нет или он не достигается. Но бывает и честная глубина. Список из ста тысяч узлов, вытянутый в цепочку, рекурсивным обходом не пройти, хотя выход в функции есть. Версия с while и своим стеком такого ограничения не имеет: её стек лежит в обычной памяти. Именно поэтому в задачах с большими глубинами просят «итеративное решение», и после этой статьи оно у тебя уже есть: заменить вызов на append.

Кадр хранит незаконченную работу. В версии с return сложение node.val + ... выполняется после того, как вернулись оба вызова. Именно кадр помнит, что это сложение ещё предстоит. Это и есть тот самый трюк из шага 7, увиденный со стороны языка: кадр хранит не только где мы, но и что осталось сделать.

Какие задачи теперь открываются

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

Деревья и графы

• Задачи на деревья: сумма значений, максимальная глубина, поиск узла, проверка свойств поддеревьев. Движение уже задано самой структурой: у текущего узла есть дети, по которым мы продолжаем обход.
• Задачи на графы: найти, куда можно добраться, проверить существование пути, найти связные части графа. Вместо детей у вершины соседи, а чтобы не ходить по кругу, мы запоминаем посещённые вершины.
• Графы по координатам: выход из лабиринта, заливка области, поиск островов, в том числе Number of Islands. В условии может вообще не быть слова «граф»: перед нами просто поле. Но клетка — это вершина, а разрешённые переходы в соседние клетки — дороги между вершинами.

Для лабиринта вопрос звучит так: «Я стою в этой клетке. Куда отсюда можно пойти?» Для островов: «Какие клетки суши связаны с этой?» Это тот же обход с развилками, только текущую точку задаёт не объект Node, а пара координат.

Классические задачи на числа

Фибоначчи, факториал, проверка степени тройки тоже укладываются в эту картину. Только структуру переходов здесь задают не ссылки между объектами, а правила вычисления.

• Фибоначчи: из задачи для n выходят две ветки, для n - 1 и n - 2. Ответ текущей задачи складывается из ответов этих веток.
• Факториал: из задачи для n идём к задаче для n - 1, а полученный ответ умножаем на n. Развилок здесь нет: структура выродилась в цепочку.
• Power of Three: для положительного числа, большего единицы, проверяем делимость на три и переходим к числу втрое меньше. Дошли до единицы — это степень тройки; встретили число, не делящееся на три, — нет.

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

Поиск с возвратом

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

Поиск с возвратом, или backtracking, — это обход такого дерева вариантов. Сделали выбор, исследовали ветку, вернулись, отменили выбор и попробовали следующий. Если по дороге стало ясно, что из этой ветки решения не получится, дальше не идём.

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

Динамическое программирование

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

На Фибоначчи это видно буквально: F(5) требует F(4) и F(3), но внутри F(4) снова потребуется F(3). Самая простая оптимизация — сохранить ответ для F(3) и при следующем обращении взять готовый. Это мемоизация: рекурсивное вычисление с запоминанием результатов.

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

• Состояние: на какой вопрос отвечает один вызов или одна ячейка таблицы. Например, «сколько способов добраться до ступеньки i?».
• Переход: из ответов на какие другие вопросы получается текущий. Если разрешены шаги на одну или две ступеньки, в i можно прийти из i - 1 или из i - 2, поэтому количества способов складываются.
• Начальные ответы: какие состояния можно посчитать сразу, не обращаясь к другим.
• Порядок вычисления: как получать ответы так, чтобы нужные предыдущие результаты уже были готовы.

Сначала можно представить дерево рекурсивных вычислений. Но когда замечаем одинаковые состояния в разных ветках, выясняется: перед нами не независимые ветки, а сеть зависимостей, в которой одну задачу достаточно решить один раз.

Дальше есть два пути. Можно оставить рекурсию и запоминать готовые ответы. А можно вычислить те же состояния в нужном порядке обычным циклом: например, для лестницы идти по индексам снизу вверх и брать два уже посчитанных значения.

Вот почему после рекурсии мы неожиданно снова приходим к простому for. Мы не потеряли найденную структуру: мы поняли её зависимости настолько хорошо, что заранее знаем порядок вычисления и больше не нуждаемся в рекурсивном обходе.

Одна основа, разные следующие шаги

Получается понятная последовательность: сначала учимся двигаться по структуре, затем перебирать варианты, затем замечать повторную работу и избавляться от неё. Рекурсивный перебор даёт исходное решение, а понимание состояний и переходов помогает превратить его в динамическое программирование.

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

Как разбирать рекурсивные задачи самостоятельно

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

Покажи решение этой задачи итеративно, через while и явный стек.
Без рекурсии. Объясни, что хранится в стеке, что мы делаем после
pop и какие элементы добавляем для дальнейшей обработки.
Покажи изменение стека на маленьком примере.

Сначала разберись в этой версии и научись писать её самостоятельно. Попробуй пройти так несколько задач на деревья: достали узел, проверили условие, обработали значение, добавили детей. Посмотри, как меняется решение, если вместо суммы нужно что-то найти или посчитать.

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

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

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

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

Вывод

• Рекурсия — это цикл со стеком. Вызов функции из самой себя — способ записать его, переложив стек на язык.
• На линейных данных стек всегда содержит один элемент, поэтому рекурсия там избыточна: for и переменная делают то же самое дешевле.
• Нелинейные структуры — это развилки на пути цикла. Чтобы их проходить, нужно где-то хранить отложенные ветки. Это умеют только while со стеком и рекурсия, и это одна и та же конструкция.
• Переход между ними всегда один: stack.append(x) превращается в вызов для x, а continue на пустом или уже обработанном элементе превращается в return.
• Вложенный список, дерево, граф, Фибоначчи — разные одежды одного и того же цикла с развилками.
• Код простого стека и рекурсии совпадает, но стек вызовов Python устроен немного иначе: он хранит незавершённые вызовы, а не будущую работу. Для понимания рекурсии и решения задач это различие можно спокойно округлить.
• Сверх цикла рекурсия даёт одно: вызов возвращает значение. Поэтому результат можно собирать из ответов веток без внешнего накопителя.
• Если нужен образ: вызов — уснуть на уровень глубже, кадр — уровень сна, return — проснуться там, где уснул, и принести что-то с собой. Нет выхода — волчок крутится вечно.
• Из этой основы вырастают обходы деревьев и графов, задачи на клетчатом поле, поиск с возвратом и динамическое программирование. В последнем мы находим состояния и зависимости между ними, убираем повторные вычисления и иногда снова получаем обычный линейный цикл.

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

Приложение. Цикл, который повторяет стек вызовов буквально

Этот раздел для тех, кто запустил код из шага 1 в Python Tutor, увидел, что картинки стеков не совпадают, и хочет понять, как написать цикл, у которого стек растёт и разряжается точно так же, как у рекурсии. Для решения задач это не нужно. Для понимания того, что именно хранит Python, полезно.

Кадр как изменяемая запись

В простом стеке лежала будущая работа, и после pop() запись исчезала. Чтобы повторить поведение Python, запись должна оставаться в стеке, пока не закончится всё, что она запустила: уровень сна не закрывается, пока не проснулись все, кто спит ниже. Значит, у записи появляется состояние: она уже сделала своё дело или ещё нет. Будем хранить кадр как список из двух элементов, индекса и флага, потому что состояние кадра меняется, а кортеж менять нельзя.

Сумма массива

def array_sum(nums: list[int]) -> int:
    total = 0
    stack = [[0, False]]          # кадр: индекс и флаг «своё число уже прибавили»

    while stack:
        frame = stack[-1]         # смотрим на верхний кадр, но не снимаем
        i, processed = frame

        if i == len(nums):        # конец массива: этому вызову делать нечего
            stack.pop()
            continue

        if processed:             # вложенный вызов закончился: завершаемся сами
            stack.pop()
            continue

        total += nums[i]
        frame[1] = True           # своё дело сделали, дальше только ждём
        stack.append([i + 1, False])

    return total

Вот как меняется стек для [3, 4, 5], вершина справа:

[[0, False]]
[[0, True], [1, False]]                          total = 3
[[0, True], [1, True], [2, False]]               total = 7
[[0, True], [1, True], [2, True], [3, False]]    total = 12

# индекс 3 — конец массива, его кадр снимается сразу
[[0, True], [1, True], [2, True]]

# остальные кадры по очереди оказываются сверху и завершаются
[[0, True], [1, True]]
[[0, True]]
[]

Это ровно кадры todo(0), todo(1), todo(2), todo(3) из Python Tutor: стопка растёт до конца массива, потом разряжается. Флаг True означает «этот вызов ждёт возвращения из todo(i + 1)». После вложенного вызова в нашей функции стоит только пустой return, поэтому, дождавшись, кадр просто уходит. Если бы мы считали сумму через return, как в шаге 7, именно в ветке if processed выполнялось бы сложение nums[i] + результат.

Сравни с простой версией из шага 1: там мы снимали i сразу, потому что знали, что доделывать нечего. Python этого не знает и кадр хранит. Поэтому простая версия тратит O(1) памяти, а эта и рекурсия — O(n).

Вложенный список

Во вложенном списке у кадра не одно продолжение, а несколько: по одному на каждый элемент. Рекурсивная версия перебирает их циклом for new_item in item: todo(new_item), и кадр Python хранит, на каком элементе цикл остановился. Сделаем то же самое: вместо флага будем хранить номер следующего элемента.

def nested_sum(numbers: list) -> int:
    total = 0
    stack = [[numbers, 0]]        # кадр: элемент и позиция следующего элемента списка

    while stack:
        frame = stack[-1]
        item, pos = frame

        if not isinstance(item, list):   # число: прибавили и сразу закончили
            total += item
            stack.pop()
            continue

        if pos == len(item):             # элементов больше нет: вызов закончен
            stack.pop()
            continue

        frame[1] = pos + 1               # запомнили, где остановился for
        stack.append([item[pos], 0])     # и перешли к следующему элементу

    return total


print(nested_sum([1, [2, 3], [4, [5]]]))  # 15

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

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

Почему простой стек всё равно правильный

Посмотри, во что превратился код. В шаге 3 тело while и тело функции todo совпадали дословно. Здесь появились флаги, позиции, stack[-1] вместо pop(), и на рекурсию это уже не похоже. Чем точнее мы имитируем механизм вызовов, тем дальше уходим от того сходства, ради которого всё затевалось.

Поэтому главный инсайт статьи остаётся прежним. Простая версия со стеком:

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

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

🐆