Стек викликів

1. Модель виконання та стек викликів

Коли ви пишете doSomething();, здається, що компʼютер просто «перестрибнув» в інше місце програми, виконав потрібну роботу й повернувся. Але як саме він повертається? Звідки він «памʼятає», куди потрібно повернутися? І чому локальні змінні всередині функції зникають після return, ніби їх «вимкнули з реальності»?

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

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

Стек викликів: стос тарілок і правило LIFO

Слово «стек» (stack) буквально означає «стос». Уявіть, що кожен виклик функції кладе на стіл тарілку з папірцем: «я — виклик функції foo(), ось мої локальні змінні, ось мої параметри, а ось адреса, куди треба повернутися». Коли функція завершується, цю тарілку прибирають.

Важливо, що прибирають саме останню покладену тарілку. Це правило називається LIFO: Last In, First Out — «останнім увійшов, першим вийшов».

Це правило ідеально підходить для викликів функцій: якщо main() викликав f(), а f() викликав g(), то логічно, що спочатку має завершитися g(), потім продовжиться f(), і лише після цього — main().

Кадр стека: що зберігається «на тарілці»

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

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

Зручно уявити кадр стека як таблицю:

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

Міні-демонстрація: порядок входу й виходу з функцій

Зараз ми проведемо найчесніший експеримент: просто надрукуємо start/end і подивимося, у якому порядку вони зʼявляються. Приклад невеликий, але він чудово показує правило LIFO.

#include <iostream>

void h() {
    std::cout << "h: start\n"; // h: start
    std::cout << "h: end\n";   // h: end
}

void g() {
    std::cout << "g: start\n"; // g: start
    h();
    std::cout << "g: end\n";   // g: end
}

void f() {
    std::cout << "f: start\n"; // f: start
    g();
    std::cout << "f: end\n";   // f: end
}

int main() {
    f();
}

Якщо запустити програму, ви побачите приблизно таке:

f: start
g: start
h: start
h: end
g: end
f: end

Це і є «стос тарілок» у дії: поки h() не завершить роботу, g() «стоїть на паузі» саме на рядку h();, а f() — на рядку g();.

Точка повернення: чому функція, що викликає, «завмирає» на місці виклику

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

Коли виконується рядок:

int b = inner(a + 1);

функція, що викликає (outer), має памʼятати, що після завершення inner(...) потрібно продовжити виконання решти інструкції: присвоїти результат змінній b, а потім виконати наступні рядки. Саме тому в кадрі стека зберігається точка повернення.

Подивімося на приклад:

#include <iostream>

int inner(int x) {
    std::cout << "inner: x=" << x << '\n'; // inner: x=11
    return x * 2;
}

int outer(int a) {
    std::cout << "outer: before\n";        // outer: before
    int b = inner(a + 1);
    std::cout << "outer: after\n";         // outer: after
    return b + 3;
}

int main() {
    std::cout << outer(10) << '\n';        // 25
}

Тут outer буквально «зупиняється» на виклику inner, чекає return, отримує значення й лише тоді продовжує роботу.

Життєвий цикл локальних змінних: вони існують рівно до кінця виклику

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

У термінах стандарту C++ це повʼязано з поняттям automatic storage duration (автоматична тривалість зберігання) — так описують типові локальні змінні, які живуть у межах блока й знищуються під час виходу з нього.

Приклад:

#include <iostream>

int add10(int x) {
    int y = x + 10; // локальна змінна
    return y;
}

int main() {
    std::cout << add10(1) << '\n'; // 11
    std::cout << add10(5) << '\n'; // 15
}

Тут немає «памʼяті між викликами»: y щоразу створюється заново під час входу в add10(). Вона не «накопичується», не «старіє» й не «згадує минуле життя».

Два виклики однієї функції — це два різні світи локальних змінних

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

Зробімо маленький трюк: виведемо значення локальної змінної. Ми ще не вивчали вказівники достатньо глибоко, тож не заглиблюватимемося в адреси — саму логіку добре видно і без цього.

#include <iostream>

void demo(int x) {
    int local = x * 10;
    std::cout << "local=" << local << '\n'; // local=20 (потім local=50)
}

int main() {
    demo(2);
    demo(5);
}

Навіть якщо не дивитися на адреси в памʼяті, ідея та сама: кожен виклик створює власний local.

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

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

Зробимо дві невеликі функції trace_enter і trace_exit, а глибину зберігатимемо в змінній depth, яку передаємо за посиланням, щоб зміни бачили всі учасники ланцюжка викликів.

#include <iostream>
#include <string>

void trace_enter(const std::string& name, int& depth) {
    for (int i = 0; i < depth; ++i) std::cout << "  ";
    std::cout << "-> " << name << '\n';
    ++depth;
}

void trace_exit(const std::string& name, int& depth) {
    --depth;
    for (int i = 0; i < depth; ++i) std::cout << "  ";
    std::cout << "<- " << name << '\n';
}

Зверніть увагу: depth — це не «частина стека», а лише наш навчальний ліхтарик. Ми підсвічуємо те, що й так відбувається всередині програми.

3. Міні-проєкт: консольний список справ і лаконічний main

Тепер обʼєднаємо приклади в невеликий застосунок, який легко розширювати. Нічого надскладного: просто список рядків (std::vector<std::string>) і команди add/list/exit. Головна мета — побачити, як виклики функцій «живуть» у стеці та чому main() краще залишати лаконічним.

