Рекурсия и стек вызовов

Рекурсия — функция, которая вызывает саму себя. Записывается это в две строки, а происходит при этом больше, чем кажется, и на этом «больше» решения падают.

Стек вызовов

Локальные переменные функции живут в специальной области памяти — стеке вызовов. Устроен он предельно просто: есть указатель на вершину, и всё.

Объявили int x — указатель сдвинулся на четыре байта, эти четыре байта и есть x. Вызвали функцию — запомнили текущую вершину, выделили место под её переменные, аргументы и адрес возврата. Функция закончилась — вершину вернули на место.

Освобождение памяти при выходе из функции — это буквально одно присваивание указателя. Данные при этом физически остаются на месте, просто перестают кому-либо принадлежать. Отсюда и берётся мусор в неинициализированных переменных: там лежит то, что оставил предыдущий вызов.

flowchart TD
    A["main<br/>локальные переменные"] --> B["f(5)<br/>n=5, адрес возврата"]
    B --> C["f(4)<br/>n=4, адрес возврата"]
    C --> D["f(3)<br/>n=3, адрес возврата"]
    D --> E["…"]

Сколько кадров помещается

Стек не бесконечен. Обычный лимит — 8 МБ на локальной машине, на олимпиадных серверах чаще 64 или 256 МБ.

Замер на кадре примерно в 64 байта (несколько локальных переменных):

лимит стека	максимальная глубина
8 МБ	около 130 000
64 МБ	около 1 000 000

Проверено: при ulimit -s 8192 глубина 125 000 проходит, 131 250 даёт ошибку сегментации; при 64 МБ проходит миллион и не проходит два.

Практический вывод: рекурсия глубиной до $10^5$ обычно безопасна, глубиной $10^6$ — нет. И чем больше локальных переменных в функции, тем меньше кадров поместится: массив на сотню элементов внутри рекурсивной функции сокращает допустимую глубину в разы.

Заметьте, что переполнение стека выглядит как обычная ошибка исполнения. Никакого сообщения «слишком глубокая рекурсия» вы не получите.

Локальный массив — тоже стек

Гораздо чаще стек переполняют не рекурсией, а вот этим:

int main() {
    int a[10000000];   // 40 МБ на стеке — падение
}

Локальный массив живёт на стеке, а стек меньше, чем вся доступная память программы. При лимите памяти 256 МБ и лимите стека 64 МБ такой массив не поместится, хотя по условию задачи памяти достаточно.

Правильно — глобальный массив или vector:

int a[10000000];              // глобальный: в другой области памяти, помещается
vector<int> b(10000000);      // данные в куче, на стеке только заголовок

Это одна из немногих ситуаций, где глобальная переменная — правильное решение, а не небрежность.

Хвостовая рекурсия

Если функция вызывает себя ровно один раз и последним действием, рекурсия называется хвостовой.

long long power(long long base, int exp, long long acc = 1) {
    if (exp == 0) return acc;
    return power(base, exp - 1, acc * base);   // хвостовой вызов
}

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

long long power(long long base, int exp) {
    long long acc = 1;
    while (exp-- > 0) acc *= base;
    return acc;
}

Компиляторы с оптимизацией умеют делать это сами, но гарантий нет: с -O0 оптимизация не сработает, а именно так собирают код некоторые проверяющие системы. Если глубина может быть большой — переписывайте руками.

Когда рекурсия оправдана

Рекурсия не бесплатна: каждый вызов — это работа с кадром стека, и цикл всегда быстрее.

Но есть задачи, где она незаменима:

• обход дерева или графа — итеративная версия требует явного стека и получается длиннее;
• перебор с возвратом — состояние естественно живёт в кадрах;
• разделяй и властвуй — сортировка слиянием, быстрая сортировка;
• ленивая динамика — когда порядок обсчёта неочевиден.

Правило простое: если порядок обхода очевиден и одномерен, пишите цикл. Если структура ветвится — рекурсию.

Как обойти ограничение глубины

Когда глубина всё же велика:

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

Увеличить стек. На Codeforces это делают запуском решения в отдельном потоке с большим стеком; локально помогает ulimit -s unlimited. На школьных олимпиадах такой возможности обычно нет.

Уменьшить кадр. Вынести массивы и большие структуры в глобальные переменные, передавать по ссылке, а не по значению. Иногда этого достаточно, чтобы глубина выросла втрое.