Рекурсия и разделяй-и-властвуй

Рекурсия — самый недооценённый инструмент в арсенале. Её либо боятся («сложно отлаживать, съест стек»), либо применяют механически («задача про дерево — значит, рекурсия»). И то и другое мешает. На самом деле рекурсия — это способ свести задачу к самой себе меньшего размера, а разделяй-и-властвуй — способ сделать это так, чтобы уменьшение было экспоненциально быстрым.

Эта статья про три связанные вещи:

1. Механика. Что физически происходит в памяти при рекурсивном вызове, откуда берётся RecursionError и почему хвостовая рекурсия иногда бесплатна, а иногда нет.
2. Метод. Как проектировать рекурсивные решения так, чтобы они были заведомо корректны (спойлер: через индукцию), и как считать их стоимость.
3. Инженерия. Когда рекурсию надо разворачивать в цикл, как распараллеливать, где она встречается в проде и какие уязвимости с ней связаны.

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

1. Рекурсия — это индукция, записанная как программа

Математическая индукция доказывает утверждение P(n) для всех n, показывая две вещи: базу P(0) и переход P(k) → P(k+1). Рекурсивная функция делает ровно то же самое, но вместо доказательства строит значение:

• база — что вернуть, когда задача тривиальна;
• шаг — как получить ответ для n, имея ответ для меньшего входа.

Ключевой психологический приём — «рекурсивный скачок веры» (recursive leap of faith): при написании шага вы предполагаете, что рекурсивный вызов уже работает правильно, и не пытаетесь мысленно раскручивать его в голове. Разворачивать стек вручную — верный способ запутаться на третьем уровне. Если база верна и шаг верен в предположении корректности вызова на меньшем входе, функция верна для всех входов — это и есть индукция.

def sum_list(xs: list[int]) -> int:
    """Сумма списка. Читается как индуктивное определение."""
    if not xs:                  # база: сумма пустого списка равна 0
        return 0
    return xs[0] + sum_list(xs[1:])   # шаг: первый + (сумма остального — уже верна)

Этот код, конечно, ужасен по производительности (xs[1:] копирует срез, итого Θ(n²) времени и Θ(n²) суммарной аллокации), но структурно он идеален как иллюстрация. Ниже мы это исправим.

Три условия завершения

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

1. База существует и покрывает все тривиальные случаи (не только «пустой список», но и, например, «список из одного элемента», если шаг требует минимум двух).
2. Есть убывающая мера (variant, «фундированная мера») — целочисленная неотрицательная величина, которая строго уменьшается при каждом вызове. Для списка это длина, для дерева — высота, для числа — само число, для графа — количество непосещённых вершин.
3. Каждый рекурсивный вызов реально уменьшает меру. Классический баг: f(n) вызывает f(n) в какой-то ветке (например, забыли - 1), или quicksort с плохим partition рекурсивно вызывается на том же диапазоне.

Формулируйте меру явно, в докстринге. Это дисциплинирует лучше любых тестов:

def gcd(a: int, b: int) -> int:
    """НОД по Евклиду. Мера: b, строго убывает, т.к. a % b < b для b > 0."""
    if b == 0:
        return a
    return gcd(b, a % b)

Что происходит, когда мера не убывает, — видно на печально известном примере из реальной жизни: def factorial(n): return n * factorial(n - 1) без базы. Функция уйдёт в n = -1, -2, ..., мера (значение n) убывает, но никогда не достигает базы, потому что база отсутствует. Формально требование звучит так: мера принимает значения из вполне упорядоченного множества (например, ℕ), поэтому бесконечно убывать не может — она обязана упереться в базу.

Таксономия рекурсивных схем

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

Различие между «разделяй-и-властвуй» и «перекрывающиеся подзадачи» — водораздел. Если подзадачи не пересекаются, честная рекурсия оптимальна. Если пересекаются — нужна мемоизация, и вы уже пишете динамическое программирование, о чём отдельная статья: Динамическое программирование: от мемоизации до оптимизаций.

2. Что происходит в железе: кадры вызова

Абстракция «функция вызывает себя» реализуется через стек вызовов. Каждый вызов создаёт кадр (stack frame / activation record), в котором лежат: аргументы, локальные переменные, адрес возврата и сохранённые регистры. Кадр живёт до тех пор, пока вызов не вернётся.

Отсюда следуют три практических вывода:

