Рекурсия: от математики к коду

Связываем математическую рекурсию с рекурсией в программировании и доказываем, что рекурсивный код корректен.

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

Зачем это нужно

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

Анатомия рекурсии

У любой корректной рекурсии есть две обязательные части:

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

Если базы нет или задача не уменьшается — получится бесконечная рекурсия (на практике — переполнение стека). Сравни с индукцией: базовый случай рекурсии — это база индукции, а рекурсивный случай — это шаг. Не совпадение: доказывать корректность рекурсии естественнее всего индукцией.

Классика №1: факториал

Факториал n! — произведение всех чисел от 1 до n. Его рекурсивное определение:

База: 0! = 1.
Шаг: n! = n · (n−1)!.

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

def factorial(n):
    if n == 0:            # базовый случай
        return 1
    return n * factorial(n - 1)   # рекурсивный случай

for n in range(7):
    print(f"{n}! = {factorial(n)}")

Вывод:

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720

Почему мы уверены, что код верен для всех n? Индукция. База: factorial(0) возвращает 1 — верно. Шаг: предположим, factorial(n−1) правильно вернул (n−1)!; тогда factorial(n) вернёт n · (n−1)! = n! — тоже верно. Доказали для всех n. Вот она, связь рекурсии и индукции в действии.

Классика №2: Ханойские башни

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

Рекурсивная идея гениально проста: чтобы перенести n дисков с A на C (через B), нужно:

перенести верхние n−1 дисков с A на B (та же задача, меньше на 1);
переложить самый большой диск с A на C (один ход);
перенести n−1 дисков с B на C (снова та же задача).

Число ходов задаётся рекуррентой T(n) = 2·T(n−1) + 1 с базой T(0) = 0. Решим её — и проверим, что замкнутая формула 2^n − 1 верна.

def hanoi_moves(n):
    if n == 0:
        return 0
    return 2 * hanoi_moves(n - 1) + 1     # T(n) = 2T(n-1) + 1

counts = [hanoi_moves(n) for n in range(8)]
formula = [2 ** n - 1 for n in range(8)]
print("Число ходов:        ", counts)
print("Формула 2^n - 1:    ", formula)
print("Совпадают:", counts == formula)

Вывод:

Число ходов:         [0, 1, 3, 7, 15, 31, 63, 127]
Формула 2^n - 1:     [0, 1, 3, 7, 15, 31, 63, 127]
Совпадают: True

Рекуррента T(n) = 2·T(n−1) + 1 разворачивается в формулу 2^n − 1. Для 64 дисков (легенда о башне Брахмы) это 2^64 − 1 ходов — больше 18 квинтиллионов. Если делать ход в секунду, не хватит и возраста Вселенной. Так дискретная математика наглядно показывает, что такое экспоненциальный рост.

Рекурсивные определения структур

Рекурсия описывает не только функции, но и сами объекты. «Список — это либо пустой список, либо элемент плюс список». «Дерево — это узел, у которого детьми являются деревья». Такие индуктивно определённые структуры естественно обходятся рекурсией, и утверждения про них доказываются структурной индукцией — той же идеей «база + шаг», но по строению объекта, а не по числу.

За пределами линейных рекуррент: метод производящих функций

Характеристическое уравнение решает линейные рекурренты, но не все рекурренты линейны. Знаменитый пример — числа Каталана, которые считают, сколькими способами можно правильно расставить скобки, или сколько существует различных двоичных деревьев из n узлов. Их рекуррента «свёрточная»: каждый член — сумма произведений предыдущих, и характеристический метод тут бессилен.

Для таких случаев есть более мощный инструмент — производящие функции. Идея красивая: всю бесконечную последовательность a0, a1, a2, ... «упаковывают» в один объект — формальный степенной ряд a0 + a1·x + a2·x² + .... Рекуррента на числах превращается в уравнение на эту функцию, которое часто решается алгеброй, а из ответа «вынимают» формулу для члена. Этим методом получают замкнутые формулы там, где прямой подход не работает. Производящие функции — вершина школьной комбинаторики и мост к высшей математике; здесь достаточно знать, что они существуют и что рекурренты бывают сложнее линейных.

Ещё один пример: сумма цифр числа

Рекурсия отлично подходит, когда задачу можно «откусить с краю». Посчитаем сумму цифр числа: последняя цифра — это n % 10, а сумму остальных цифр найдём рекурсивно для n // 10 (число без последней цифры). База — однозначное число: его сумма цифр равна ему самому.

def digit_sum(n):
    if n < 10:                  # база: однозначное число
        return n
    return n % 10 + digit_sum(n // 10)   # последняя цифра + сумма остальных

for x in [7, 123, 99999]:
    print(f"digit_sum({x}) =", digit_sum(x))

Вывод:

digit_sum(7) = 7
digit_sum(123) = 6
digit_sum(99999) = 45

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

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

Забыть базовый случай. Рекурсия без базы не остановится — переполнение стека. База обязательна.
Не уменьшать задачу. Если рекурсивный вызов идёт с тем же или большим аргументом, до базы не дойти. Каждый шаг должен приближать к базе.
Бояться «функция вызывает себя». Каждый вызов работает с меньшими данными и в итоге упирается в базу — никакой магии, обычная цепочка как в индукции.

Итог

Рекурсия = базовый случай + сведение к меньшей подзадаче.
Рекурсия и индукция — одна идея: рекурсия строит, индукция доказывает.
Корректность рекурсивной функции доказывают индукцией (база = базовый случай, шаг = рекурсивный).
Ханойские башни: T(n) = 2·T(n−1) + 1 = 2^n − 1 — наглядный экспоненциальный рост.