рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

The Call Stack

The Call Stack - раздел Философия, Recursive factorials The Call Stack Is An Area Of A Program's Memory Used To Manage The Cur...

The call stack is an area of a program's memory used to manage the currently executing function and all pending function calls. Figure 3 lends some insight into what is meant by a "pending function call." Looking back at figure 3, we can see that even though the instance of function factorial with the parameter 5 was the first to begin execution, it is the last to finish execution. The program pauses the execution of factorial(5) "pending" the completion of the function call to factorial(4). Likewise, the program pauses the execution of factorial(4) pending the completion of the function call to factorial(3). This series of nested function calls is managed using the call stack. Consider the following example C++ program.

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

Stepping through the function calls in Listing 3 demonstrates how a program uses the call stack to manage the function calls in a program. As in all C++ programs, the first function that executes in the program in Listing 3 is function main. Figure 1(a) represents the state of the call stack after function main begins execution, but before it calls method1. Since function main is the routine currently in execution, the information needed to run this function sits on the top of the call stack. This information, which includes among other things the local variables of the function, is known as an activation record.


Figure 1 The call stack during various points of Listing 3

When main calls function method1, the run-time system pushes an activation record for method1 onto the top of the call stack. The run-time system then halts execution of function main, pending the completion of method1. At this point in the program, Figure 1(b) represents the state of the call stack. Function method1 then immediately calls method2. The run-time system pauses execution of method1 and pushes an activation record for method2 onto the top of the stack. This state of the call stack at this point in the program corresponds to Figure 1(c). After function method2 calls method3, the call stack resembles Figure 1(d).

At this point during the execution of the program, function calls are nested four levels deep. The program currently is executing function method3, with functions method2, method1, and main all suspended. After the program finishes execution of function method3, the run-time system pops off the activation record for method3 from the top of the stack. Execution of method2 then resumes. The call stack would then again resemble Figure 1(c). When execution of method2 completes, the run-time system pops it off the stack also, putting the call stack back to the state represented in Figure 1(b). As the nested functions in the program end, the call stack grows shorter and shorter. Eventually, function main finishes and the run-time system pops its activation record off the stack, ending the execution of the program.

The call stack operates in the same manner when dealing with recursive functions as it does with regular functions. Revisiting the factorial example, let's trace the call stack as it manages the recursive calls to function factorial. The program execution begins with function main. Function main then calls function factorial with the parameter 5. The run-time system pushes the information needed to execute factorial with the parameter 5 on top of the stack. The call stack, at this point resembles Figure 2.


Figure 2 The call stack while factorial(5) executes

The function call factorial(5), as we know from earlier examination, makes a call to factorial(4), which makes a call to factorial(3), and so on until factorial(0) begins execution. At this point, the call stack resembles Figure 3.


Figure 3 The call stack while factorial(0) executes

Function factorial(0) is the base case of the recursion. When this instance of the function finishes, it returns the value 1 to the function whose activation record sits below it. Then the run-time system pops the activation record for factorial(0) off the stack and resumes execution with function factorial(1). The nested functions continue to "unwind" in this manner, passing values back to their calling functions, until function main completes and the program terminates.

Debuggers often provide a feature that allows programmers to inspect the call stack of a program. This feature can prove invaluable when trying to debug a recursive function. Figure 4 shows an example call-stack window from Microsoft Visual C++.

Figure 4 Microsoft Visual C++ call stack window

– Конец работы –

Эта тема принадлежит разделу:

Recursive factorials

Example contains the output of the factorial program after the addition of the output statements to function factorial factorial begin... The output in Example shows that the program first calls function factorial... Problem Solving with Recursion Divide and...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: The Call Stack

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Removing Recursion
Recursion comes with a price: the run time system has to maintain a complicated call stack, on top of having to perform the usual evaluations contained in the function. Often, we can eliminate recu

Divide and Conquer
Divide and conquer is a problem solving technique that utilizes recursion to solve a problem by "dividing" the problem into smaller and smaller sub-problems. The base case of the r

Backtracking. The Concept
Backtracking is a problem solving technique that involves examining all possibilities in the search for a solution. An example of backtracking can be seen in the process of finding the solution to

The Problem
A classic problem that we can solve using backtracking is the Eight Queens problem. This difficult problem deals with placing eight queens on a chessboard such that no two queens are attacking each

The Solution
To solve the Eight Queens problem, we use a backtracking algorithm. The algorithm involves placing queens, column by column, onto the chessboard. The algorithm terminates when it places all eight q

The Call Stack
Call Stack это область памяти программы, используемая, чтобы управлять выполняющейся функцией и всеми последующими вызовами находящиеся в ожидании. Рисунок 3 отражает то понимание, которое принято

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

Отслеживание в обратном порядке. Понятие
Отслеживание в обратном порядке является проблемой, решая метод, который включает исследование всех возможностей в поиске решения. Пример отслеживания в обратном порядке может быть замечен в процес

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

Решение
Чтобы решить проблему Восьми Королев, мы используем алгоритм отслеживания в обратном порядке. Алгоритм включает размещения королев, столбец за столбцом, на шахматную доску. Алгоритм завершается, ко

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги