Обмеження рекурсії

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_counted(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. Профілюємо рекурсію: глибина та кількість викликів

Тут багато новачків плутаються, і це нормально: у мозку немає вбудованого «датчика рекурсивних дерев». Тож проговорімо все максимально чітко.

Глибина — це скільки викликів одночасно «живе» у стеку.
Загальна кількість викликів — це скільки разів функцію було викликано за весь час виконання.

І ці величини можуть поводитися дуже по‑різному.

Фібоначчі без оптимізацій: багато викликів за невеликої глибини

Ось «наївна» рекурсивна версія Фібоначчі:

#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) з лічильником, ви побачите приблизно таку картину (точні числа залежать від реалізації, але загальна тенденція незмінна):

n

fib(n)

І ось тут рекурсія починає програвати не тому, що «рекурсія погана», а тому, що сам алгоритм породжує надто багато повторних викликів. Ми свідомо не обговорюємо сьогодні техніки прискорення цього прикладу (інакше це вже була б окрема велика тема), але як попередження про вартість викликів це ідеальний кейс.

Практичний приклад: додаємо діагностику в 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: вимірювати «швидкість рекурсії» лише за відчуттями, не рахуючи виклики.
Рекурсивна функція може бути повільною не тому, що рекурсія «погана», а тому, що ви породили надто багато викликів (як у наївному обчисленні Фібоначчі). Лічильник викликів через int& — простий спосіб швидко зрозуміти масштаб того, що відбувається, не торкаючись складних інструментів вимірювання часу.

Помилка № 5: робити рекурсивний крок без гарантій прогресу.
Це формально стосується коректності, але безпосередньо впливає і на практичні обмеження: якщо крок не наближає до бази, ви отримуєте нескінченну рекурсію, а отже — майже гарантований stack overflow. Найпрактичніший запобіжник проти цієї помилки — завжди ставити собі запитання: «який параметр зменшується і коли він досягне бази?»