Каркас застосунку

Почнемо з каркаса:

#include <iostream>
#include <string>
#include <vector>

void run_app() {
    std::vector<std::string> tasks;
    std::cout << "TodoApp started\n"; // TodoApp started
}

int main() {
    run_app();
}

Поки що тут немає нічого особливо цікавого, але це хороший каркас: main() не містить основної логіки, а просто передає керування run_app().

Додаємо команди й дивимося на стек через трасування

Тепер зробимо функції для показу меню, читання команди та її обробки. І додамо трасування, щоб побачити, як run_app() викликає інші функції.

#include <iostream>
#include <string>

void trace_enter(const std::string& name, int& depth) {
    for (int i = 0; i < depth; ++i) std::cout << "  ";
    std::cout << "-> " << name << '\n';
    ++depth;
}

void trace_exit(const std::string& name, int& depth) {
    --depth;
    for (int i = 0; i < depth; ++i) std::cout << "  ";
    std::cout << "<- " << name << '\n';
}

void print_menu(int& depth) {
    trace_enter("print_menu", depth);
    std::cout << "Commands: add, list, exit\n";
    trace_exit("print_menu", depth);
}

std::string read_command(int& depth) {
    trace_enter("read_command", depth);
    std::string cmd;
    std::getline(std::cin, cmd);
    trace_exit("read_command", depth);
    return cmd;
}

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

Зʼєднуємо все в run_app і спостерігаємо кадри стека

Зараз ми зберемо ланцюжок: main() → run_app() → print_menu() → read_command(). Навіть без рекурсії стек уже працює й уже має значення.

#include <iostream>
#include <string>
#include <vector>

void trace_enter(const std::string& name, int& depth) {
    for (int i = 0; i < depth; ++i) std::cout << "  ";
    std::cout << "-> " << name << '\n';
    ++depth;
}

void trace_exit(const std::string& name, int& depth) {
    --depth;
    for (int i = 0; i < depth; ++i) std::cout << "  ";
    std::cout << "<- " << name << '\n';
}

void print_menu(int& depth) {
    trace_enter("print_menu", depth);
    std::cout << "Commands: add, list, exit\n"; // Commands: add, list, exit
    trace_exit("print_menu", depth);
}

std::string read_command(int& depth) {
    trace_enter("read_command", depth);
    std::string cmd;
    std::getline(std::cin, cmd);
    trace_exit("read_command", depth);
    return cmd;
}

void run_app() {
    int depth = 0;
    trace_enter("run_app", depth);

    std::vector<std::string> tasks;

    print_menu(depth);
    std::cout << "Enter command: ";            // Enter command:
    std::string cmd = read_command(depth);

    std::cout << "You typed: " << cmd << '\n'; // наприклад: You typed: add

    trace_exit("run_app", depth);
}

int main() {
    run_app();
}

Якщо ви введете add, то побачите приблизно таку картину:

-> run_app
  -> print_menu
Commands: add, list, exit
  <- print_menu
Enter command:   -> read_command
  <- read_command
You typed: add
<- run_app

Це візуалізація стека: поки ми перебуваємо в read_command(), попередні функції не зникають — вони «чекають», доки виконання повернеться до їхньої точки повернення.

4. Що насправді означає return

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

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

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

5. Візуальна схема стека під час вкладених викликів

Щоб остаточно закріпити матеріал, намалюємо просту схему. Йдеться не про «точне побайтне розташування в памʼяті», а про сенс.

flowchart TD
    A["main()"] --> B["run_app()"]
    B --> C["print_menu()"]
    B --> D["read_command()"]

І в момент, коли ми перебуваємо всередині read_command(), «стос» виглядає приблизно так:

[ top ]
read_command frame
run_app frame
main frame
[ bottom ]

Коли read_command() виконує return, її кадр знімається, і ми знову «перебуваємо» в run_app().

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

Помилка № 1: очікувати, що функція, яка викликає, продовжить виконуватися «паралельно».
Іноді здається, що run_app() може «встигнути зробити ще щось», поки виконується read_command(). В однопотоковому коді це не так: функція, яка викликала іншу, стоїть на паузі до return. Якщо тримати в голові модель «одна доріжка виконання» і «точка повернення», плутанини стає менше.

Помилка № 2: вважати, що локальні змінні «памʼятають» значення між викликами.
Локальна змінна належить конкретному кадру стека. Новий виклик — новий кадр — нові локальні змінні. Якщо вам потрібно зберігати стан між викликами, це має бути змінна «вище» — наприклад, у run_app() — або параметр чи контейнер, який передається між функціями.

Помилка № 3: плутати порядок виклику та порядок завершення.
Виклики йдуть «углиб», а завершення — «назовні». Тому в ланцюжку main → run_app → read_command спочатку завершиться read_command, потім продовжиться run_app, і лише після цього завершиться main. Це правило LIFO — «останнім увійшов, першим вийшов» — корисно повторювати як заклинання, тільки без містики.

Помилка № 4: сприймати return як «просто вихід», не розуміючи наслідків.
Ранній return часто робить код простішим, але важливо памʼятати: він завершує функцію прямо зараз, кадр знімається, локальні змінні знищуються, а функція, що викликає, продовжує виконання. Якщо ви до return не оновили потрібний стан, наприклад не записали результат у контейнер, який живе вище, то потім уже буде запізно.

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