• Глубина рекурсии = пиковая дополнительная память. Рекурсия глубины n стоит Θ(n) памяти, даже если сам алгоритм «ничего не аллоцирует». Для merge sort глубина Θ(log n) — копейки. Для наивного обхода связного списка рекурсией глубина Θ(n) — катастрофа на миллионе элементов.
• Вызов не бесплатен по времени. Пролог/эпилог функции, запись адреса возврата, потенциальный промах предсказателя переходов. На маленьких входах рекурсивный merge sort проигрывает сортировке вставками именно поэтому — отсюда приём «cutoff to insertion sort», который мы разбирали в статье Сортировки: от пузырька до Timsort и radix.
• Стек ограничен и обычно мал. Типичный размер стека потока — 1 МБ (Windows, по умолчанию), 8 МБ (Linux main thread, ulimit -s), 512 КБ–1 МБ у пула потоков в JVM. Go — исключение: горутины стартуют с 2–8 КБ и растут копированием до runtime/debug.SetMaxStack (1 ГБ на 64-битных по умолчанию), поэтому в Go глубокая рекурсия ведёт себя гораздо мягче; подробности в обзоре Go.

В CPython добавляется собственный лимит интерпретатора:

import sys

print(sys.getrecursionlimit())   # 1000 по умолчанию
sys.setrecursionlimit(20000)     # ОПАСНО: снимает предохранитель, но не увеличивает С-стек

sys.setrecursionlimit — это не «дать больше памяти», а «отключить сигнализацию». Реальный C-стек не растёт, и вместо аккуратного RecursionError вы получите сегфолт интерпретатора. Правильный способ увеличить глубину — запустить работу в потоке с явным размером стека:

import threading, sys

def run_deep(fn, *args, stack_mb: int = 64, limit: int = 200_000):
    """Запускает fn в потоке с большим стеком — безопаснее, чем один setrecursionlimit."""
    threading.stack_size(stack_mb * 1024 * 1024)
    sys.setrecursionlimit(limit)
    box: list = []
    t = threading.Thread(target=lambda: box.append(fn(*args)))
    t.start()
    t.join()
    return box[0]

Но лучший способ — не углубляться. К этому вернёмся в разделе про разворачивание в цикл.

3. Доказательство корректности рекурсии

Для циклов инструмент — инвариант, для рекурсии — сильная индукция по мере. Схема доказательства всегда одна:

1. База. Показать, что на минимальных входах функция возвращает правильный ответ.
2. Шаг. Предположить (индукционная гипотеза), что для всех входов с мерой меньше текущей функция возвращает правильный ответ. Показать, что тогда комбинирование этих ответов даёт правильный ответ для текущего входа.
3. Завершение. Показать, что мера строго убывает и ограничена снизу.

Обратите внимание: нужна именно сильная индукция («для всех меньших»), а не обычная («для предыдущего»), потому что merge sort вызывает себя на n/2, а не на n−1.

Разберём на подсчёте инверсий — это merge sort с одной добавленной строкой, и заодно отличный пример «алгоритма, который считает что-то попутно».

def sort_and_count(a: list[int]) -> tuple[list[int], int]:
    """Возвращает (отсортированную копию a, число инверсий i<j при a[i]>a[j]).

    Мера: len(a). Убывает, т.к. при len >= 2 обе половины строго короче.
    """
    n = len(a)
    if n <= 1:                       # БАЗА: 0 или 1 элемент — уже отсортирован, инверсий нет
        return a[:], 0

    mid = n // 2
    left,  cl = sort_and_count(a[:mid])   # ГИПОТЕЗА: вернёт верный ответ для левой половины
    right, cr = sort_and_count(a[mid:])   # ГИПОТЕЗА: и для правой

    merged: list[int] = []
    i = j = 0
    cross = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:           # <= сохраняет стабильность и не считает "инверсией" равенство
            merged.append(left[i]); i += 1
        else:
            # left[i] > right[j] => все оставшиеся элементы left тоже больше right[j]
            cross += len(left) - i
            merged.append(right[j]); j += 1
    merged.extend(left[i:]); merged.extend(right[j:])
    return merged, cl + cr + cross

