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

1. Вступ

Якщо ви вже пробували рекурсію, то могли помітити дивну річ: код виходить красивим і «математичним». Але щойно вхідні дані стають великими, десь удалині ніби починає кричати стек, а програма інколи падає так упевнено, наче все життя до цього готувалася. Хвостова рекурсія — це спосіб записати рекурсивний алгоритм так, щоб компілятор міг (але не зобовʼязаний) перетворити його на щось ближче до циклу й не накопичувати кадри стека.

Щоб не заплутатися, одразу домовимося про терміни: «хвостова рекурсія» — це форма запису, а «оптимізація хвостового виклику» — можлива дія компілятора. Ці дві речі часто змішують між собою, а потім дивуються: «Я ж написав хвостову рекурсію, чому вона все одно переповнила стек?»

Як розпізнати хвостовий виклик у коді

Хороший спосіб почати — навчитися розпізнавати хвостову рекурсію на око, так само як ви розпізнаєте if і for. Інтуїтивно хвостова рекурсія — це ситуація, коли функція викликає сама себе, і після цього виклику їй уже нічого робити: вона одразу повертає результат рекурсивного виклику. Тобто рекурсивний виклик — остання дія функції.

Подивіться на два схожі фрагменти:

int sum_not_tail(int n) {
    if (n == 0) return 0;
    return n + sum_not_tail(n - 1); // не хвостова: після виклику ще є '+'
}

int sum_tail_impl(int n, int acc) {
    if (n == 0) return acc;
    return sum_tail_impl(n - 1, acc + n); // хвостова: return одразу повертає результат виклику
}

У першому варіанті компілятор (і ви також) бачить: «Я маю дочекатися результату sum_not_tail(n - 1), а потім ще додати n». Отже, робота відкладається «на повернення», і стек тут справді працює як «памʼять очікування».

У другому варіанті робота не відкладається: ми обчислюємо acc + n до виклику, а потім просто передаємо керування далі. Теоретично це вже нагадує цикл: «поки n != 0, оновлюй акумулятор і зменшуй n».

Акумулятор і нейтральний елемент

Коли люди вперше бачать акумулятор (acc), реакція часто така: «О, ніби ми перехитрили рекурсію і потай зробили цикл». Певною мірою так і є, тільки це не обман, а звичайний спосіб перевести обчислення з режиму «доробляємо на поверненні» в режим «робимо заздалегідь».

Акумулятор — це параметр, у якому ми зберігаємо уже накопичений результат, щоб у базовому випадку повернути його повністю, без додаткових обчислень після повернення.

Корисно запамʼятати нейтральні елементи:

0

x + 0 = x

1

x * 1 = x

Тому хвостовий факторіал зазвичай виглядає так:

long long fact_tail_impl(int n, long long acc) {
    if (n == 0) return acc;
    return fact_tail_impl(n - 1, acc * n);
}

long long fact_tail(int n) {
    return fact_tail_impl(n, 1);
}

Зверніть увагу на зручний стиль: ми робимо маленьку «внутрішню» функцію *_impl, а назовні даємо зручнішу сигнатуру fact_tail(n). Це робить API дружнішим: користувач функції не зобовʼязаний знати, що таке акумулятор, щоб обчислити факторіал.

2. Хвостова рекурсія, стек і TCO

Чому хвостова форма сама собою не рятує стек

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

Щоб побачити це наочно, можна додати налагоджувальний вивід, який показує глибину:

#include <iostream>

int sum_tail_dbg(int n, int acc, int depth) {
    for (int i = 0; i < depth; ++i) std::cout << "  ";
    std::cout << "n=" << n << " acc=" << acc << '\n';

    if (n == 0) return acc;
    return sum_tail_dbg(n - 1, acc + n, depth + 1);
}

int main() {
    std::cout << sum_tail_dbg(3, 0, 0) << '\n';
}
// n=3 acc=0
//   n=2 acc=3
//     n=1 acc=5
//       n=0 acc=6
// 6

Якщо компілятор не виконав оптимізацію хвостового виклику, ми побачимо реальні сходинки глибини: кожен наступний виклик буде глибшим за попередній.

І ось тут зʼявляється головна думка: хвостова рекурсія — це можливість для компілятора, а не обовʼязок. Стандарт C++ не обіцяє, що хвостову рекурсію буде перетворено на цикл. Ваша програма має бути коректною і без цієї оптимізації.

Що таке оптимізація хвостового виклику

Ідея оптимізації хвостового виклику, яку часто називають Tail Call Optimization (TCO), така: якщо функція наприкінці робить return f(...);, то замість того, щоб створювати новий кадр стека для f(...), можна перевикористати поточний кадр, оновити параметри й «стрибнути» на початок функції, ніби це був цикл.

