Рекурсия: как понять и не уйти в бесконечный вызов

База и шаг рекурсии, стек вызовов, почему наивный Фибоначчи медленный, как помогает мемоизация и когда лучше написать цикл. Примеры на C и Python.

Рекурсивная функция вызывает сама себя. На лекции это выглядит как фокус: факториал в три строки, и непонятно, почему он вообще останавливается. А в лабораторной та же идея заканчивается Segmentation fault в C или RecursionError в Python. Разберём, из чего состоит любая рекурсия, что происходит в памяти при каждом вызове, почему одна рекурсия считает мгновенно, а другая минутами, и когда её лучше заменить циклом. Примеры на C (gcc 12) и Python 3.12, время замерено на нашем компьютере, у вас цифры будут другими.

База и шаг

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

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

Факториал: 0! = 1 (база), n! = n · (n − 1)! (шаг).

long long fact(int n) {
    if (n == 0)
        return 1;
    return n * fact(n - 1);
}
def fact(n):
    if n == 0:
        return 1
    return n * fact(n - 1)

fact(5) даёт 120 в обоих языках. Разница появляется на больших числах: в C long long вмещает максимум 20! = 2432902008176640000, дальше переполнение и мусор. В Python целые числа не ограничены, и fact(25) честно выдаёт 15511210043330985984000000.

Главное условие: каждый шаг должен приближать к базе. В fact(n - 1) число уменьшается и рано или поздно станет нулём. Если шаг к базе не ведёт, вызовы не кончатся.

Что происходит в стеке вызовов

Стопка бумажных листов, которая растёт вверх, а войлочный кот Тиль кладёт сверху ещё один лист

Каждый вызов функции получает свой кадр в стеке: место под аргументы, локальные переменные и адрес, куда вернуться. Вызов fact(4) не может закончиться, пока не вернётся fact(3), и так до базы. Добавим печать с отступом по глубине:

fact(4)
  fact(3)
    fact(2)
      fact(1)
        fact(0)
        return 1
      return 1
    return 2
  return 6
return 24

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

Это видно в gdb. Поставим точку останова на базу и посмотрим стек, когда до неё дошли:

(gdb) break fact if n == 0
(gdb) run
Breakpoint 1, fact (n=0) at fact4.c:4
(gdb) bt
#0  fact (n=0) at fact4.c:4
#1  0x0000aaaaaaaa0788 in fact (n=1) at fact4.c:6
#2  0x0000aaaaaaaa0788 in fact (n=2) at fact4.c:6
#3  0x0000aaaaaaaa0788 in fact (n=3) at fact4.c:6
#4  0x0000aaaaaaaa0788 in fact (n=4) at fact4.c:6
#5  0x0000aaaaaaaa07a8 in main () at fact4.c:10

Как придумать рекурсивное решение

Три вопроса:

  1. Какой самый простой вход, где ответ очевиден? Это база.
  2. Как свести задачу к такой же, но меньшей?
  3. Как из ответа для меньшей задачи получить ответ для текущей?

Сумма цифр числа: если число однозначное, ответ само число. Иначе последняя цифра плюс сумма цифр числа без неё.

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

print(digit_sum(2026))   # 10

Не пытайтесь мысленно развернуть все вызовы. Достаточно проверить базу и поверить, что вызов на меньшем входе уже работает правильно. Это та же индукция, что в математике.

Бесконечная рекурсия и переполнение стека

Вызовем наш факториал с -1. Шаг уменьшает число: −2, −3, … До нуля оно не дойдёт никогда.

В C каждый кадр занимает место в стеке, а стек ограничен. В Linux и на Mac его размер по умолчанию около 8 МБ (ulimit -s у нас показал 8192 и 8176 КБ). Когда место кончается, программа падает:

$ ./inf
Segmentation fault (core dumped)

По этому сообщению не видно, что виновата рекурсия. Санитайзер называет причину прямо:

$ gcc -g -fsanitize=address inf.c -o inf && ./inf
==15==ERROR: AddressSanitizer: stack-overflow on address 0xffffc236bff0 ...
    #0 0xca1232410994 in fact /tmp/w/inf.c:3
    #1 0xca12324109c4 in fact /tmp/w/inf.c:6
    #2 0xca12324109c4 in fact /tmp/w/inf.c:6

Python ограничивает глубину заранее, по умолчанию 1000 вызовов (sys.getrecursionlimit()):

  File "inf.py", line 6, in fact
    return n * fact(n - 1)
               ^^^^^^^^^^^
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

Строка Previous line repeated 996 more times почти всегда значит, что база не срабатывает. Что проверить:

  • есть ли база вообще и выполняется ли до рекурсивного вызова;
  • достижима ли она: n == 0 не сработает для отрицательного n, надёжнее n <= 0;
  • меняется ли аргумент: fact(n) вместо fact(n - 1) зациклится на первом же шаге.

Ещё одна частая ошибка в Python не зацикливает, а ломает ответ: забытый return перед рекурсивным вызовом. Функция возвращает None, и вызов уровнем выше падает с TypeError: unsupported operand type(s) for *: 'int' and 'NoneType'.

