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

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

The Call Stack

The Call Stack - раздел Философия, Recursive factorials Call Stack Это Область Памяти Программы, Используемая, Чтобы Управлять Выполн...

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

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

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

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

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

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

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

The Call Stack
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 "pend

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

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

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

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

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

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