Call Stack это область памяти программы, используемая, чтобы управлять выполняющейся функцией и всеми последующими вызовами находящиеся в ожидании. Рисунок 3 отражает то понимание, которое принято называть "вызовом функции в ожидании". Из рисунка 3 видно, что экземпляр функции factorial с параметром 5 был первым с чего началось и последним, чем закончилось выполнение. Программа приостанавливает выполнение факториала (5) "ожидания" завершение вызова функции к factorial (4). Аналогично, программа приостанавливает выполнение factorial (4) ожидая завершение вызова функции к factorial (3). Этой серией вызовов вложенной функции управляют, используя стек вызовов. Рассмотрите следующую программу C++ в качестве примера.
| 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: | #include <iostream> #include <cstdlib> using namespace std; void method3(void) { cout << "Method 3" << endl; } void method2(void) { method3(); } void method1(void) { method2(); } int main(int argc, char* argv[]) { method1(); return EXIT_SUCCESS; } |
| Listing 3A program with nested function calls |
Продвижение посредством вызовов функции в листинге 3 демонстрирует, как программа использует стек вызовов, чтобы управлять вызовами функции в программе. Как во всех программах C++, первая функция, которая выполняется в программе в листинге 3, является функцией main. Рисунок 1 (a) представляет состояние стека вызовов после того, как функция main начинает выполнение, но до того как вызовет method1. Так как функция main является подпрограммой и в настоящий момент находится в выполнении, то она считает первую информацию - эта функция находится на вершине стека вызовов. Информация, которая включает локальные переменные функции, известна как запись активации.
Figure 1 The call stack during various points of Listing 3
Когда main функция вызывает method1, система времени выполнения вталкивает активацию записи method1 на вершину стека вызовов. Затем система времени выполнения останавливает выполнение функции main, ожидая завершение method1. Рисунок 1 (b) представляет состояние стека вызовов в этой точке программы. Затем функция method1 вызывает method2. Системное выполнение пауз времени выполнения method1 вталкивает активацию записи method2 на вершину стека. Это состояние стека вызовов в программе отражено на рисунке 1 (c). После завершение функции method2 вызывает method3, стек вызовов показан на рисунок 1 (d).
В этой точке, во время выполнения программы, вызовы функции содержат четыре «глубоких» уровня. Программа выполняет функции в обратном порядке, т.е.: method3, с функциями method2, method1, и main и все завершается. После выполнения программы функции method3, система времени выполнения выталкивает активацию записи для method3 из вершины стека. И выполнение method2 возобновляется. Стек вызовов вернувшись был бы как на рисунке 1 (c). Когда выполнение method2 завершается, система времени выполнения выталкивает ее из стека также, представляя стек вызовов в состояние, представленному на рисунке 1 (b). Как вложенные функции в конце программы, стек вызовов становится короче и короче. В конечном счете, функция main и система времени выполнения выталкивают ее запись активации из стека, заканчивая выполнение программы.
Стек вызовов работает с рекурсивными функциями тем же самым способом. Повторно, давайте отследим стек вызовов, поскольку это управляет рекурсивными вызовами функции factorial. Выполнение программы начинается с функции main. Функция main вызывает функцию factorial с параметром 5. Системные run-time выполнения должны были выполнить факториал с параметром 5 сверху стека. Стек вызовов, в этой точке напоминает рисунок 2.
Рисунок 2 стек вызовов, во время исполнения factorial (5)
Вызов функции factorial (5), как мы знаем из вышеприведенных исследований, делает вызов в factorial (4), который в свою очередь делает вызов в factorial (3), и так далее пока factorial (0) не начнет выполнение. В этой точке стек вызовов имеет вид рисунка 3.
Рисунок 3 стек вызовов, во время выполнения factorial (0)
Функция factorial (0) является base case рекурсии. Когда этот экземпляр функции завершается, оно возвращает значение 1 в запись активации которой находится ниже него. Затем система времени выполнения выталкивает запись активации для factorial (0) из стека и возобновляет выполнение с функцию factorial (1). Вложенные функции продолжают "раскручиваться" этим способом, передавая назад значения к их функциям вызова, пока функция main не завершит всю работу, т.е. программа завершится.
Отладчик позволяет программистам осматривать стек вызовов программы. Эта возможность может оказаться неоценимой при попытках отладить рекурсивную функцию. Рисунок 4 показывает окно стека вызовов в качестве примера.
Figure 4 Microsoft Visual C++ call stack window