На этом шаге рассмотрим понятие стека вызовов.
Во внутренней работе компьютера используется стек, называемый стеком вызовов. Давайте посмотрим, как он работает. Предположим, имеется простая процедура:
procedure greet(name:string); begin writeln('Привет, ',name,'!'); greet2(name); bye(); end;
Эта процедура приветствует вас, после чего вызывает две другие процедуры.
Вот эти две процедуры:
procedure greet2(name:string); begin writeln('Как твои дела, ',name,'?'); end; procedure bye(); begin write('До встречи...') end;
Разберемся, что происходит при вызове процедуры. Предположим, в программе используется вызов greet ("Мария"). Сначала ваш компьютер выделяет блок памяти для этого вызова процедуры.
Затем эта память используется. Переменной name присваивается значение "Мария"; оно должно быть сохранено в памяти.
Каждый раз, когда вы вызываете процедуру, компьютер сохраняет в памяти значения всех переменных для этого вызова. Далее выводится приветствие Привет, Мария!, после чего следует второй вызов greet2( "Мария"). И снова компьютер выделяет блок памяти для вызова процедуры.
Компьютер объединяет эти блоки в стек. Второй блок создается над первым. Вы выводите сообщение Как твои дела, Мария?, после чего возвращаете управление из вызова процедуры. Когда это происходит, блок на вершине стека извлекается из него.
Теперь верхний блок в стеке относится к процедуре greet; это означает, что вы вернулись к процедуре greet. При вызове процедуры greet2 процедура greet еще не была завершена.
Когда вы вызываете подпрограмму из другой подпрограммы, вызывающая подпрограмма приостанавливается в частично завершенном состоянии. Все значения переменных этой подпрограммы остаются в памяти.
А когда выполнение процедуры greet2 будет завершено, вы вернетесь к процедуре greet и продолжите ее выполнение с того места, где оно прервалось. Вызывается процедура Ьуе.
Блок для этой процедуры добавляется на вершину стека. Далее выводится сообщение До встречи... с выходом из вызова процедуры.
Управление снова возвращается процедуре greet. Делать больше нечего, так что управление возвращается и из процедуры greet. Этот стек, в котором сохранялись переменные разных подпрограмм, называется стеком вызовов.
Архив с примером на языке С++ можно взять здесь.
Архив с примером на языке Pascal можно взять здесь.
На следующем шаге продолжим рассматривать рекурсию.