Це можна уявити такою схемою:

flowchart TD
    A["sum_tail_impl(n, acc)"] -->|якщо n==0| B["return acc"]
    A -->|інакше| C["готуємо next: (n-1, acc+n)"]
    C --> D["замість нового кадру перезаписуємо параметри в поточному"]
    D --> A

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

Але ключове слово тут — якщо.

3. Чому оптимізація може не спрацювати

Скажімо відверто: дуже хочеться вірити, що компілятор — добрий чарівник, який побачить хвостову рекурсію і скаже: «О, та це ж цикл у костюмі рекурсії!» — і врятує стек. Іноді так і стається. Але «іноді» — не те слово, на якому варто будувати надійність програми.

По-перше, компілятор узагалі не зобовʼязаний оптимізувати. Оптимізації — це його право. У різних режимах збирання, з різними прапорцями та налаштуваннями він може ухвалювати різні рішення. І так, інколи найприкріший сценарій виглядає так: «У маленькому тесті все працює, а на реальних вхідних даних — переповнення стека».

По-друге, компілятору може бути невигідно викидати кадри стека, бо стек потрібен не лише для виконання, а й для діагностики. Навіть без повноцінного дебагера людям подобається бачити стек викликів у повідомленнях про аварії. А якщо компілятор агресивно згорнув рекурсію в цикл, ланцюжок викликів зникає — і налагоджувати програму може стати складніше.

По-третє, не кожна рекурсія, яка здається хвостовою, справді є хвостовою з погляду компілятора. Іноді ви додаєте маленьку «невинну» деталь — і хвостовість зникає. Наприклад:

int almost_tail(int n, int acc) {
    if (n == 0) return acc;
    int res = almost_tail(n - 1, acc + n);
    return res; // виглядає хвостовою, але тут є зайві кроки й змінна
}

Для людини це «майже те саме», але для компілятора це вже інша історія: зʼявилася локальна змінна, зʼявився додатковий крок після виклику, і залежно від оптимізатора цього може вистачити, щоб не застосовувати перетворення.

По-четверте, навіть якщо виклик стоїть останнім, навколо нього можуть бути деталі, які заважають згортанню: додаткові перевірки, особливі угоди про виклик на платформі, потреба зберегти певні значення для коректного повернення. Ми сьогодні не заглиблюємося в низькорівневу механіку, але практичний висновок простий: розраховувати на оптимізацію не можна.

4. Як вручну замінити хвостову рекурсію на цикл

Щоб не покладатися на магію, корисно тримати напоготові «план Б»: якщо хвостова рекурсія потрібна лише для зручного запису, ви маєте розуміти, який вигляд має еквівалентний цикл.

Візьмемо суму від 1 до n.

Хвостова рекурсія:

int sum_tail_impl(int n, int acc) {
    if (n == 0) return acc;
    return sum_tail_impl(n - 1, acc + n);
}

Еквівалентний цикл (за змістом):

int sum_loop(int n) {
    int acc = 0;
    while (n != 0) {
        acc += n;
        --n;
    }
    return acc;
}

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

5. Практика: TextTools — сума цифр у рядку

Тепер акуратно привʼяжемо тему до нашого навчального мінізастосунку. Нехай це буде проста консольна утиліта TextTools, яка читає команду і рядок, а потім виконує операцію. Раніше ми вже робили такі застосунки, щоб закріпити введення рядків, умови та функції; сьогодні додамо хвостову рекурсію як одну з реалізацій.

Ідея команди проста: порахувати суму цифр у рядку. Наприклад, "a1b2c3" → 6. Це зручно, бо ми тренуємо і роботу з рядками, і рекурсію, і акуратне використання індексів.

Хвостова рекурсія для суми цифр у рядку

Зробимо хвостову рекурсію з індексом i та акумулятором acc. Нам вистачить лише std::string, size(), індексації та умов.

#include <string>

int sum_digits_tail_impl(const std::string& s, std::size_t i, int acc) {
    if (i == s.size()) return acc;

    char c = s[i];
    if (c >= '0' && c <= '9') acc += (c - '0');

    return sum_digits_tail_impl(s, i + 1, acc);
}

Зверніть увагу: рекурсивний виклик справді є останньою дією. Усі обчислення — перевірка символу й оновлення acc — виконано до return ....

Назовні дамо «чисту» функцію без акумулятора:

int sum_digits_tail(const std::string& s) {
    return sum_digits_tail_impl(s, 0, 0);
}

Циклічна версія як «надійний дублер»

Щоб застосунок не залежав від оптимізацій компілятора, додамо і цикл. Він буде корисний як еталон: якщо рекурсивна версія працює інакше, то помилка в логіці, а не в тому, що «компілятор знову щось не те зробив».

#include <string>