Бывает, что база правильная, но глубина просто большая. Наша функция суммы от 1 до n в C при сборке с -O0 прошла глубину 100 000 и упала на 1 000 000. С -O2 она не упала: компилятор превратил рекурсию в цикл. Рассчитывать на это не стоит, в учебной проверке могут собирать без оптимизации. В Python лимит поднимается через sys.setrecursionlimit, но документация предупреждает, что слишком большой лимит может обрушить интерпретатор (документация Python). Если глубина зависит от размера входа и может дойти до десятков тысяч, лучше переписать на цикл.

Фибоначчи: почему наивная рекурсия медленная

long long fib(int n) {
    if (n < 2)
        return n;
    return fib(n - 1) + fib(n - 2);
}

Код верный, но каждый вызов порождает два новых, и одни и те же значения считаются снова и снова. Дерево вызовов для fib(5):

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   │   ├── fib(1)
│   │   │   └── fib(0)
│   │   └── fib(1)
│   └── fib(2)
│       ├── fib(1)
│       └── fib(0)
└── fib(3)
    ├── fib(2)
    │   ├── fib(1)
    │   └── fib(0)
    └── fib(1)

fib(3) считается дважды, fib(2) трижды. Посчитаем вызовы счётчиком:

fib(10) = 55, calls = 177
fib(20) = 6765, calls = 21891
fib(30) = 832040, calls = 2692537
fib(40) = 102334155, calls = 331160281

Число вызовов растёт примерно в 1,6 раза с каждым следующим n, то есть экспоненциально. В C fib(40) ещё укладывается в полсекунды. В Python fib(35) у нас считалась 0,87 с, fib(40) уже 9,75 с, а fib(50) по той же пропорции заняла бы около 20 минут.

Мемоизация: запоминаем готовые ответы

Раз одни и те же значения считаются много раз, их можно запомнить. В Python это делает декоратор functools.cache:

from functools import cache

@cache
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(90))   # 2880067194370816120

fib(32) с кэшем у нас посчитался за 0,00003 с вместо 0,2 с без него. В C то же самое делают массивом:

long long memo[100];

long long fib(int n) {
    if (n < 2)
        return n;
    if (memo[n] != 0)
        return memo[n];
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

Для fib(40) вместо 331 миллиона вызовов теперь 79. Глобальный массив в C заполнен нулями, а fib(n) для n ≥ 2 никогда не равно нулю, поэтому ноль работает как отметка «ещё не считали». Если ноль может быть настоящим ответом, заведите отдельный массив флагов или заполните memo значением -1.

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

Когда лучше цикл

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

long long fib(int n) {
    long long a = 0, b = 1;
    for (int i = 0; i < n; i++) {
        long long t = a + b;
        a = b;
        b = t;
    }
    return a;
}

Этот вариант считает fib(90) за 90 шагов и без лишней памяти. Цикл лучше, когда:

  • глубина зависит от входа и может быть большой (обход списка из 10⁵ элементов, сумма до n);
  • каждый вызов делает один рекурсивный вызов (факториал, сумма, степень по одному множителю);
  • в задаче есть ограничение по памяти.

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

def permutations(items, current=None):
    if current is None:
        current = []
    if not items:
        print(current)
        return
    for i in range(len(items)):
        rest = items[:i] + items[i + 1:]
        permutations(rest, current + [items[i]])

permutations([1, 2, 3])

Печатает шесть строк от [1, 2, 3] до [3, 2, 1]. Циклом такое пишется заметно сложнее. Глубина здесь равна длине списка, так что стек не переполнится.

Как отлаживать рекурсию

  • Печатайте вход и выход каждого вызова с отступом по глубине, как в примере с fact(4) выше. Сразу видно, где ветка не дошла до базы.
  • Проверьте функцию на базе и на входе на один больше базы. Если fact(0) и fact(1) верны, остальное обычно тоже.
  • В gdb bt показывает все кадры рекурсии с аргументами. При бесконечной рекурсии их будут тысячи, тогда bt 10 выведет только десять последних вызовов.
  • Трассировка RecursionError в Python не показывает значения аргументов. Добавьте print(n) в начало функции и запустите на маленьком входе: по первым строкам видно, куда уходит аргумент.

Как с этим помогает Tilpi

В чате задания Tilpi разбирает тему по шагам и объясняет код: можно показать свою рекурсивную функцию и спросить, почему она не останавливается, или попросить расписать стек вызовов для конкретного входа. Если к заданию приложены лекции, ответ опирается на них и ссылается на страницу. Исполнитель запускает код на C и Python в отдельной изолированной машине, пишет и прогоняет тесты, ищет ошибки и предлагает исправления. Чат по своим файлам работает бесплатно с подтверждённой почтой в пределах лимитов, исполнитель на уровне «Быстрая» входит в тариф «Лайт», все уровни открыты с тарифа «Плюс».

ИИ для учёбы. По вашим лекциям.

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

Разобрать рекурсию в Tilpi