В прошлой статье мы познакомились с замечательным приемом программирования рекурсией, рассмотрели его достоинства и недостатки, рассмотрели примеры, где она приводит к простым и элегантным решениям и где она, напротив, неуместна. Теперь я предлагаю вам заглянуть внутрь этого механизма и понаблюдать в деталях, что же происходит внутри программы при использовании рекурсивных вызовов.
Конечно же, рекурсию вполне можно использовать как черный ящик, не заглядывая внутрь, и некоторые именно так и делают (хотя многие не делают даже так). Однако понимание некоторых тонкостей позволит вам избежать некоторых неприятных сюрпризов, которые рекурсия может преподнести и на которых базируется предубеждение против ее использования.
Итак, открываем крышку черного ящика и смотрим внутрь, знакомясь с нехитрым механизмом внутри.
Благодарности
Прежде чем приступить непосредственно к изложению материала, хотелось бы упомянуть добрым словом людей, сопричастных к этой теме.
Прежде всего, конечно же, Dimyan, который в процессе своих неутомимых изысканий в дебрях .NET добрался наконец и до задачи, которую просто грех было не решить рекурсивными методами обработки древовидной структуры и тем самым сделал тему рекурсии не предметом абстрактного разговора, а реальным приемом, позволившим построить компактный и красивый алгоритм решения конкретной проблемы. Без этого статья, безусловно, потеряла бы изрядную часть интереса.
Добрые слова Never после первой публикации явились доказательством того, что время на работу над статьей было потрачено не зря и тему следует продолжить. Если справедливость восторжествует и программирование наконец-то займет достойное место среди прочих искусств, то я уже знаю имя десятой музы, которая будет ему покровительствовать :).
Нельзя также не высказать благодарности людям, которые приняли самое деятельное участие в обсуждении статьи.
ysv_ обнаружил ошибку, которая вкралась в одну из моих программ, и предложил ряд своих вариантов.
npak вопреки сложившейся у большинства программистов печальной традиции сразу же бросаться кодировать предварительно подверг задачу анализу с точки зрения теории автоматов, что в результате позволило нам рассмотреть два корректных решения одной задачи рекурсивное и нерекурсивное и воочию убедиться в допустимости и эквивалентности обоих подходов. Ему также принадлежат решения дополнительных задач, которые я предложил в форуме для закрепления навыков рекурсивного подхода.
Надеюсь, что и эта статья вызовет интерес у читателей.
С чего мы начнем
Выбор учебной задачи
В качестве иллюстративного материала для статьи я выбрал, как ни странно, подпрограмму рекурсивного вычисления факториала. Хотя мы и пришли к очевидному выводу, что на практике рекурсивный подход для данной задачи существенно уступает итеративному, тем не менее для данного применения эта подпрограмма имеет ряд вполне подходящих свойств:
* она предельно компактна и содержит минимум операторов, которые не будут заслонять своими деталями картины в целом;
* она не содержит никаких обращений к каким-либо объектам вне самой подпрограммы (в отличие от ханойских башен и многих подобных программ);
* при всем этом она решает вполне реальную, а не надуманную задачу, ее результат осмыслен, и его корректность может быть без труда проверена.
Выбор рабочей среды
В качестве рабочей среды я предпочел использование Microsoft Visual C++ версии 6 в составе интегрированной среды Visual Studio 6. Полагаю, большинство читателей располагают этим средством и не встретят затруднений при попытке воспроизвести примеры на своем рабочем компьютере. Не думаю также, что предпочитающих платформу .NET или компиляторы от Borland (включая старый добрый 16-разрядный C++ 3.1 для реального режима) ждут какие-то серьезные трудности; вам придется только повнимательнее изучить руководство к своему отладчику.
Подготовительные действия
Для подготовки к выполнению приведенных в статье примеров вам придется выполнить следующие действия:
* создать пустой проект консольного приложения;
* создать в этом проекте файл с исходным текстом программы;
* скопировать в него следующий исходный код:
Код:
long int Fact(long int N)
{
if (N < 1) return 0;
else if (N == 1) return 1;
else return N * Fact(N-1);
}
int main(void)
{
long int F3;
F3 = Fact(3);
return 0;
}
* открыть окно свойств проекта;
* выбрать конфигурацию Win32 Release;
* на вкладке C++ в категории General установить: Optimization = Minimize Size, Debug info = Program Database;
* установить Win32 Release в качестве активной конфигурации;
* откомпилировать программу.
Все, теперь во всеоружии мы можем приступать к погружению во внутренний мир рекурсивной программы.
Погружение
Исходное положение
Начинаем сеанс отладки нажатием на клавишу F11. Желтая стрелка, указывающая текущий оператор, устанавливается на первой строке нашей главной программы.
Теперь самое время открыть дополнительные окна, которые предоставят нам информацию о деталях процесса, происходящего в нашей нехитрой программе. В меню View -> Debug Windows выбираем:
* Registers для просмотра содержимого регистров процессора;
* Memory для исследования содержимого оперативной памяти;
* Disassembly для просмотра выполняемых инструкций процессора;
* Call Stack для доступа к содержимому стека вызовов функций.
Вот что находится в этих окнах в текущий момент (некоторые несущественные для рассмотрения детали, вроде содержимого не интересующих нас регистров, я буду опускать:
Registers:
Код:
EAX = 00321138
EBX = 7FFDF000
ECX = 00320768
EDX = 00320000
ESI = 00000000
EDI = 00000000
EIP = 00401021
ESP = 0012FF84
EBP = 0012FFC0
EFL = 00000206
CS = 001B DS = 0023
ES = 0023 SS = 0023
FS = 0038 GS = 0000 OV=0
UP=0 EI=1 PL=0 ZR=0 AC=0
PE=1 CY=0
Disassembly:
Код:
1: long int Fact(long int N)
2: {
00401000 56 push esi
00401001 8B 74 24 08 mov esi,dword ptr [esp+8]
00401005 6A 01 push 1
00401007 58 pop eax
00401008 3B F0 cmp esi,eax
0040100A 7D 04 jge Fact+10h (00401010)
0040100C 33 C0 xor eax,eax
0040100E 5E pop esi
6: }
0040100F C3 ret
3: if (N < 1) return 0;
4: else if (N == 1) return 1;
00401010 74 0D je Fact+1Fh (0040101f)
5: else return N * Fact(N-1);
00401012 8D 46 FF lea eax,[esi-1]
00401015 50 push eax
00401016 E8 E5 FF FF FF call Fact (00401000)
0040101B 0F AF C6 imul eax,esi
0040101E 59 pop ecx
0040101F 5E pop esi
6: }
00401020 C3 ret
7:
8: int main(void)
9: {
00401021 6A 03 push 3
00401023 E8 D8 FF FF FF call Fact (00401000)
00401028 59 pop ecx
10: long int F3;
11: F3 = Fact(3);
12: return 0;
00401029 33 C0 xor eax,eax
13: }
0040102B C3 ret
Call Stack:
Код:
main() line 9
MECH! mainCRTStartup + 180 bytes
KERNEL32! 77e814c7()
Как видно из окна Disassembly, будут выполнены следующие действия: сначала в стек будет отложена константа 3 (фактический аргумент вызываемой функции Fact), а затем вызвана сама функция.
Почему именно так? Для этого нам придется прерваться на некоторое время и ознакомиться с механизмом передачи параметров в функции C++.
Лирическое отступление механизм передачи параметров в функции.
Вообще говоря, способов передачи фактических параметров функции при ее вызове не так уж мало. Различия между ними одна из причин барьера между языками, когда функция, разработанная на одном языке программирования, не может быть вызвана на другом, и приходится переписывать ее заново, хотя функциональность нас вроде бы полностью устраивает.
Более-менее благополучно дело с межъязыковой совместимостью обстоит только в управляемой среде .NET, но в данном случае мы имеем дело с традиционным кодом, который в данный момент преобладает. Поэтому уделим немного времени рассмотрению механизмов, используемых для передачи параметров в программах на VC++ V6.
Подробно этот материал изложен в MSDN, в разделе MSDN Library Visual Studio 6.0 => Visual C++ Documentation => Using Visual C++ => Visual C++ Programmers Guide => Adding Program Functionality => Overviews => Calling conventions: Overview.
В прежних системах программирования порой применялись экзотические методы передачи параметров подпрограммам. Например, в FORTRAN IV аргументы (передаваемые только по ссылке) образовывали непрерывный блок в памяти, указатель на который передавался в одном из регистров общего назначения. Со временем разработчики реализаций пришли к выводу, что наиболее рационально передавать аргументы через стек. Впрочем, и тут нашелся повод для разногласий, даже целых два: 1) в каком порядке передавать параметры слева направо или справа налево, и 2) кто будет чистить стек после выполнения функции сама вызванная функция или тот, кто ее вызвал. К сожалению, там, где есть возможность выбора, найдется источник несовместимости. Итак, краткая сводка используемых методов передачи параметров (или, более корректно, соглашений о вызовах):
Метод Передача параметров Кто чистит стек Где применяется
__cdecl В стек, справа налево Вызывающий По умолчанию в C и C++
__stdcall В стек, справа налево Сама функция Вызовы почти всех системных функций, а также по умолчанию внутренние функции Visual Basic
__fastcall Два первых параметра в регистрах ECX и EDX, остальные в стек, справа налево Сама функция По умолчанию в Borland Delphi
thiscall Указатель this передается в регистре ECX, параметры в стек, справа налево. Сама функция Функциями-методами классов без списка аргументов переменной длины. Не может быть задан явно.
Как видно из этого краткого обзора, только __cdecl не чистит за собой стек после завершения функции, поэтому вызывающая функция должна каждый раз делать это явно. Естественно, это приводит к некоторому количеству избыточного кода по сравнению с другими соглашениями, для которых единственный фрагмент очистки стека встроен в само тело функции. Казалось бы, это нерационально, и выбор __cdecl в качестве соглашения по умолчанию неоправдан.
На самом деле это единственное соглашение, которое может поддерживать вызовы функций с переменным числом параметров вроде printf(). Поскольку функция не знает заранее, сколько аргументов получит при вызове, сгенерировать универсальный код для очистки стека в данном случае проблематично. Зато непосредственно в точке вызова функции об аргументах известно все, поэтому очистка стека не представляет проблем.
Таким образом, разработчики среды программирования идут на компромисс: ценой увеличения объема кода добиваются большей гибкости при передаче параметров. К счастью, как мы вскоре убедимся сами, эта цена не столь уж велика, чтобы существенно повлиять на общий размер программы.
Итак, подведем итог сказанному:
* по умолчанию C++ использует соглашение о вызовах __cdecl (и, поскольку мы явно не меняли это умолчание, код в нашей программе порожден с использованием именно этого соглашения);
* параметры функции заносятся в стек в обратном порядке, справа налево; таким образом, первый параметр окажется на верхушке стека, второй под ним и так далее; последний параметр зароется в стек глубже всех, поскольку начинается занесение именно с него;
* по завершении функция ничего не делает с параметрами; очистка стека обязанность вызывающего кода.
Теперь нам проще будет разобраться в коде нашего примера.
Первый вызов
Посмотрим теперь, куда указывает желтая стрелка в окне Disassembly. Это и есть текущие инструкции нашей программы. Поскольку мы еще не успели продвинуться по нашему примеру, мы видим самое начало функции main:
Код:
00401021 6A 03 push 3
00401023 E8 D8 FF FF FF call Fact (00401000)
На всякий случай повторю, что первая из этих инструкций заносит константу 3 на верхушку стека, а вторая вызывает функцию Fact. Совместно они реализуют вызов Fact(3).
Инструкция call это команда процессора, посредством которой реализуются вызовы подпрограмм. По этой команде выполнение потока инструкций временно прекращается и переходит к инструкциям, составляющим код подпрограммы (по адресу, который является аргументом инструкции). В конце подпрограммы находится инструкция ret, по которой поток инструкций возвращается обратно в код, вызвавший подпрограмму, и продолжается со следующей за call инструкции.
Разумеется, для возвращения необходимо сохранить адрес возврата, причем по возможности таким образом, чтобы вызываемая функция в свою очередь тоже могла вызывать другие функции, т.е. поддерживалась вложенность вызовов. Наилучшим образом для хранения адреса возврата, как и аргументов функций, подходит стек.
Поскольку следующие наши шаги непосредственно будут связаны со стеком (да и вообще при реализации рекурсии стек играет весьма важную роль), имеет смысл познакомиться с ним поближе.
Отступление второе - стек
Стек: логическая модель
На логическом уровне стек проще всего представить себе как стопку однородных предметов (например, книг, тарелок или любых других предметов, которые можно сложить друг на друга стопкой). Правило тут простое: класть очередной предмет можно только на верхушку стопки, и брать тоже можно только верхний предмет.
Такую структуру называют также очередью LIFO (Last In First Out, т.е. последним пришел первым ушел). Она незаменима, например, при хранении адресов возврата при вызовах функций.
Например, предположим, что функция F1 в некоторой точке вызывает F2, а та, в свою очередь, при выполнении вызывает F3. Для простоты примем, что изначально стек пуст.
Код:
void F1(void)
{
F2();
}
void F2(void)
{
F3();
}
void F3(void)
{
}
Исходное состояние стека:
???
???
???
После вызова F2:
???
???
Адрес возврата в F1
После вызова F3:
???
Адрес возврата в F2
Адрес возврата в F1
Выход из F3, возврат в F2:
???
???
Адрес возврата в F1
Выход из F2, возврат в F1:
???
???
???
Итак, вывод: корректная работа со стеком возможна только через его вершину. Несоблюдение этого правила ведет к нарушению целостности структуры. Вспомните фильм Операция Ы и катастрофу, которая постигла Вицина при попытке извлечь девайс со дна заполненного стека
Стек: физическая реализацияРазумеется, никакого специального аппаратного блока для реализации стека внутри компьютера вы не найдете; по крайней мере, это на 100% верно для IBM PC-совместимых компьютеров, на одном из которых вы сейчас наверняка и работаете с этой статьей. Все, что найдется подходящего в его архитектуре, - это однородный массив ячеек оперативной памяти и набор регистров внутри центрального процессора. К счастью, этого вполне достаточно для организации стека.
Физически стек это специально выделенная область оперативной памяти. Стек растет в обратном направлении, т.е. от старших адресов к младшим. Таким образом, дно стека это ячейка с максимальным адресом в области стека.
На вершину стека указывает специальный регистр процессора, который так и называется указатель стека. Его содержимое можно увидеть среди прочих регистров в окне Registers, он фигурирует там под именем ESP.
Стек работает со словами размером 32 бита, или 4 байта. В случае, если реальные данные требуют для хранения меньше места, свободный остаток не используется. Это может показаться расточительным, но, во-первых, обмен словами между процессором и оперативной памятью наиболее эффективен, во-вторых, меньше вероятность нарушить структуру стека, скажем, положив туда длинное целое, а потом забрав один байт.
При занесении слова в стек командой push сначала содержимое регистра ESP уменьшается на 4, а затем слово заносится в оперативную память по адресу, который хранится в ESP.
При извлечении слова из стека командой pop с верхушки стека, то есть из ячейки оперативной памяти с адресом, хранящемся в ESP, считывается значение, а потом содержимое ESP увеличивается на 4.
Обратите внимание, что при выборке из стека не происходит физического уничтожения прежних значений хранящихся там данных. Они всего лишь перестают быть доступны через операции со стеком, но по-прежнему остаются в тех же ячейках оперативной памяти. Разумеется, прежние значения этих данных будут уничтожены при последующем занесении новых данных в стек.
Продолжаем разговор
Разумеется, это отступление было неспроста. Теперь мы знаем, что такое стек и где его искать.
У нас по-прежнему открыто окно Memory, которое мы до сих пор никак не использовали. Разумеется, открывали мы его не для того, чтобы чем-то заполнить экран. Самое время воспользоваться им для того, чтобы следить за состоянием стека, вооружившись только что полученными познаниями.
Для этого:
* находим ESP среди регистров процессора в окне Registers;
* двойным щелчком левой кнопки мыши выделяем его содержимое (у меня это - 0012FF84);
* копируем его в буфер (комбинацией <Ctrl>+C или кому как больше нравится);
* в окне Memory выделяем поле ввода Address и вставляем туда содержимое указателя стека (комбинацией <Ctrl>+V);
* для большего удобства переключаем окно Memory на показ содержимого памяти в виде 32-разрядных слов (раз уж стек все равно работает именно с ними); сделать это можно, щелкнув правой кнопкой мыши в окне и выбрав Long Hex Format в контекстном меню.
Теперь мы обзавелись инструментом для наблюдения за метаморфозами, происходящими в стеке. Это было необходимо, поскольку все самое интересное в ближайшее время будет происходить именно там.
Наберемся храбрости и нажмем 2 раза клавишу F11 (каждое нажатие это команда отладчику выполнить очередную инструкцию процессора в пошаговом режиме). Сразу же заглянем в стек:
Код:
0012FF7C 00401028
0012FF80 00000003
0012FF84 004010E0
Мы видим, что значение формального параметра 3 оказалось в стеке. А на вершине стека теперь лежит 00401028. Обратившись к окну Disassembly, мы видим, что это адрес инструкции, следующей за вызовом функции Fact.
Вход в функцию Fact
Если вы аккуратно проделали предыдущие действия, в данный момент программа должна в первый раз войти в функцию Fact, и указатель текущей инструкции (желтая стрелка) находится перед первой ее инструкцией.
Прежде всего посмотрим, что делается в стеке вызовов функций (окно CallStack):
Код:
Fact(long 3) line 2
main() line 9 + 7 bytes
MECH! mainCRTStartup + 180 bytes
KERNEL32! 77e814c7()
Судя по тому, что мы уже знаем о стеках, события в нем должны идти в порядке, обратном хронологическому, т.е последнее находиться на вершине стека. Так и есть: в верхней строке мы видим вызов Fact(3), затем вызвавшую ее функцию main(). (Ниже расположены еще 2 строки, имеющие отношение к работе исполняющей системы. Для того, чтобы наша программа могла выполняться, перед ее запуском необходимо проделать некоторую вспомогательную работу по созданию среды, в которой она будет выполняться. Однако этот вопрос находится за пределами нашей темы).
Первая инструкция функции:
Код:
00401000 56 push esi
Как мы уже знаем, команда push заносит в стек свой операнд (в данном случае содержимое регистра ESI). Очевидно, компилятор планировал использовать этот регистр для своих нужд, поэтому позаботился о предварительном сохранении его содержимого в стеке. Такой подход является хорошим стилем при программировании на ассемблере перед тем, как менять содержимое регистра в подпрограмме, сохранить его содержимое в стеке, а перед выходом из подпрограммы восстановить его содержимое, если только регистр не используется для возврата результата функции, и позволяет избежать многих неприятных ошибок.
Выполняем очередную команду (напоминаю, делается это нажатием на клавишу F11) и проверяем состояние стека. Обратите внимание, что значение ESP изменилось с 0012FF7C на 0012FF78. Новое содержимое стека:
Код:
0012FF78 00000000
0012FF7C 00401028
0012FF80 00000003
0012FF84 004010E0
Следующая инструкция подтверждает нашу догадку о том, что сохранение ESI было сделано неспроста:
Код:
00401001 8B 74 24 08 mov esi,dword ptr [esp+8]
Эта инструкция загружает в регистр ESI содержимое двойного слова (dword), которое смещено на 8 байт (или 2 слова) относительно указателя стека ESP.
Прокрутим обратно в памяти историю работы программы со стеком. На вершине стека ([esp]) лежит прежнее содержимое регистра ESI, под ним ([esp+4]) адрес возврата в вызывающую функцию main(), а еще ниже ([esp+8]) константа 3, которая была загружена в стек перед вызовом Fact (в полном соответствии с соглашением о вызовах __cdecl, как мы уже знаем).
Выполняем эту инструкцию. Обратите внимание, что в окне Registers содержимое ESI отмечено красным цветом. Отладчик использует это выделение, чтобы программисту легче было заметить, что содержимое регистра изменилось. Новое значение, как и следовало ожидать,
Код:
ESI = 00000003
Итак, наша функция получила доступ к значению своего аргумента через регистр ESI. Как видно из исходного текста функции
Код:
if (N < 1) return 0;
сначала функция должна сравнить аргумент с 1 и возвратить в случае равенства значение 0. Столь нехитрая конструкция, тем не менее, не может быть выполнена в коде процессора за один шаг.
Прежде всего нужно получить константу 1. Это достигается парой инструкций:
Код:
00401005 6A 01 push 1
00401007 58 pop eax
Константа сначала помещается в стек, а потом загружается из него в регистр EAX. (Казалось бы, нерациональный подход, проще было бы прямо загрузить 1 в EAX. Однако попробуйте и убедитесь, что в этом случае код получается длиннее. Впрочем, не будем заострять на этом внимание, ибо статья не об оптимизации).
Следующая инструкция производит сравнение:
Код:
00401008 3B F0 cmp esi,eax
Эта инструкция выполняется аналогично вычитанию, однако при этом ни один из операндов не меняется. Зато флаги в регистре состояния устанавливаются в соответствии с результатом и могут быть использованы для условного перехода.
Обычно инструкция cmp используется в паре с последующим условным переходом. Именно так обстоит дело и в нашем случае:
Код:
0040100A 7D 04 jge Fact+10h (00401010)
В случае, если значение аргумента (ESI) больше или равно 1 (EAX), выполнение продолжается с ветки else. В нашем случае так и есть (3 ;gt= 1).
Следом должно выполниться сравнение аргумента с 1 на равенство:
Код:
else if (N == 1) return 1;
Это делается при помощи инструкции условного перехода по равенству:
Код:
00401010 74 0D je Fact+1Fh (0040101f)
В этом случае инструкции условного перехода не предшествует инструкция сравнения, т.к. предыдущая инструкция условного перехода оставляет состояние флагов неизменным, и им можно воспользоваться.
В нашем случае условие (3 == 1) не выполняется, поэтому выполнение функции продолжается.
А теперь самое интересное: рекурсивный вызов:
Код:
5: else return N * Fact(N-1);
Должен быть произведен вызов функции Fast(N-1). Для этого, как мы уже знаем, сначала следует положить на вершину стека значение (N-1). Это делается парой инструкций
Код:
00401012 8D 46 FF lea eax,[esi-1]
00401015 50 push eax
Как всегда, не забываем заглянуть в стек:
Код:
ESP = 0012FF74
0012FF74 00000002
0012FF78 00000000
0012FF7C 00401028
0012FF80 00000003
0012FF84 004010E0
Значение (N-1), то есть 2, теперь находится на вершине стека. Остается произвести рекурсивный вызов:
Код:
00401016 E8 E5 FF FF FF call Fact (00401000)
Выполняем его (F11).
Первый рекурсивный вход в Fact
На первый взгляд, мы снова оказались в том же месте, что и в предыдущем разделе. Указатель текущей инструкции находится все на той же первой инструкции функции Fact. Но это только на первый взгляд.
Во-первых, на вершине стека у нас находится 2, а не 3, как в прошлый раз.
Во-вторых, посмотрим в окно Call Stack:
Код:
Fact(long 2) line 2
Fact(long 3) line 5 + 9 bytes
main() line 9 + 7 bytes
MECH! mainCRTStartup + 180 bytes
KERNEL32! 77e814c7()
На вершине стека вызовов появился новый вызов Fact(2).
Продолжаем пошагово выполнять функцию до инструкции call по адресу 00401016. Все происходит почти так же, как и в прошлый раз, за исключением того, что в этот раз на вершине стека находится значение 1:
Код:
ESP = 0012FF68
0012FF68 00000001
0012FF6C 00000003
0012FF70 0040101B
0012FF74 00000002
0012FF78 00000000
0012FF7C 00401028
0012FF80 00000003
0012FF84 004010E0
Второй (и последний) рекурсивный вход в Fact
В первую очередь, как обычно, проверяем стек вызовов:
Код:
Fact(long 1) line 2
Fact(long 2) line 5 + 9 bytes
Fact(long 3) line 5 + 9 bytes
main() line 9 + 7 bytes
MECH! mainCRTStartup + 180 bytes
KERNEL32! 77e814c7()
Пошагово выполняем функцию до инструкции cmp по адресу 00401008. В этот раз значения сравниваемых регистров у нас равны:
Код:
EAX = 00000001
ESI = 00000001
Следовательно, можно ожидать, что результат сравнения будет иным. Проверим это предположение, выполнив инструкцию cmp. В этот раз в окне Registers установился флаг ZR=1, что указывает на равенство операндов инструкции. По этому условию инструкция
Код:
00401010 74 0D je Fact+1Fh (0040101f)
должна осуществить переход.
Так и есть: по очередному нажатию F11 попадаем на инструкцию
Код:
0040101F 5E pop esi
Состояние стека на этот момент
Код:
ESP = 0012FF60
0012FF60 00000002
0012FF64 0040101B
0012FF68 00000001
0012FF6C 00000003
0012FF70 0040101B
0012FF74 00000002
0012FF78 00000000
0012FF7C 00401028
0012FF80 00000003
0012FF84 004010E0
Инструкция pop восстанавливает значение регистра ESI, сохраненное в момент входа в функцию (если вы внимательно отслеживали операции со стеком, то заметили, что это не что иное, как значение формального аргумента N из вызывающей функции). Выполняем ее:
Код:
ESI = 00000002
ESP = 0012FF64
0012FF64 0040101B
0012FF68 00000001
0012FF6C 00000003
0012FF70 0040101B
0012FF74 00000002
0012FF78 00000000
0012FF7C 00401028
0012FF80 00000003
0012FF84 004010E0
Наконец-то мы достигли инструкции ret, которая осуществляет возврат из подпрограммы (путем загрузки счетчика команд EIP содержимым вершины стека):
Код:
00401020 C3 ret
С этого момента начинается обратная раскрутка стека вызовов.
Стек вызовов: обратная раскрутка
Выполнив инструкцию ret, мы возвращаемся обратно в первый рекурсивный вызов функции:
Код:
Call stack:
Fact(long 2) line 5 + 9 bytes
Fact(long 3) line 5 + 9 bytes
main() line 9 + 7 bytes
MECH! mainCRTStartup + 180 bytes
KERNEL32! 77e814c7()
Остаток кода функции, который будет выполняться далее, имеет вид:
Код:
0040101B 0F AF C6 imul eax,esi
0040101E 59 pop ecx
&nbsз;0040101F 5E pop esi
6: }
00401020 C3 ret
Инструкция imul выполняет целочисленное умножение. В данном случае будет вычислено произведение EAX*ESI, и результат будет занесен в регистр EAX.
Как мы уже выяснили, в регистре ESI в нашей функции хранится значение N, то есть в данном случае 2. Но вот в регистр EAX мы вроде бы ничего подходящего не заносили. Зачем мы используем его в инструкции умножения?
Чтобы понять это, нам нужно узнать еще небольшую деталь о вызове функций. Мы уже знаем, как передать значения фактических параметров в функцию, но ни слова до сих пор не сказали о том, как же функция возвращает результат своей работы. На самом деле это происходит очень просто, во всяком случае, когда результат функции типа int: при выходе из функции возвращаемое значение находится в регистре EAX.
Теперь все становится понятно: вызов Fact(1) завершился, вернув результат 1 в регистре EAX, который теперь и используется в инструкции умножения. В результате выполнения инструкции
Код:
EAX = 00000002
Состояние стека в данный момент:
Код:
ESP = 0012FF68
0012FF68 00000001
0012FF6C 00000003
0012FF70 0040101B
0012FF74 00000002
0012FF78 00000000
0012FF7C 00401028
0012FF80 00000003
0012FF84 004010E0
Следующая инструкция
Код:
0040101E 59 pop ecx
на первый взгляд несколько туманна. Мы ведь не использовали регистр ECX до сих пор, зачем же нам нужно загружать его из стека?
Все станет ясно, если вспомнить подробнее детали соглашения __cdecl. Как уже было сказано, при этом соглашении убирать параметры функции из стека должен вызывающий код, а не сама функция. Данная инструкция это самый компактный способ продвинуть указатель стека вперед на одно слово. В качестве побочного эффекта при этом изменяется значение регистра ECX, но его содержимое не представляет для нас интереса.
Итак, данная инструкция всего лишь чистит стек после вызова Fact(1):
Код:
ESP = 0012FF6C
0012FF6C 00000003
0012FF70 0040101B
0012FF74 00000002
0012FF78 00000000
0012FF7C 00401028
0012FF80 00000003
0012FF84 004010E0
Очередная инструкция
Код:
0040101F 5E pop esi
восстанавливает значение регистра ESI, которое мы испортили в начале функции:
Код:
ESI = 00000003
ESP = 0012FF70
0012FF70 0040101B
0012FF74 00000002
0012FF78 00000000
0012FF7C 00401028
0012FF80 00000003
0012FF84 004010E0
Далее инструкция ret завершает очередной вызов Fact(2):
Код:
Call Stack:
Fact(long 3) line 5 + 9 bytes
main() line 9 + 7 bytes
MECH! mainCRTStartup + 180 bytes
KERNEL32! 77e814c7()
Теперь мы вернулись в первый, нерекурсивный вызов Fact(3). Указатель текущей инструкции вновь находится в строке
Код:
0040101B 0F AF C6 imul eax,esi
но в этот раз уже
Код:
EAX = 00000002
ESI = 00000003
(соответственно значения Fact(2) и N).
Пошагово выполняем остаток инструкций функции и возврат в вызывающую функцию main(). Теперь у нас:
Код:
EAX = 00000006
ESI = 00000000
ESP = 0012FF80
0012FF80 00000003
0012FF84 004010E0
Осталось рассмотреть теперь совсем немного. Инструкция
Код:
00401028 59 pop ecx
как мы уже знаем, очищает верхушку стека от аргумента предыдущего вызова (константы 3). Следующая инструкция
Код:
00401029 33 C0 xor eax,eax
заносит 0 в регистр EAX, который снова будет использован в качестве возвращаемого функцией main() значения (c точки зрения исполняющей системы main() такая же функция, как и любая другая, за исключением того, что с нее начинается выполнение программы, и она так же точно может возвращать значение, которое используется системой в качестве кода завершения; обычно 0 нормальное завершение, отличное от нуля значение код ошибки, хотя это соглашение применяется не всегда).
Наконец, инструкция
Код:
0040102B C3 ret
осуществляет возврат в исполняющую систему, которая выполнит код, необходимый для корректного завершения программы.
Заключение
Разумеется, в качестве примера я выбрал наиболее примитивный вариант рекурсивной программы, который выполняет минимум действий и лишен каких бы то ни было средств ввода/вывода. Тем не менее на этом примере мы смогли увидеть метаморфозы, проистекающие в стеке при работе рекурсивной программы, а также ознакомиться с низкоуровневыми деталями передачи параметров в вызываемые функции (разумеется, не только рекурсивные).
Кроме того, мы могли убедиться, что при работе функции стек использовался не столь уж расточительно: на каждый рекурсивный вызов расходовались 3 слова в стеке. Если учесть, что результат вычисления 50! уже превосходит 1 с 64 нулями и вряд ли может потребоваться на практике, вряд ли при реальных вычислениях будет использовано более 150 двойных слов стека, что можно назвать непомерной ценой лишь с большой натяжкой. Конечно, параметров у рекурсивной функции вполне может быть и более, чем 1, да и могут потребоваться вспомогательные локальные переменные, которые также размещаются в стеке. Однако при рациональном построении алгоритма и умеренной глубине рекурсии использование стека обычно остается в пределах разумного.
Конечно, убежденные противники рекурсии всегда смогут привести пример рекурсивного приложения, которому и гигабайта стека окажется недостаточно. Но тут уж мне остается только вспомнить поговорку, что существует категория людей, которые даже когда их заставляют молиться богу, умудряются получить травмы головы
(Если вам все еще интересно, продолжение следует).
Alf
Information
- Posted on 31.01.2010 22:05
- Просмотры: 2961