int sum_digits_loop(const std::string& s) {
    int acc = 0;
    for (std::size_t i = 0; i < s.size(); ++i) {
        char c = s[i];
        if (c >= '0' && c <= '9') acc += (c - '0');
    }
    return acc;
}

Міні-CLI: обʼєднуємо команди в один main

Зараз зберемо маленький main, який підтримує дві команди: "sumdigits" (цикл) і "sumdigits_tail" (хвостова рекурсія). Ми спеціально тримаємо код невеликим, щоб він лишався читабельним, а не перетворювався на «проєкт для диплома».

#include <iostream>
#include <string>

int sum_digits_loop(const std::string& s);
int sum_digits_tail(const std::string& s);

int main() {
    std::string cmd;
    std::getline(std::cin, cmd);

    std::string line;
    std::getline(std::cin, line);

    if (cmd == "sumdigits") {
        std::cout << sum_digits_loop(line) << '\n';
    } else if (cmd == "sumdigits_tail") {
        std::cout << sum_digits_tail(line) << '\n';
    } else {
        std::cout << "Невідома команда\n";
    }
}

Приклад використання (ввід користувача з двох рядків):

sumdigits_tail
a1b2c3

Вивід:

6

Якщо ви зараз запитаєте: «А навіщо дві версії?» — відповідь дуже практична. Хвостова рекурсія — класна техніка, але цикл передбачуваніший щодо памʼяті, і ви завжди можете повернутися до нього як до «залізобетонної» реалізації.

6. Коли хвостова рекурсія корисна як стиль

Хвостову рекурсію часто цінують не лише за потенційну оптимізацію, а й за те, що вона дисциплінує алгоритм: ви явно формулюєте, що саме є поточним станом обчислення. Акумулятор — це не «додаткова змінна», а дуже чесний спосіб сказати: «Ось усе, що мені потрібно знати про прогрес».

Наприклад, якщо ви хочете не суму цифр, а «суму цифр до першого нецифрового символу», вам потрібно додати правило зупинки. У хвостовій версії це виглядає природно: ви просто змінюєте базову умову.

int sum_prefix_digits_tail_impl(const std::string& s, std::size_t i, int acc) {
    if (i == s.size()) return acc;

    char c = s[i];
    if (c < '0' || c > '9') return acc;

    return sum_prefix_digits_tail_impl(s, i + 1, acc + (c - '0'));
}

Це, як і раніше, хвостова форма, і ви все ще не відкладаєте роботу «на повернення».

7. Типові помилки під час хвостової рекурсії

Помилка № 1: вважати хвостову рекурсію «гарантією того, що стек не переповниться».
Хвостова рекурсія — це форма запису, яка може дати компілятору шанс прибрати зростання стека. Але якщо компілятор цього не зробив, глибина зростатиме як зазвичай. Тому коректність програми не можна будувати на сподіванні «ну компілятор же розумний».

Помилка № 2: випадково зламати хвостовість і не помітити цього.
Найтиповіша поломка — поставити обчислення після рекурсивного виклику, на кшталт return f(...) + 1;. Іноді проблема менш очевидна: ви додаєте локальну змінну й післяобробку результату, і це вже не чистий хвостовий виклик. У таких місцях корисно буквально ставити собі запитання: «Після рекурсивного виклику в мене лишається хоч якась робота?»

Помилка № 3: неправильне початкове значення акумулятора.
Якщо ви рахуєте суму, стартове значення acc має бути 0, якщо добуток — 1. Помилка здається кумедною, але трапляється дуже часто, бо мозок новачка ще не автоматизував ідею нейтрального елемента. Підсумок — формально коректна рекурсія, яка повертає неправильну відповідь, і це прикріше, ніж помилка компіляції.

Помилка № 4: акумулятор оновлюють не там.
Іноді пишуть хвостову рекурсію, але оновлення стану роблять не перед викликом, а після нього, намагаючись зберегти стару структуру «на поверненні». Тоді хвостовість втрачається, а разом із нею — і сенс акумулятора. Хороша ознака правильного коду — усі зміни стану (acc, n, i) відбуваються до return recursion(...).

Помилка № 5: рекурсивний крок не наближає до базового випадку, але ви сподіваєтеся на оптимізацію.
Якщо рекурсивний крок не наближає до базового випадку (наприклад, ви забули i + 1 або n - 1), програма піде в нескінченну рекурсію. Жодна оптимізація не врятує алгоритм, який не зупиняється: у найкращому разі ви отримаєте нескінченний цикл, у найгіршому — падіння. Спочатку логіка зупинки, потім усе інше.

1

Опитування

Рекурсія та стек викликів, рівень 16, лекція 4

Недоступний

Рекурсія та стек викликів

Рекурсія та стек викликів

Відкрити