Доказательство шага. Любая инверсия (i, j) попадает ровно в одну из трёх категорий: обе позиции в левой половине (посчитано в cl по гипотезе), обе в правой (cr), или i слева и j справа. Третью категорию считает слияние: когда мы забираем right[j], все ещё не забранные элементы левой половины больше него — а поскольку левая половина отсортирована по гипотезе, их ровно len(left) - i. Категории не пересекаются и покрывают всё, значит, cl + cr + cross — точный ответ. ∎

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

Сложность. T(n) = 2T(n/2) + Θ(n) ⇒ Θ(n log n) по времени. По памяти в этой реализации Θ(n log n) из-за срезов — на практике пишут in-place версию с индексами и одним буфером, получая Θ(n) дополнительной памяти.

4. Разделяй-и-властвуй как шаблон проектирования

Общая схема состоит из трёх шагов, и в 90% случаев вся сложность сосредоточена в третьем:

Проектируя алгоритм, задавайте себе вопросы в этом порядке:

1. Как разрезать? Пополам по индексу (сортировки), пополам по значению (quickselect), по координате (геометрия), по битам (radix), по вершине-разделителю (деревья).
2. Что теряется при разрезе? Ответ, который «лежит на границе»: инверсия между половинами, пара точек по разные стороны разделяющей прямой, подотрезок, пересекающий середину. Это и есть работа шага combine.
3. Можно ли сделать combine дешевле, чем перебор границы? Здесь рождаются нетривиальные алгоритмы: Карацуба вместо четырёх умножений делает три; ближайшая пара точек проверяет не все пары в полосе, а не более 7 соседей.

Считаем стоимость: три случая

T(n) = a·T(n/b) + f(n). Работа распределяется по дереву рекурсии: на уровне k подзадач aᵏ, каждая размера n/bᵏ. Всё сводится к сравнению «сколько работы наверху» и «сколько работы в листьях» — листьев n^(log_b a):

Полезная интуиция без формул: сравните f(n) с n^(log_b a). Кто больше — тот и ответ; если равны — добавьте log n.

Что делать, когда мастер-теорема не применима (неравные части, как в T(n) = T(n/5) + T(7n/10) + Θ(n) у алгоритма «медиана медиан»):

• Метод Акра–Бацци — обобщение на T(n) = Σ aᵢT(n/bᵢ) + f(n). Находим p из Σ aᵢ·bᵢ^(−p) = 1; здесь 1/5 + 7/10 = 0.9 < 1, значит p < 1 и доминирует линейный член ⇒ Θ(n). Оригинал: Akra & Bazzi, 1998.
• Метод подстановки — угадать ответ и доказать индукцией. Работает всегда, но требует угадать.
• Дерево рекурсии — нарисовать и просуммировать по уровням. Лучший способ угадать для последующей подстановки.

5. Трассировка: как выглядит порядок вызовов

Главный источник путаницы у новичков — порядок исполнения. Рекурсия не «сначала делит всё, потом сливает всё»: она идёт в глубину. Вот честная последовательность для merge_sort([3,1,2,4]):

Запомните форму: спуск идёт до самого низа по крайней левой ветке, и только раскрутка «включает» соседей. Именно поэтому в рекурсивном DFS вершины посещаются в порядке preorder на спуске и postorder на подъёме, — деталь, критичная для топологической сортировки; см. Обходы графов: BFS, DFS, топологическая сортировка, компоненты.

6. Каноничные алгоритмы разделяй-и-властвуй

6.1 Quickselect: T(n) = T(n/2) + Θ(n) = Θ(n)

Если после разреза нужно спуститься только в одну половину, сумма работы становится геометрической прогрессией: n + n/2 + n/4 + … = 2n. Это «уменьшай-и-властвуй», и оно даёт линейный поиск k-й порядковой статистики.

import random

def quickselect(a: list[int], k: int) -> int:
    """k-й по величине элемент (0-индексация), Θ(n) в среднем, Θ(1) доп. памяти.

    Реализация итеративная — рекурсия здесь хвостовая, разворачивается тривиально.
    """
    lo, hi = 0, len(a) - 1
    a = a[:]                                   # не портим вход
    while lo < hi:
        p = random.randint(lo, hi)             # рандомизация против adversarial-входов
        a[p], a[hi] = a[hi], a[p]
        pivot = a[hi]
        i = lo
        for j in range(lo, hi):                # схема Ломуто
            if a[j] < pivot:
                a[i], a[j] = a[j], a[i]
                i += 1
        a[i], a[hi] = a[hi], a[i]
        if k == i:
            return a[i]
        elif k < i:
            hi = i - 1                         # спускаемся ТОЛЬКО влево
        else:
            lo = i + 1                         # или ТОЛЬКО вправо
    return a[lo]

