1. Введение
Когда вы только начинаете программировать, рекурсия часто выглядит как магия: короткий код, «сам себя вызывает», и почему-то всё работает. Проблема в том, что магия обычно заканчивается ровно в тот момент, когда вы подали на вход число побольше, строку подлиннее или случайно забыли базовый случай. И тогда программа падает так уверенно, будто это была её мечта с детства.
Важно понимать два типа ограничений. Во‑первых, рекурсия ест память стека, и если глубина вызовов слишком велика, стек закончится. Во‑вторых, каждый вызов функции стоит времени: даже если стек не переполнится, рекурсивное решение может сделать настолько много вызовов, что вы успеете попить чай, остыть, согреть чай, снова остыть — и всё ещё ждать ответ.
Кстати, стандарты языков не обещают вам «бесконечный стек»: конкретные лимиты зависят от платформы и настроек, а в документах C++ даже существует отдельная тема про implementation limits (ограничения реализации), то есть «сколько чего гарантировать нельзя».
2. Глубина рекурсии и рост стека
Если рекурсию представить как «матрёшку вызовов», то глубина рекурсии — это сколько матрёшек одновременно раскрыто. То есть сколько вызовов вашей функции прямо сейчас «висит в воздухе» и ещё не дошло до return.
Ключевая мысль тут простая: глубина рекурсии ≈ сколько кадров стека накопилось. А стек — не бездонная сумка Гермионы (в жизни, увы, чаще наоборот).
Чтобы это не оставалось философией, зафиксируем максимально практично: глубина растёт на 1 при каждом самовызове, и уменьшается на 1 при каждом return.
Мини‑схема стека при рекурсии
Представим, что у нас есть factorial(3):
flowchart TB
A["main()"] --> B["factorial(3)"]
B --> C["factorial(2)"]
C --> D["factorial(1)"]
D --> E["factorial(0) // база"]
Идея такая: пока мы не дошли до базы (factorial(0)), мы только «накапливаем» вызовы. С точки зрения стека это выглядит как стопка кадров, где верхний — самый свежий вызов.
Как оценить глубину заранее
Прежде чем писать рекурсию (или хотя бы прежде чем радостно отправлять её в продакшен), полезно задать себе вопрос: на сколько шагов может углубиться рекурсия при максимальном входе?
Если у вас линейная рекурсия вида f(n) → f(n-1), то грубо глубина будет порядка n (плюс/минус 1). Это уже достаточно, чтобы понять: n = 10 — ок, n = 1'000'000 — почти наверняка «ой».
Если рекурсия идёт по строке и индекс увеличивается на 1, то глубина будет порядка длины строки. И да, строка на 200 тысяч символов — это уже не «ой», это «ой-ой-ой».
Визуализация глубины в коде
Сделаем маленькую функцию, которая печатает глубину отступами. Код короткий, а эффект почти терапевтический: вы видите, как растёт стек.
#include <iostream>
void trace_depth(int n, int depth) {
std::cout << depth << ": n=" << n << '\n'; // 0: n=3 ...
if (n == 0) return;
trace_depth(n - 1, depth + 1);
}
Если вызвать trace_depth(3, 0), вывод будет примерно таким:
// 0: n=3
// 1: n=2
// 2: n=1
// 3: n=0
Здесь глубина равна depth, и она растёт ровно на каждом рекурсивном шаге.
3. Переполнение стека — stack overflow
Когда стек заканчивается, программа обычно не «вежливо сообщает», что ей тесно. Она чаще делает резкое движение в стиле «мне пора» и аварийно завершает выполнение. В разных средах вы можете увидеть разные сообщения, но смысл один: рекурсия ушла слишком глубоко, память под кадры стека закончилась.
Важно понимать: переполнение стека связано именно с глубиной, а не с общим числом вызовов. Можно сделать миллиард вызовов функции в цикле — стек при этом не растёт. Но если вы сделали, например, 200000 вложенных вызовов рекурсией — стек вполне может закончиться даже при сравнительно «небольшом» общем числе операций.
Почему большие локальные переменные усугубляют ситуацию
Каждый кадр стека хранит не только параметры и адрес возврата, но и локальные переменные. Если вы в рекурсивной функции создаёте что-то тяжёлое, например большой массив или длинную строку, то каждый уровень рекурсии будет «съедать» больше памяти.
Даже без сложных типов можно случайно сделать себе хуже. Например, если вы положили в кадр стека int huge[100000]; (так делать не надо), глубина станет критичной очень быстро.
Учебный предохранитель: ограничиваем глубину явно
Мы пока не обсуждали продвинутую обработку ошибок и исключения, поэтому в учебном коде можно использовать простой флаг ok (через ссылку) и ограничение по глубине.
#include <iostream>
long long factorial_safe(int n, int depth, int maxDepth, bool& ok) {
if (depth > maxDepth) { ok = false; return 0; }
if (n == 0) return 1;
return n * factorial_safe(n - 1, depth + 1, maxDepth, ok);
}
Здесь идея проста: если углубились слишком далеко, мы прекращаем вычисление. Это не «идеальная архитектура», но как учебный предохранитель — очень полезно: вы хотя бы контролируете момент, когда всё пошло не туда.
4. Стоимость вызова функции
Теперь про вторую проблему: даже если стек не переполняется, рекурсивное решение может быть ощутимо медленнее циклического. Причина не в мистике, а в том, что вызов функции имеет накладные расходы.
На уровне нашей «модели новичка» можно считать так: при каждом вызове функции нужно сохранить точку возврата, передать параметры, создать локальные переменные, а потом корректно вернуться обратно. Компьютер делает это очень быстро, но если вы сделали это 50 миллионов раз — внезапно оказывается, что «очень быстро» стало «почему вентилятор ноутбука взлетает».
Самый честный способ почувствовать стоимость — посчитать вызовы
Мы пока не меряем время через std::chrono (это будет гораздо позже), но мы можем измерить «масштаб работы» очень простым способом: посчитать, сколько раз функция была вызвана.
И тут нам пригодится передача параметра по ссылке int& (мы уже это умеем): это позволит накапливать счётчик без глобальных переменных.
#include <iostream>
int sum_to_counted(int n, int& calls) {
++calls;
if (n == 0) return 0;
return n + sum_to_counted(n - 1, calls);
}
Если вызвать так:
int calls = 0;
std::cout << sum_to_counted(5, calls) << '\n'; // 15
std::cout << "calls=" << calls << '\n'; // calls=6
Мы увидим, что sum_to(5) вызвался 6 раз: для n = 5,4,3,2,1,0.
Факториал: рекурсия против цикла
Факториал — хороший пример, потому что рекурсивная версия короткая и красивая, а циклическая — тоже простая.
Рекурсивная версия (посчитаем вызовы):
#include <iostream>
long long factorial_rec(int n, int& calls) {
++calls;
if (n == 0) return 1;
return n * factorial_rec(n - 1, calls);
}
Циклическая версия (вызовов функций нет, кроме самой):
#include <iostream>
long long factorial_loop(int n) {
long long r = 1;
for (int i = 2; i <= n; ++i) r *= i;
return r;
}
Важно не сделать неверный вывод «рекурсия всегда хуже». Для n = 10 разницы вы почти не почувствуете. Но если задача такая, что глубина или число вызовов растут сильно, накладные расходы становятся заметными.
Есть рекурсия «дешёвая»: пример с НОД
Теперь важный нюанс: рекурсия бывает разной. Есть рекурсии, которые делают мало шагов, быстро сходятся к базе и не создают огромного количества вызовов. Классический пример — алгоритм Евклида для НОД.
#include <iostream>
int gcd(int a, int b, int& calls) {
++calls;
if (b == 0) return a;
return gcd(b, a % b, calls);
}
Почему это обычно работает быстро (в рамках нашей интуитивной модели)? Потому что b в паре (a, b) достаточно быстро уменьшается до нуля, и глубина обычно не огромная. Это пример рекурсии, которая часто оказывается и понятной, и практичной.
5. Профилируем рекурсию: глубина и число вызовов
Вот здесь многие новички путаются, и это нормально: у мозга нет встроенного «датчика рекурсивных деревьев». Поэтому проговорим максимально явно.
Глубина — сколько вызовов одновременно «живёт» в стеке.
Общее число вызовов — сколько раз функция была вызвана за всё время выполнения.
И они могут вести себя очень по‑разному.
Fibonacci без оптимизаций: много вызовов при небольшой глубине
Вот «наивная» рекурсивная версия Фибоначчи:
#include <iostream>
int fib(int n, int& calls) {
++calls;
if (n <= 1) return n;
return fib(n - 1, calls) + fib(n - 2, calls);
}
С виду всё прилично. Но тут есть подвох: каждый вызов порождает два новых вызова, то есть вызовы разрастаются как снежный ком, который катится с горы и собирает весь снег в ближайших трёх районах.
При этом глубина будет порядка n (потому что есть ветка n, n-1, n-2, ...), а вот общее число вызовов растёт очень быстро.
Если вы запустите fib(n) со счётчиком, вы увидите примерно такую картину (точные числа зависят от реализации, но тенденция железная):
|
|
примерное calls |
|---|---|---|
| 5 | 5 | десятки |
| 10 | 55 | сотни/тысячи |
| 20 | 6765 | десятки тысяч+ |
И вот тут рекурсия начинает проигрывать не потому, что «рекурсия плохая», а потому что алгоритм порождает слишком много повторных вызовов. Мы сознательно не обсуждаем сегодня техники ускорения этого примера (иначе мы уедем в отдельную большую тему), но как предупреждение о стоимости вызовов — это идеальный кейс.
Практический пример: добавляем диагностику в RecursionLab
Чтобы примеры не были «в вакууме», давайте представим, что у нас есть маленькое учебное приложение RecursionLab (мы его начали в прошлых лекциях): оно умеет считать что‑то рекурсивно и печатать результат. Сегодня мы добавим туда две вещи: счётчик вызовов и оценку максимальной глубины.
Сделаем маленькую функцию, которая обновляет максимум глубины:
#include <iostream>
void update_max_depth(int depth, int& maxDepth) {
if (depth > maxDepth) maxDepth = depth;
}
Теперь факториал с учётом глубины и вызовов:
#include <iostream>
long long factorial_profiled(int n, int depth, int& calls, int& maxDepth) {
++calls;
update_max_depth(depth, maxDepth);
if (n == 0) return 1;
return n * factorial_profiled(n - 1, depth + 1, calls, maxDepth);
}
Обратите внимание на важный практический момент: depth мы увеличиваем до рекурсивного вызова, потому что следующий вызов — это «следующий этаж».
И вот как это может использоваться в main():
#include <iostream>
int main() {
int n = 5;
int calls = 0, maxDepth = 0;
long long r = factorial_profiled(n, 0, calls, maxDepth);
std::cout << "factorial=" << r << '\n'; // factorial=120
std::cout << "calls=" << calls << '\n'; // calls=6
std::cout << "depth=" << maxDepth << '\n';// depth=5
}
Здесь получается хорошая проверка здравого смысла: для n = 5 глубина 5, а вызовов 6 (потому что есть ещё базовый n=0). Если у вас получилось иначе — значит, вы где-то ошиблись с тем, что именно считаете.
6. Типичные ошибки
Ошибка №1: путать глубину рекурсии и число вызовов.
Очень частая ситуация: студент видит, что программа «сделала миллион вызовов», и думает, что стек переполнился от этого. На самом деле стек переполняется от глубины, то есть от числа одновременно активных вызовов. А миллион вызовов можно сделать и в цикле, и стек при этом будет чувствовать себя спокойно.
Ошибка №2: считать, что «раз рекурсия работает на n=10, значит будет работать на n=1’000’000».
Рекурсия часто отлично проходит маленькие тесты, потому что стек большой по сравнению с учебными входами. Но рост глубины линейной рекурсии при росте входа — тоже линейный. Поэтому «проверил на маленьком» ничего не гарантирует: нужно заранее прикидывать максимальную глубину, хотя бы грубо.
Ошибка №3: складывать тяжёлые локальные объекты в рекурсивную функцию «просто потому что удобно».
Каждый уровень рекурсии приносит свой кадр стека. Если в кадре лежит что-то крупное, вы ускоряете переполнение стека. В рекурсивных функциях особенно полезно держать локальные переменные компактными и не создавать лишнего.
Ошибка №4: измерять «скорость рекурсии» только по ощущениям, не считая вызовы.
Рекурсивная функция может быть медленной не потому, что рекурсия «плохая», а потому что вы породили слишком много вызовов (как в наивном Fibonacci). Счётчик вызовов через int& — простой способ быстро понять масштаб происходящего, не трогая сложные инструменты измерения времени.
Ошибка №5: делать рекурсивный шаг без гарантий прогресса.
Это формально относится к корректности, но напрямую бьёт и по ограничениям: если шаг не приближает к базе, вы получаете бесконечную рекурсию, а значит почти гарантированный stack overflow. Самый практичный «анти-заговор» против этой ошибки — всегда задавать себе вопрос: «какой параметр уменьшается и когда он достигнет базы?»
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