База й крок рекурсії: без бази програма падає

1. Вступ

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

Якщо коротко й по суті, рекурсія складається з двох частин.

Перша частина — базовий випадок (base case): ситуація, коли задача настільки мала, що відповідь очевидна і далі викликати себе вже не треба.

Друга частина — рекурсивний крок (recursive step): правило, як із поточної задачі зробити схожу, але меншу, а потім знову викликати функцію.

Схематично це можна уявити так:

flowchart TD
    A["Задача"] --> B{"Задача вже проста?"}
    B -->|так| C["Відповідь відразу (база)"]
    B -->|ні| D["Розвʼязати «трохи меншу» задачу рекурсивно (крок)"]
    D --> E["Побудувати відповідь для поточної задачі"]

2. Базовий випадок: точка, де ми перестаємо заглиблюватися

Базовий випадок — це не прикраса і не «ну гаразд, додамо if, щоб компілятор не сварився». Це центральна частина рекурсивної функції. Він відповідає на запитання: коли ми припиняємо самовиклики і починаємо повертатися назад по стеку викликів. У минулій лекції ви бачили, що кожен виклик створює кадр стека; базовий випадок — це місце, де нові кадри перестають створюватися.

Найпростіший приклад — сума чисел від 1 до n.

Приклад: сума від 1 до n — базовий випадок

Почнімо з визначення: sum_to(n) повертає 1 + 2 + ... + n. Тоді природно записати:

• якщо n == 0, сума дорівнює 0 (це база),
• інакше sum_to(n) = n + sum_to(n - 1) (це крок, про нього трохи пізніше).

Код базового випадку виглядає так:

int sum_to(int n) {
    if (n == 0) return 0;   // база: сума до 0 дорівнює 0
    return n + sum_to(n - 1);
}

Зверніть увагу: базова відповідь 0 тут не випадкова. Це так званий «нейтральний елемент» додавання: якщо ви щось додаєте, починати з нуля зручно.

Приклад: факторіал — базовий випадок

Факторіал n! — це 1 * 2 * 3 * ... * n. Логічно:

• 0! = 1 — це база,
• n! = n * (n - 1)! — крок.

long long factorial(int n) {
    if (n == 0) return 1;           // база: 0! = 1
    return n * factorial(n - 1);
}

І знову: 1 тут не просто тому, що «так у підручнику». Це нейтральний елемент множення. Якщо ви будуєте добуток, «порожній добуток» зручно вважати рівним 1.

База як «найменша цеглинка» задачі

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

Таблиця: як швидко підібрати базовий випадок

n

n == 0

0

n

n == 0

1

b

b == 0

a

i

i == s.size()

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

3. Рекурсивний крок: робимо задачу меншою і викликаємо себе

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

Зазвичай рекурсивний крок має два компоненти.

Перший компонент — отримати результат меншої задачі через самовиклик.

Другий компонент — «добудувати» результат для поточного рівня, наприклад додати n, помножити на n або вивести символ.

Шаблон рекурсивної функції

Нижче — корисний «скелет» мислення: це не магія, а просто звичний порядок дій.

ReturnType f(Args...) {
    if (base_condition) {
        return base_value;          // база
    }

    // зменшуємо задачу
    auto smaller = f(modified_args); // крок: самовиклик

    // добудовуємо відповідь
    return combine(smaller, current_state);
}

Іноді «добудова» відбувається до виклику, іноді — після. Сьогодні нам важливо інше: крок зобовʼязаний вести до бази.

Приклад: сума sum_to(n) — крок

int sum_to(int n) {
    if (n == 0) return 0;
    return n + sum_to(n - 1);   // крок: n зменшується на 1
}

Тут зменшення очевидне: було n, стало n-1. Рано чи пізно n дійде до нуля, і спрацює база.

Приклад: НСД (алгоритм Евкліда) — крок

НСД (gcd) зручно показати, бо тут рекурсія йде не «за одним числом», а за парою. База: коли b == 0, відповідь — a. Крок: замінити (a, b) на (b, a % b).

int gcd(int a, int b) {
    if (b == 0) return a;       // база
    return gcd(b, a % b);       // крок: b зменшується через остачу
}

Чому це «наближає до бази»? Тому що a % b за модулем менше за b (якщо b != 0), а отже друге число поступово зменшується і в якийсь момент стане 0.

4. Перевірка збіжності: чи дійдемо ми до бази

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

По-перше, чи досяжна база для всіх допустимих вхідних даних? Якщо ви вирішили, що базовий випадок n == 0, а користувач може передати -5, то куди ви зменшуватимете? У мінус нескінченність? Це не надто продуктивний карʼєрний план.

По-друге, чи зменшується задача на кожному кроці? Якщо ви випадково написали sum_to(n + 1), база ставатиме все далі, а не ближче.

По-третє, чи змінюється параметр узагалі? Рекурсивний крок виду return f(n); — це майже 100 % квиток у «переповнення стека».

Подивімося на дві «погані» версії, щоб навчитися розпізнавати їх із першого погляду.

Поганий приклад: параметр не змінюється

int sum_bad(int n) {
    if (n == 0) return 0;
    return n + sum_bad(n); // ПОМИЛКА: n не зменшується
}