Ожидаемое время Θ(n), худшее Θ(n²) — при неудачной последовательности pivot’ов. Детерминированная Θ(n) в худшем случае даётся алгоритмом «медиана медиан» (BFPRT, 1973), но его константа настолько велика, что в проде почти всегда используют рандомизацию с fallback (introselect в libstdc++). Вероятностный анализ такого рода — тема статьи Рандомизированные алгоритмы и вероятностный анализ.

6.2 Карацуба: как экономия одного вызова меняет экспоненту

Умножение двух n-значных чисел «в столбик» стоит Θ(n²). Наивное разбиение пополам не помогает — четыре произведения половинок дают ту же Θ(n²). Анатолий Карацуба в 1960 году показал, что достаточно трёх.

def karatsuba(x: int, y: int) -> int:
    """Умножение длинных чисел за Θ(n^log2(3)) ≈ Θ(n^1.585)."""
    if x < 10 or y < 10:            # база: однозначное — обычное умножение
        return x * y

    n = max(x.bit_length(), y.bit_length())
    m = n // 2                      # режем по битам: основание B = 2, сдвиг на m
    mask = (1 << m) - 1
    a, b = x >> m, x & mask         # x = a·2^m + b
    c, d = y >> m, y & mask         # y = c·2^m + d

    p1 = karatsuba(a, c)            # старшие
    p2 = karatsuba(b, d)            # младшие
    p3 = karatsuba(a + b, c + d)    # трюк: содержит ad+bc внутри себя
    middle = p3 - p1 - p2           # ad + bc за ОДНО умножение вместо двух

    return (p1 << (2 * m)) + (middle << m) + p2

Урок общего характера: сокращение числа рекурсивных вызовов с a до a−1 меняет показатель степени log_b a, а лишние сложения (Θ(n)) тонут в шуме. Ровно та же идея у Штрассена для матриц: 7 умножений подматриц вместо 8 даёт Θ(n^log₂7) ≈ Θ(n^2.807) вместо Θ(n³).

Границы применимости в проде — важнее самого алгоритма:

Именно так устроен GMP — см. gmplib.org/manual/Multiplication-Algorithms. CPython переключается на Карацубу в longobject.c при KARATSUBA_CUTOFF = 70 «цифр» по 30 бит. Числовая сторона вопроса — в статье Теория чисел и математика для алгоритмов и криптографии.

6.3 Ближайшая пара точек: дешёвый combine

T(n) = 2T(n/2) + Θ(n). Разрезаем плоскость вертикальной прямой, рекурсивно находим минимальные расстояния слева (dl) и справа (dr), берём d = min(dl, dr). Наивный combine — проверить все пары через границу, Θ(n²), и всё сломать. Спасает геометрическая лемма: в полосе шириной 2d вокруг разделителя, если отсортировать точки по y, достаточно сравнить каждую точку не более чем с 7 следующими — больше точек на расстоянии ≥ d в прямоугольник 2d × d просто не помещается. Combine становится Θ(n), итого Θ(n log n). Разбор геометрических примитивов — в статье Вычислительная геометрия: примитивы, выпуклая оболочка, sweep line.

7. Рекурсия с возвратом (backtracking)

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

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

def solve_n_queens(n: int) -> int:
    """Число расстановок n ферзей. Классический backtracking с O(1)-проверкой конфликтов."""
    cols = [False] * n
    diag1 = [False] * (2 * n - 1)   # r + c — константа на побочной диагонали
    diag2 = [False] * (2 * n - 1)   # r - c + n - 1 — на главной
    count = 0

    def place(row: int) -> None:
        nonlocal count
        if row == n:                # база: все строки заполнены — решение найдено
            count += 1
            return
        for c in range(n):
            d1, d2 = row + c, row - c + n - 1
            if cols[c] or diag1[d1] or diag2[d2]:
                continue            # ОТСЕЧЕНИЕ: не спускаемся в заведомо мёртвую ветку
            cols[c] = diag1[d1] = diag2[d2] = True     # выбор
            place(row + 1)                             # рекурсия
            cols[c] = diag1[d1] = diag2[d2] = False    # ОТКАТ — обязательно
        # инвариант: здесь массивы в точности такие же, как на входе в place(row)

    place(0)
    return count

