Стек вызовов

Стек вызовов

Кадры и стек вызовов, работа на пути вниз и на пути обратно, передача больших данных по ссылке и то, насколько глубокой может быть рекурсия.

Теория

Урок 3 из 7

7 мин чтения

Вопросов: 4

Когда fact(3) вызвала fact(2), она не исчезла — она остановилась недоделанной и ждала ответа. Этот урок о том, где ждут такие остановленные вызовы и что можно сделать в момент, когда каждый из них просыпается.

У каждого вызова свой кадр

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

Отсюда два следствия:

У каждого вызова своя копия переменных. n внутри fact(2) и n внутри fact(3) — разные коробки, и изменение одной никогда не трогает другую.
Вызовы заканчиваются в обратном порядке: последний вызванный возвращается первым.

Работа на пути вниз и на пути обратно

Рекурсивный вызов делит функцию на две половины: код до вызова выполняется, пока вызовы уходят глубже, а код после — пока они возвращаются, в обратном порядке. Пройдите по шагам функцию, которая печатает в обоих местах:

Работа до вызова и работа после него

C++

1#include <bits/stdc++.h>

2using namespace std;

4void show(int x) {

5 if (x == 0) {

6 return;

7 }

8 cout << x << " ";

9 show(x - 1);

10 cout << x << " ";

11}

13int main() {

14 ios_base::sync_with_stdio(false);

15 cin.tie(NULL);

17 show(3);

18 return 0;

19}

Начинаем в main()

строка 13

Пока ничего не вызвано.

стек вызовов

main()

x—

depth0

1 / 20

У каждого вызова свой кадр

Работа на пути вниз и на пути обратно

Практика: Стек вызовов

Большое передавайте по ссылке

Насколько глубоко можно зайти?

Проверьте себя