Рекурсия: функция, вызывающая саму себя

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

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

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

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

Рекурсия часто пугает новичков, и причина в том, что она ломает привычный способ думать. Обычно мы решаем задачу «снизу вверх»: делаем шаг, потом ещё шаг, накапливаем результат. Рекурсия предлагает противоположное — думать «сверху вниз», доверяя самому себе. Формула проста: предположите, что функция уже умеет решать задачу для меньшего случая, и постройте из этого решение для большего. Звучит как жульничество — мы используем то, что ещё не написали, — но именно это «доверие» и есть суть рекурсивного мышления. Когда вы пишете factorial(n) = n * factorial(n-1), вы не вычисляете факториал руками; вы лишь формулируете, как ответ для n связан с ответом для n−1, и добавляете точку опоры — базу. Освоить этот сдвиг в мышлении важнее, чем заучить конкретные примеры: он открывает целый класс задач, которые «в лоб» решить почти невозможно.

Два обязательных элемента

Любая корректная рекурсия состоит из двух частей:

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

Если забыть базу или не приближаться к ней, рекурсия не остановится — программа упадёт. Классический пример — факториал: n! = n · (n−1)!, а 0! = 1 (это база):

def factorial(n):
    if n == 0:            # база: дальше не спускаемся
        return 1
    return n * factorial(n - 1)   # шаг: задача через меньшую

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

Вывод:

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

Как это работает: стек вызовов

При вызове factorial(4) функция приостанавливается и ждёт factorial(3), тот ждёт factorial(2) и так до базы factorial(0)=1. Затем результаты «всплывают» обратно, перемножаясь. Эти приостановленные вызовы хранятся в специальной области памяти — стеке вызовов. Проследим спуск и подъём с печатью отступов:

def factorial(n, depth=0):
    print("  " * depth + f"вход factorial({n})")
    if n == 0:
        print("  " * depth + "база, возвращаю 1")
        return 1
    result = n * factorial(n - 1, depth + 1)
    print("  " * depth + f"возвращаю {n} * ... = {result}")
    return result

factorial(3)

Вывод:

вход factorial(3)
  вход factorial(2)
    вход factorial(1)
      вход factorial(0)
      база, возвращаю 1
    возвращаю 1 * ... = 1
  возвращаю 2 * ... = 2
возвращаю 3 * ... = 6

Числа Фибоначчи и ловушка медленной рекурсии

Числа Фибоначчи определяются рекурсивно: каждое — сумма двух предыдущих, а первые два равны 1. Прямая запись красива, но скрывает проблему: fib(n) заново пересчитывает одни и те же значения многократно. Покажем и саму функцию, и количество вызовов — оно растёт лавинообразно:

calls = 0
def fib(n):
    global calls
    calls += 1
    if n <= 2:
        return 1
    return fib(n - 1) + fib(n - 2)

for n in (5, 10, 20):
    calls = 0
    value = fib(n)
    print(f"fib({n}) = {value}, вызовов функции: {calls}")

Вывод:

fib(5) = 5, вызовов функции: 9
fib(10) = 55, вызовов функции: 109
fib(20) = 6765, вызовов функции: 13529

Видите взрыв? Для fib(20) функция вызвалась 13 529 раз ради 20-го числа. Лечится это запоминанием уже вычисленных значений (мемоизацией) — но сама проблема отлично показывает, что «красиво» не всегда «быстро».

Мемоизация: рекурсия с памятью

Сохраним вычисленные значения в словаре — и повторных вызовов не будет. Сравните число вызовов с предыдущим примером:

memo = {}
calls = 0
def fib(n):
    global calls
    calls += 1
    if n <= 2:
        return 1
    if n in memo:                 # уже считали — берём готовое
        return memo[n]
    memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]

print("fib(20) =", fib(20), "вызовов:", calls)

Вывод:

fib(20) = 6765 вызовов: 37

Ханойские башни: рекурсия во всей красе

Задача о Ханойских башнях — эталон рекурсивного мышления. Нужно перенести стопку дисков с одного стержня на другой, перекладывая по одному и не кладя больший на меньший. Решение умещается в три строки рекурсии: перенести верхние n−1 дисков на промежуточный стержень, переложить самый большой, затем перенести n−1 дисков сверху. Минимальное число ходов — 2ⁿ−1:

moves = 0
def hanoi(n, src, dst, tmp):
    global moves
    if n == 1:
        moves += 1
        print(f"диск 1: {src} → {dst}")
        return
    hanoi(n - 1, src, tmp, dst)        # верхние n-1 на промежуточный
    moves += 1
    print(f"диск {n}: {src} → {dst}")   # самый большой на место
    hanoi(n - 1, tmp, dst, src)        # n-1 поверх него

hanoi(3, "A", "C", "B")
print("всего ходов:", moves, "(теория: 2^3 - 1 =", 2**3 - 1, ")")

Вывод:

диск 1: A → C
диск 2: A → B
диск 1: C → B
диск 3: A → C
диск 1: B → A
диск 2: B → C
диск 1: A → C
всего ходов: 7 (теория: 2^3 - 1 = 7 )

Попробуй сам

Напишем рекурсивную сумму цифр числа — частый школьный приём. Идея: последняя цифра плюс сумма цифр оставшегося числа. База — однозначное число.

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

for x in (7, 123, 99999, 2025):
    print(f"сумма цифр {x} = {digit_sum(x)}")

Вывод:

сумма цифр 7 = 7
сумма цифр 123 = 6
сумма цифр 99999 = 45
сумма цифр 2025 = 9

Частые ошибки

• Нет базы или до неё не доходят. Тогда рекурсия бесконечна и программа падает с «превышением глубины рекурсии».
• Шаг не уменьшает задачу. Каждый рекурсивный вызов обязан приближать к базе (меньше число, короче список).
• Наивная рекурсия там, где много повторов. Фибоначчи без мемоизации экспоненциально медленный; запоминайте результаты.
• Забывают вернуть результат рекурсивного вызова. factorial(n-1) без return или умножения теряет ответ.

Итоги

• Рекурсия = база (простой случай) + шаг (задача через свою меньшую версию, приближающий к базе).
• Вызовы хранятся в стеке; результаты «всплывают» обратно после достижения базы.
• Наивная рекурсия может быть экспоненциально медленной (Фибоначчи) — спасает мемоизация.
• Рекурсия незаменима для вложенных задач: Ханойские башни, обход деревьев, разбор выражений.