Сложность backtracking почти никогда не выражается красивой формулой: верхняя оценка для N ферзей — O(n!), реальная — сильно меньше благодаря отсечениям. Практические правила:

• Отсекать как можно раньше. Проверка «конфликтует ли» до спуска экономит целое поддерево. Перенос проверки на уровень ниже (в базу) превращает алгоритм в тупой перебор.
• Выбирать самую ограниченную переменную первой (MRV, minimum remaining values). В судоку — заполнять клетку с наименьшим числом кандидатов; ускорение на порядки.
• Мутировать состояние, а не копировать. cols[c] = True / cols[c] = False — O(1); передача копии списка — O(n) на вызов и Θ(n·глубина) мусора.

Полный контекст перебора и его связи с NP-полнотой — в статье NP-полнота, приближённые и эвристические алгоритмы.

8. Хвостовая рекурсия и разворачивание в цикл

Хвостовой называется вызов, результат которого возвращается немедленно, без последующих вычислений. return f(x) — хвостовой. return 1 + f(x) и return f(x) + g(y) — нет, потому что после возврата ещё есть работа, а значит, кадр обязан жить.

Компилятор, делающий TCO (tail call optimization), заменяет вызов на переход, переиспользуя кадр — рекурсия становится циклом с O(1) памятью.

Позиция Гвидо ван Россума описана в его посте Tail Recursion Elimination — аргумент в том, что TCO уничтожает информацию в трейсбеке, а Python ценит отладку выше элегантности.

Ручное разворачивание

Хвостовая рекурсия превращается в цикл механически: параметры становятся переменными цикла.

# Было: хвостовая рекурсия
def fact_rec(n: int, acc: int = 1) -> int:
    if n <= 1:
        return acc
    return fact_rec(n - 1, n * acc)

# Стало: тот же алгоритм, O(1) стека
def fact_iter(n: int) -> int:
    acc = 1
    while n > 1:
        acc *= n            # тело шага
        n -= 1              # обновление параметра
    return acc

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

def inorder_iterative(root) -> list:
    """Симметричный обход дерева без рекурсии: явный стек вместо кадров."""
    result, stack, node = [], [], root
    while stack or node:
        while node:                 # спуск в крайнюю левую ветку
            stack.append(node)      # кадр = отложенная работа "вернуться и обработать"
            node = node.left
        node = stack.pop()          # возврат
        result.append(node.val)     # работа "после левого поддерева"
        node = node.right           # переход в правое — хвостовой, кадр не нужен
    return result

Обратите внимание: правый вызов в inorder — хвостовой, поэтому он превратился в присваивание, а левый — нет, поэтому потребовал стека. Это общее правило: в явный стек кладут только нехвостовые вызовы.

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

def dfs_iterative(graph: dict, start):
    """DFS с корректными preorder и postorder — как в рекурсивной версии."""
    visited, pre, post = set(), [], []
    stack = [(start, "enter")]
    while stack:
        node, stage = stack.pop()
        if stage == "exit":                  # эмулируем "код после рекурсивного вызова"
            post.append(node)
            continue
        if node in visited:
            continue
        visited.add(node)
        pre.append(node)
        stack.append((node, "exit"))         # отложенная postorder-работа
        for nb in reversed(graph[node]):     # reversed — чтобы порядок совпал с рекурсивным
            if nb not in visited:
                stack.append((nb, "enter"))
    return pre, post

Когда разворачивать обязательно:

• глубина зависит от размера входа и не ограничена логарифмом (списки, цепочки, пути в графе, разбор пользовательского JSON/XML);
• вход приходит извне и может быть враждебным (см. раздел про безопасность);
• код исполняется в среде с крошечным стеком: embedded, WASM, ядро ОС, корутины/зелёные потоки.

Когда не стоит: если глубина заведомо Θ(log n) — merge sort, сбалансированные деревья, бинарный поиск. Развернутая версия будет длиннее, медленнее в отладке и не даст выигрыша. Читаемость дороже.

9. Мемоизация: где рекурсия встречается с динамикой

Если дерево вызовов содержит повторяющиеся подзадачи, честная рекурсия экспоненциальна:

def fib_naive(n: int) -> int:
    """T(n) = T(n-1) + T(n-2) + O(1) => Θ(φ^n) ≈ Θ(1.618^n). fib_naive(40) — секунды."""
    return n if n < 2 else fib_naive(n - 1) + fib_naive(n - 2)

Одна строка превращает экспоненту в линию:

from functools import cache

@cache                       # functools.cache = lru_cache(maxsize=None), Python 3.9+
def fib(n: int) -> int:
    """Θ(n) времени, Θ(n) памяти. Каждая подзадача вычисляется ровно один раз."""
    return n if n < 2 else fib(n - 1) + fib(n - 2)

Механика простая: число различных подзадач — n, стоимость каждой (без учёта рекурсии) — O(1), значит, суммарно Θ(n). Общая формула для мемоизированной рекурсии:

Время = (число различных состояний) × (стоимость перехода)

Это ровно та же формула, что и для восходящей динамики, — а значит, мемоизация и есть DP, только «сверху вниз». Практические отличия:

• Мемоизация (top-down) вычисляет только достижимые состояния — выигрыш, если пространство состояний разрежено. Проще писать: формула повторяет рекуррентность. Платит за это накладными расходами на вызовы и хеш-таблицу и рискует переполнить стек.
• Табличная динамика (bottom-up) заполняет всё, зато без рекурсии, с лучшей локальностью кэша и возможностью сжать память до пары строк таблицы.

Подводные камни @cache: ключом служат аргументы, поэтому они должны быть хешируемыми (списки не пройдут — передавайте кортежи), кеш живёт до конца жизни функции (утечка памяти в долгоживущих сервисах — используйте lru_cache(maxsize=...)), и кеш держит сильные ссылки на аргументы, что для методов класса означает, что self никогда не будет собран сборщиком. Подробнее: docs.python.org — functools. Полный разбор — в статье Динамическое программирование.

10. Параллельный разделяй-и-властвуй

D&C — почти идеальная форма для параллелизма: подзадачи независимы по определению, значит, их можно считать одновременно. Это модель fork-join.

Единственная нетривиальная деталь — порог зернистости (granularity threshold). Создание задачи стоит порядка микросекунды; если подзадача считается быстрее, накладные расходы съедают весь выигрыш. Поэтому все реальные реализации переключаются на последовательный код ниже порога:

from concurrent.futures import ProcessPoolExecutor

SEQ_THRESHOLD = 100_000     # ниже порога параллелизм только вредит

def par_sum(a: list[int], depth: int = 2) -> int:
    """Параллельная сумма. depth ограничивает число уровней fork — иначе получим 2^d задач."""
    if depth == 0 or len(a) < SEQ_THRESHOLD:
        return sum(a)                       # последовательная база
    mid = len(a) // 2
    with ProcessPoolExecutor(max_workers=2) as pool:
        left = pool.submit(par_sum, a[:mid], depth - 1)
        right = pool.submit(par_sum, a[mid:], depth - 1)
        return left.result() + right.result()

В Python это иллюстрация, а не рецепт: GIL закрывает путь потокам, а процессы платят за сериализацию. Реальные fork-join-фреймворки — java.util.concurrent.ForkJoinPool (с work stealing, дока Oracle), Rust’овский rayon с его join, Intel TBB, std::execution::par в C++17, errgroup в Go.

Теоретическая рамка — модель work/span: work T₁ (суммарная работа) и span T∞ (критический путь). Для merge sort с последовательным слиянием T₁ = Θ(n log n), T∞ = Θ(n) (слияние верхнего уровня не распараллеливается), значит, максимальное ускорение — T₁/T∞ = Θ(log n). Чтобы получить больше, приходится распараллеливать и само слияние. Подробнее — в статье Параллельные и распределённые алгоритмы, консенсус.

11. Типичные ошибки

