Рекурсивная функция вызывает сама себя. На лекции это выглядит как фокус: факториал в три строки, и непонятно, почему он вообще останавливается. А в лабораторной та же идея заканчивается 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
Как придумать рекурсивное решение
Три вопроса:
- Какой самый простой вход, где ответ очевиден? Это база.
- Как свести задачу к такой же, но меньшей?
- Как из ответа для меньшей задачи получить ответ для текущей?
Сумма цифр числа: если число однозначное, ответ само число. Иначе последняя цифра плюс сумма цифр числа без неё.
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 в отдельной изолированной машине, пишет и прогоняет тесты, ищет ошибки и предлагает исправления. Чат по своим файлам работает бесплатно с подтверждённой почтой в пределах лимитов, исполнитель на уровне «Быстрая» входит в тариф «Лайт», все уровни открыты с тарифа «Плюс».