Це нескінченна рекурсія. База є, але до неї ніхто не рухається.

Поганий приклад: база недосяжна

int sum_bad2(int n) {
    if (n == 0) return 0;
    return n + sum_bad2(n + 1); // ПОМИЛКА: n зростає, база все далі
}

Знову нескінченність: тепер база «втікає».

5. Чому без бази програма «падає»: стек не гумовий

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

Важливо розуміти одну психологічну пастку: рекурсія не «зациклюється», як while(true). У циклі у вас є один кадр стека, і ви нескінченно виконуєте тіло. У рекурсії ви створюєте нові кадри — багато, дуже багато, — і вони накопичуються.

Візуалізація: нескінченні сходи викликів

Уявімо таку функцію без бази:

int boom(int n) {
    return boom(n - 1);  // бази немає
}

Виклик boom(3) призводить до такого ланцюжка:

boom(3) викликає boom(2)
boom(2) викликає boom(1)
boom(1) викликає boom(0)
boom(0) викликає boom(-1)
...

І так далі, доки стек не переповниться.

Мінідемонстрація: «рекурсія без бази»

Нижче — приклад, який компілюється, але логічно приречений. Він корисний саме як ілюстрація:

int factorial_bad(int n) {
    // бази немає -> нескінченні виклики
    return n * factorial_bad(n - 1);
}

Навіть якщо ви викличете factorial_bad(1), далі функція перейде до factorial_bad(0), потім — до factorial_bad(-1) і так далі.

6. Практика: трасування й мінізастосунок

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

Невелике трасування: як працюють база й крок

Візьмемо sum_to(3):

int sum_to(int n) {
    if (n == 0) return 0;
    return n + sum_to(n - 1);
}

Трасування:

sum_to(3) = 3 + sum_to(2)
sum_to(2) = 2 + sum_to(1)
sum_to(1) = 1 + sum_to(0)
sum_to(0) = 0          <-- база

далі повернення:
sum_to(1) = 1 + 0 = 1
sum_to(2) = 2 + 1 = 3
sum_to(3) = 3 + 3 = 6

Це важливо: хоча рядок return n + sum_to(n - 1); записано «в один рядок», фактично спочатку треба обчислити sum_to(n - 1), а вже потім додати n.

Практичний приклад: рекурсивні команди в консольному застосунку

Щоб рекурсія не залишалася лише «одним факторіалом на полиці», оформімо її як невеликий набір команд у межах одного застосунку. Ми не будемо ускладнювати введення чи створювати «розумний парсер» рядків — достатньо простого меню на std::cin і кількох функцій. Сенс прикладу — побачити, що рекурсивна функція виглядає як звичайна функція й викликається так само.

Рекурсивні функції

long long factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
}

int sum_to(int n) {
    if (n == 0) return 0;
    return n + sum_to(n - 1);
}

main: просте меню

#include <iostream>

long long factorial(int n);
int sum_to(int n);

int main() {
    int cmd = 0;
    std::cin >> cmd;

    if (cmd == 1) {
        int n; std::cin >> n;
        std::cout << factorial(n) << '\n'; // наприклад: 120
    } else if (cmd == 2) {
        int n; std::cin >> n;
        std::cout << sum_to(n) << '\n';    // наприклад: 55
    } else {
        std::cout << "Невідома команда\n";  // невідома команда
    }
}

Тут важлива така думка: рекурсія — це не «особливий режим C++». Це просто функція, яка викликає себе.

7. Типові помилки

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

Помилка № 2: базовий випадок є, але він недосяжний.
Класична ситуація: база перевіряє n == 0, але крок робить n + 1 або взагалі не змінює n. Формально база є, але реального шляху до неї немає. Гарна звичка — подумки запитати себе: «через скільки кроків я точно потраплю до бази?» Якщо відповіді немає, значить, щось не так.

Помилка № 3: неправильна базова відповідь (наприклад, factorial(0) = 0).
Іноді база написана, крок теж зменшує задачу, рекурсія завершується, але результат неправильний. Зазвичай це означає, що базову відповідь обрано неправильно. Для суми база майже завжди 0, для добутку майже завжди 1. Якщо переплутати, помилки будуть тихими: програма не впаде, але видаватиме неправильні числа.

Помилка № 4: рекурсивний крок не зменшує задачу «у потрібній метриці».
Буває, що параметр змінюється, але не гарантує наближення до бази. Наприклад, ви зменшуєте n не на 1, а робите щось на кшталт n = n - 2, забувши, що n може бути непарним, а база перевіряється лише на n == 0. У підсумку для n == 1 рекурсія піде у відʼємні числа. У таких місцях важливо заздалегідь продумати допустимі вхідні значення й те, яка база справді покриває всі випадки.

Помилка № 5: рекурсивний виклик стоїть «не там», і ви не розумієте порядок виконання.
На вигляд рядок return n + f(n - 1); простий, але обчислюється у два етапи: спочатку f(n - 1), потім + n. Якщо ви намагаєтеся друкувати щось «у процесі», легко сплутати момент, коли буде виконано std::cout. Тут допомагає трасування «на пальцях»: випишіть 3–4 кроки викликів і повернень та подивіться, де ви насправді перебуваєте — до виклику чи вже на поверненні.