1. Нет базы или база недостижима. if n == 0 при уменьшении на 2 — на нечётных входах провалимся в минус. Проверяйте if n <= 0.
2. Мера не убывает. f(n) в какой-то ветке вызывает f(n). Частный случай в quicksort: при неудачном partition pivot не исключается из рекурсии, и на массиве одинаковых элементов получаем бесконечный спуск.
3. Срезы вместо индексов. sort(a[:mid]) копирует. Θ(n) на вызов превращает Θ(n log n) в Θ(n log n) времени, но Θ(n log n) памяти, а иногда и в Θ(n²). Передавайте (a, lo, hi).
4. Пересчёт одного и того же. Проверьте: если два разных пути в дереве вызовов приводят к одинаковым аргументам — нужна мемоизация.
5. Забытый откат в backtracking. Мутировали состояние — обязан быть парный undo, лучше через try/finally или контекстный менеджер.
6. Изменяемый аргумент по умолчанию. def walk(node, acc=[]) в Python — список создаётся один раз при определении функции и переживает вызовы. Всегда acc=None + acc = [] if acc is None else acc.
7. setrecursionlimit как «решение». Меняет местами понятную ошибку и сегфолт. Лечите глубину, а не симптом.
8. Рекурсия там, где хватает цикла. Обход связного списка рекурсией — Θ(n) стека без всякой пользы.
9. Ленивая генерация внутри рекурсии. yield from в глубокой рекурсии на генераторах даёт O(глубина) на каждый элемент, если не оптимизировано, — суммарно квадрат.
10. Общее мутируемое состояние между ветками. Если левая ветка меняет структуру, которую читает правая, рекурсивный «скачок веры» перестаёт быть валидным: подзадачи больше не независимы, и индукция ломается.

12. Как это выглядит в проде

Парсеры рекурсивного спуска. Грамматика языка описана рекурсивно (выражение := терм ('+' терм)*), поэтому парсер пишется рекурсивно почти дословно. Так устроены парсер CPython (до 3.9 — LL(1), с 3.9 — PEG, но всё ещё рекурсивный спуск с backtracking, см. PEP 617), компилятор Go (cmd/compile/internal/syntax), Clang, serde_json. Именно поэтому у всех парсеров есть лимит глубины вложенности: json в Python падает с RecursionError на глубоко вложенном массиве, а Go encoding/json имеет явную проверку.

Безопасность. Глубокая рекурсия при разборе недоверенного ввода — реальный класс уязвимостей (CWE-674, Uncontrolled Recursion). Атакующий шлёт [[[[[[...]]]]]] на 100 000 уровней и роняет процесс переполнением стека. Примеры: CVE-2022-3171 (protobuf-java), многочисленные DoS в YAML- и XML-парсерах. Правило: любой рекурсивный разбор внешних данных обязан иметь явный счётчик глубины и жёсткий лимит.

MAX_DEPTH = 64

def parse_node(tokens, depth: int = 0):
    if depth > MAX_DEPTH:
        raise ValueError("превышена максимальная глубина вложенности")   # не даём упасть стеку
    ...
    return parse_node(tokens, depth + 1)

MapReduce и распределённые агрегации. map + древовидный reduce — тот же разделяй-и-властвуй, только «подзадача» уехала на другую машину. Spark строит DAG стадий, где shuffle играет роль combine.

Merkle-деревья. Хеш поддерева = хеш(хеш левого ‖ хеш правого) — рекурсивное определение. Отсюда git (дерево коммитов), IPFS, блокчейны, rsync. Проверка включения элемента — Θ(log n) хешей по пути к корню.

Иерархические структуры в UI и данных. Виртуальный DOM в React обходится рекурсивно; React 16 (Fiber) переписали именно потому, что рекурсивный обход нельзя было прервать посреди — заменили на итеративный обход со связным списком и явным указателем «где мы». Отличная иллюстрация тезиса «разворачивай рекурсию, когда нужен контроль над исполнением».

Файловые системы и сборка. find, du, rsync, обход зависимостей в Bazel/webpack — DFS по дереву с защитой от циклов (символические ссылки!). Забыть про циклы = получить бесконечную рекурсию на первой же symlink-петле.

Сортировки. introsort в C++ — quicksort, который считает глубину рекурсии и при превышении 2·log₂n переключается на heapsort, гарантируя Θ(n log n) в худшем случае. Красивый пример «рекурсия со встроенным предохранителем».

13. Чек-лист проектирования рекурсивного решения

1. Сформулировал ли я задачу так, что она сводится к себе меньшего размера? Какая мера убывает?
2. Покрывает ли база все тривиальные случаи, включая пустой вход и вход размера 1?
3. Независимы ли подзадачи? Если нет — нужна мемоизация (это динамика) или пересмотр разреза.
4. Что теряется на границе разреза, и сколько стоит это восстановить? Именно f(n) определяет сложность.
5. Какова глубина в худшем случае? Если она может быть Θ(n) — планируйте разворачивание в цикл или лимит глубины.
6. Передаю ли я срезы/копии вместо индексов? (Почти всегда это ошибка.)
7. Есть ли порог отсечения на маленьких входах? Для сортировок 16–32 элемента, для параллелизма — десятки тысяч.
8. Если состояние мутируется — есть ли парный откат, и выполняется ли он на всех путях выхода, включая исключения?
9. Может ли вход прийти от недоверенной стороны? Тогда лимит глубины обязателен.
10. Написал ли я в докстринге рекуррентность T(n) = ... и её решение? Если не можете — вы не понимаете свой алгоритм.

Мини-итог

• Рекурсия — это индукция в форме кода: база + шаг + убывающая мера. Доказательство корректности пишется механически, и его стоит писать хотя бы в голове.
• Каждый вызов стоит кадра стека. Глубина = память. Θ(log n) — бесплатно, Θ(n) — риск.
• Разделяй-и-властвуй = divide + conquer + combine, и вся интеллектуальная работа сидит в combine: как дёшево восстановить то, что потерялось на границе разреза.
• T(n) = a·T(n/b) + f(n): сравните f(n) с n^(log_b a); кто больше — тот и ответ. Для неравных разрезов — Акра–Бацци.
• Экономия одного рекурсивного вызова (4→3 у Карацубы, 8→7 у Штрассена) меняет показатель степени — это дороже любых константных оптимизаций.
• Хвостовая рекурсия разворачивается в цикл механически; нехвостовая — через явный стек с сохранением «стадии». Разворачивайте, когда глубина не логарифмическая или вход недоверенный.
• Перекрывающиеся подзадачи ⇒ мемоизация ⇒ это уже динамическое программирование.

Источники

• T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms, 4-е изд. — гл. 2 (merge sort и индукция), гл. 4 (рекуррентности, мастер-теорема, Штрассен), гл. 9 (порядковые статистики): mitpress.mit.edu
• J. Kleinberg, É. Tardos. Algorithm Design, гл. 5 «Divide and Conquer» — инверсии, ближайшая пара, интегральное умножение: www.cs.princeton.edu/~wayne/kleinberg-tardos
• S. Skiena. The Algorithm Design Manual, 3-е изд. — раздел про backtracking и практические советы: algorist.com
• M. Akra, L. Bazzi. On the solution of linear difference equations with variable coefficients (Акра–Бацци): link.springer.com
• А. А. Карацуба, Ю. П. Офман. Умножение многозначных чисел на автоматах, ДАН СССР, 1962; исторический обзор автора: The Complexity of Computations
• V. Strassen. Gaussian Elimination is not Optimal, 1969: doi.org/10.1007/BF02165411
• Blum, Floyd, Pratt, Rivest, Tarjan. Time Bounds for Selection (медиана медиан), 1973: doi.org/10.1016/S0022-0000(73)80033-9
• Guido van Rossum. Tail Recursion Elimination — почему в Python нет TCO: neopythonic.blogspot.com
• Doug Lea. A Java Fork/Join Framework — классика про work stealing: gee.cs.oswego.edu/dl/papers/fj.pdf
• GMP Manual, Multiplication Algorithms — реальные пороги переключения Карацуба/Тоом/FFT: gmplib.org
• CWE-674: Uncontrolled Recursion — класс уязвимостей: cwe.mitre.org/data/definitions/674.html
• Andy Wingo. Fibers, coroutines, threads и серия про стеки — как рантаймы управляют стеком: wingolog.org
• Документация: docs.python.org — functools, docs.rs/rayon, pkg.go.dev/runtime/debug#SetMaxStack

Что дальше

Разделяй-и-властвуй разбивает задачу на независимые части и честно решает каждую. Но существует класс задач, где можно вообще не рассматривать альтернативы: достаточно на каждом шаге взять локально лучший вариант — и он окажется частью глобального оптимума. Звучит слишком хорошо, чтобы быть правдой, и обычно так и есть: интуиция «бери самое выгодное» подводит чаще, чем срабатывает. В следующей статье — Жадные алгоритмы и когда они корректны: матроиды, аргумент обмена (exchange argument), классические задачи о расписаниях и рюкзаке, и главное — как доказать, что жадность здесь работает, вместо того чтобы надеяться на это.