Методика изучения понятия «рекурсия»

В статье рассмотрена методика изучения «рекурсия» в среде Microsoft Visual Studio .Net и с использованием компилятора Microsoft Visual C++ 7.0. Изложение материала построено в виде диалога с обучаемым.

Что такое рекурсия? В информатике в это понятие вкладывается следующий смысл: рекурсия – это прием программирования, при котором программа (подпрограмма, процедура, функция) вызывает саму себя либо непосредственно, либо косвенно. Принцип действия рекурсии интуитивно понятен, но перед тем как начать более глубокое изучение рекурсии, рассмотрим общий механизм реализации рекурсии:
1. Функция F выполняет рекурсивный вызов.
2. Запоминается текущее состояние программы, необходимое для продолжения вычислений, когда управление снова вернется к ней.
3. F начинает выполняться заново, с новыми значениями всех локальных переменных и параметров.
4. Все повторяется до тех пор, пока очередной вызов F не приведет к какому‑либо тривиальному случаю, разрешаемому без рекурсии.
5. Происходит возврат управления в порядке, обратному тому, в котором запоминались вызовы; очистка памяти на каждом шаге.
Это универсальная схема, при реализации которой необходимо убедиться, что количество рекурсивных вызовов конечно и достаточно мало, так как каждый новый рекурсивный вызов требует процессорного времени и выделения дополнительной памяти для сохранения локальных переменных и дополнительной информации.
Несмотря на все свои преимущества, рекурсия используется далеко не всеми программистами. Зачастую это упущение связано с неполным пониманием рекурсии и устоявшимися негативными мнениями, связанными с накладными расходами на ее использование. Приведем некоторые из таких доводов:
1. Рекурсия требует большое количество памяти.
2. При рекурсивном алгоритме тратятся значительные ресурсы процессора.
3. Сложно реализовать рекурсивную процедуру и еще сложнее ее отлаживать.
Первые два пункта имеют под собой основания, но не надо забывать, что вычислительная техника совершенствуется год от года. Так что эти проблемы были актуальны лет 10 назад, сегодня же увеличившаяся производительность процессоров (примерно в 100 раз) и возросшие объемы памяти (от нескольких Кбайт до нескольких Гбайт) сводят их почти на нет. Третий пункт связан, скорее всего, с недостаточным пониманием рекурсии, так как замена рекурсии на циклы с пред‑ или постусловием не облегчит задачу и ее отладку.
Использование рекурсии достаточно просто, но что происходит на самом деле и достижение понимания механизмов её реализации не очевидно. Чтобы избежать возможных ошибок при работе с рекурсией, следует изучить процессы, происходящие при компиляции программы и ее запуске.
Нахождение факториала числа хоть и является «плохой» задачей для демонстрации рекурсии, но остановим наш выбор именно на этой задаче. Этому есть несколько причин:
1. Функция проста в реализации и содержит минимум операторов. Этого вполне достаточно, чтобы пронаблюдать за рекурсией.
2. Решается вполне реальная задача, результаты которой могут быть легко проверены.
В качестве языка программирования и среды для тестирования была выбрана Microsoft Visual Studio .Net и Microsoft Visual С++ 7.0. Нам понадобится создать новый пустой проект, добавить в него файл Fact.cpp и поместить в него код программы:
int Fact(int N)
{
if (N < 1) return 0;
else if (N == 1) return 1;
else return N * Fact(N‑1);
}
int main(void)
{
int F3;
F3 = Fact(3);
return 0;
}

Теперь можно запустить приложение в пошаговом режиме (для этого воспользоваться клавишей F11) и открыть все необходимые окна (в меню Debug – Windows):
Registers – для просмотра содержимого регистров процессора;
Memory – для исследования содержимого оперативной памяти;
Disassembly – для просмотра выполняемых инструкций процессора;
Call Stack – для доступа к содержимому стека вызовов функций.
Вот что находится в этих окнах в текущий момент (некоторые несущественные для рассмотрения детали, вроде содержимого не интересующих нас регистров, пропущены):
Окно Registers:
EAX = 003215A8 EBX = 7FFDE000 ECX = 00321530
EDX = 00000001 ESI = 00000040 EDI = 7C915B4F
EIP = 00411AA0 ESP = 0012FEE0 EBP = 0012FFC0
EFL = 00000246

CS = 001B DS = 0023 ES = 0023 SS = 0023 FS = 003B
GS = 0000

OV = 0 UP = 0 EI = 1 PL = 0 ZR = 1 AC = 0 PE = 1 CY = 0 Окно Disassembly:
int Fact(int N)
{
00411A20 push ebp
00411A21 mov ebp,esp
00411A23 sub esp,0C0h
00411A29 push ebx
00411A2A push esi
00411A2B push edi
00411A2C lea edi,[ebp‑0C0h]
00411A32 mov ecx,30h
00411A37 mov eax,0CCCCCCCCh
00411A3C rep stos dword ptr [edi]
if (N < 1) return 0;
00411A3E cmp dword ptr [N],1
00411A42 jge Fact+28h (411A48h)
00411A44 xor eax,eax
00411A46 jmp Fact+48h (411A68h)
else if (N == 1) return 1;
00411A48 cmp dword ptr [N],1
00411A4C jne Fact+35h (411A55h)
00411A4E mov eax,1
00411A53 jmp Fact+48h (411A68h)
else return N * Fact(N‑1);
00411A55 mov eax,dword ptr [N]
00411A58 sub eax,1
00411A5B push eax
00411A5C call Fact (41126Ch)
00411A61 add esp,4
00411A64 imul eax,dword ptr [N]
}
00411A68 pop edi
00411A69 pop esi
00411A6A pop ebx
00411A6B add esp,0C0h
00411A71 cmp ebp,esp
00411A73 call @ILT+935(__RTC_CheckEsp) (4113ACh)
00411A78 mov esp,ebp
00411A7A pop ebp
00411A7B ret

int main(void)
{
00411AA0 push ebp
00411AA1 mov ebp,esp
00411AA3 sub esp,0CCh
00411AA9 push ebx
00411AAA push esi
00411AAB push edi
00411AAC lea edi,[ebp‑0CCh]
00411AB2 mov ecx,33h
00411AB7 mov eax,0CCCCCCCCh
00411ABC rep stos dword ptr [edi]
int F3;
F3 = Fact(3);
00411ABE push 3
00411AC0 call Fact (41126Ch)
00411AC5 add esp,4
00411AC8 mov dword ptr [F3],eax
return 0;
00411ACB xor eax,eax
}
00411ACD pop edi
00411ACE pop esi
00411ACF pop ebx
00411AD0 add esp,0CCh
00411AD6 cmp ebp,esp
00411AD8 call @ILT+935(__RTC_CheckEsp) (4113ACh)
00411ADD mov esp,ebp
00411ADF pop ebp
00411AE0 ret
Окно Call Stack:
Factor.exe!main() Line 9 C++
Factor.exe!mainCRTStartup() Line 259 + 0x19 C
kernel32.dll!7c816d4f()
ntdll.dll!7c915b4f()
kernel32.dll!7c8399f3()
Как видно из окна Disassembly, будут выполнены следующие действия: сначала в стек будет отложена константа 3 (фактический аргумент вызываемой функции Fact), а затем вызвана сама функция. Чтобы разобраться в причинах такого поведения, необходимо ознакомиться с механизмом передачи параметров в функции в C++. Мы не будем останавливаться на этом вопросе, так как он выходит за рамки данной темы, отметим лишь, что в С++ по умолчанию используется метод __cdecl для передачи параметров. Этот метод обеспечивает передачу параметров через стек, при этом параметры берутся в порядке справа налево.
Первый вызов
Итак, после запуска проекта желтая стрелка в окне Disassembly указывает на текущую строчку, которая должна выполниться. Поскольку мы еще не успели продвинуться по нашему примеру, мы видим самое начало функции main:
00411ABE push 3
00411AC0 call Fact (41126Ch)

Инструкция call – это команда процессора, посредством которой реализуются вызовы подпрограмм. По этой команде выполнение потока инструкций временно прекращается и переходит к инструкциям, составляющим код подпрограммы (по адресу, который является аргументом инструкции). В конце подпрограммы находится инструкция ret, по которой поток инструкций возвращается обратно в код, вызвавший подпрограмму, и продолжается со следующей за call инструкции.
Команда push заносит значение (аргумент инструкции) в стек.
Команда pop считывает значение из стека и заносит его аргумент инструкции.
Первая из этих инструкций заносит константу 3 на верхушку стека, а вторая вызывает функцию Fact. Совместно они реализуют вызов Fact(3).
Разумеется, для возвращения необходимо сохранить адрес возврата, причем по возможности таким образом, чтобы вызываемая функция в свою очередь тоже могла вызывать другие функции, т.е. поддерживалась вложенность вызовов. Наилучшим образом для хранения адреса возврата, как и аргументов функций, подходит стек.
Физически стек – это специально выделенная область оперативной памяти. Стек растет в обратном направлении, т.е. от старших адресов к младшим. Таким образом, дно стека – это ячейка с максимальным адресом в области стека. На вершину стека указывает специальный регистр процессора ESP. Стек работает со словами размером 32 бита, или 4 байта. В случае, если реальные данные требуют для хранения меньше места, свободный остаток не используется. Это может показаться расточительным, но, во‑первых, обмен словами между процессором и оперативной памятью наиболее эффективен, во‑вторых, меньше вероятность нарушить структуру стека, скажем, положив туда длинное целое, а потом забрав один байт.
При занесении слова в стек командой push сначала содержимое регистра ESP уменьшается на 4, а затем слово заносится в оперативную память по адресу, который хранится в ESP. При извлечении слова из стека командой pop с верхушки стека, то есть из ячейки оперативной памяти с адресом, хранящемся в ESP, считывается значение, а потом содержимое ESP увеличивается на 4.
На вершину стека указывает специальный регистр процессора – ESP, его содержимое можно увидеть в окне Registers. Для просмотра содержимого стека воспользуемся окном Memory, которое мы до сих пор никак не использовали. Для этого:
находим ESP среди регистров процессора в окне Registers;
двойным щелчком левой кнопки мыши выделяем его содержимое (возможное значение регистра 0012FE04);
копируем его в буфер;
в окне Memory выделяем поле ввода Address и вставляем туда содержимое указателя стека;
для большего удобства переключаем окно Memory на показ содержимого памяти в виде 32‑разрядных слов (так как стек все равно работает именно с ними); сделать это можно, щелкнув правой кнопкой мыши в окне и выбрав «4‑byte Integer» и «Hexadecimal Display» в контекстном меню.
Теперь мы можем наблюдать за изменениями, происходящими в стеке, а именно там и будет происходить все самое важное.
Нажмем клавишу F11 2 раза (каждое нажатие – это команда отладчику выполнить очередную инструкцию процессора в пошаговом режиме). Сразу обратим внимание на содержимое стека:
0x0012FDFC 00411ac5
0x0012FE00 00000003
0x0012FE04 7c915b4f
Мы видим, что значение формального параметра – 3 – оказалось в стеке. А на вершине стека теперь лежит 00411ac5 – адрес инструкции (его можно найти в окне Disassembly), следующей за вызовом функции Fact. Кроме того, изменился регистр ESP – уменьшился на 8, т.е. на два 32‑разрядных слова.

Вход в функцию Fact
Если все предыдущие действия проделаны аккуратно, то программа должна в первый раз войти в функцию Fact, и указатель текущей инструкции (желтая стрелка) находится перед первой ее инструкцией.
Посмотрим, что делается в стеке вызовов функций (окно CallStack):
Factor.exe!Fact(int N=3) Line 2 C++
Factor.exe!main() Line 11 + 0x7 C++
Factor.exe!mainCRTStartup() Line 259 + 0x19 C
kernel32.dll!7c816d4f()
ntdll.dll!7c915b4f()
kernel32.dll!7c8399f3()

События в стеке должны идти в порядке, обратном хронологическому. Так и есть: в верхней строке мы видим вызов Fact(3), затем вызвавшую ее функцию – main(). Ниже расположены строки, имеющие отношение к работе исполняющей системы, в частности, для создания среды, в которой будет выполняться программа.

Первая инструкция функции:
00411A20 push ebp
00411A21 mov ebp,esp
00411A23 sub esp,0C0h
00411A29 push ebx
00411A2A push esi
00411A2B push edi
00411A2C lea edi,[ebp‑0C0h]
00411A32 mov ecx,30h
00411A37 mov eax,0CCCCCCCCh
00411A3C rep stos dword ptr [edi]

Команда push заносит в стек свой операнд, в данном случае – содержимое регистров EBP, EBX, ESI. Очевидно, компилятор планировал использовать этот регистр для своих нужд, поэтому позаботился о предварительном сохранении его содержимого в стеке (при выходе из функции данные стека будут восстановлены в этих регистрах).
Выполним все команды до строчки «if (N < 1) return 0;» и проверим состояние стека. Обратите внимание, что изменилось значение ESP и содержимое стека.
Итак, для следующего сравнения функция должна сравнить аргумент с 1 и возвратить в случае равенства значение 0. Столь нехитрая конструкция, тем не менее, не может быть выполнена в коде процессора за один шаг.
00411A3E cmp dword ptr [N],1
Инструкция cmp выполняется аналогично вычитанию, однако при этом ни один из операндов не меняется. Зато флаги в регистре состояния устанавливаются в соответствии с результатом и могут быть использованы для условного перехода.
Обычно инструкция cmp используется в паре с последующим условным переходом. Именно так обстоит дело и в нашем случае:
00411A42 jge Fact+28h (411A48h)

В случае, если значение аргумента (N) больше или равно 1, выполнение продолжается с ветки else. В нашем случае так и есть (3 > 1).
Следом должно выполниться сравнение аргумента с 1 на равенство:
else if (N == 1) return 1;

Это делается при помощи следующих инструкций:
00411A48 cmp dword ptr [N],1
00411A4C jne Fact+35h (411A55h)
00411A4E mov eax,1
00411A53 jmp Fact+48h (411A68h)

В нашем случае условие (3 == 1) не выполняется, поэтому выполнение функции продолжается.
А теперь – самое интересное: рекурсивный вызов:
else return N * Fact(N‑1);

Должен быть произведен вызов функции Fact(N‑1). Для этого, как мы уже знаем, сначала следует положить на вершину стека значение (N‑1). Это делается тремя инструкциями: сначала помещаем N в регистр EAX, затем вычитаем из него единицу и только потом заносим значение N‑1 в стек при помощи команды push:
00411A55 mov eax,dword ptr [N]
00411A58 sub eax,1
00411A5B push eax

Как всегда, не забываем заглянуть в стек:
ESP = 0012FD28
0x0012FD28 00000002

Значение (N‑1), то есть 2, теперь находится на вершине стека. Остается произвести рекурсивный вызов:
00411A5C call Fact (41126Ch)
Выполняем его при помощи кнопки F11.

Первый рекурсивный вход в Fact
На первый взгляд, мы снова оказались в том же месте, что и в предыдущем разделе. Указатель текущей инструкции находится все на той же первой инструкции функции Fact. Но это только на первый взгляд.
Во‑первых, на вершине стека у нас находится 2, а не 3, как в прошлый раз.
Во‑вторых, посмотрим в окно Call Stack:
Factor.exe!Fact(int N=2) Line 2 C++
Factor.exe!Fact(int N=3) Line 5 + 0xc C++
Factor.exe!main() Line 11 + 0x7 C++
Factor.exe!mainCRTStartup() Line 259 + 0x19 C
kernel32.dll!7c816d4f()
ntdll.dll!7c915b4f()
kernel32.dll!7c8399f3()

На вершине стека вызовов появился новый вызов Fact(2).
Продолжаем пошагово выполнять функцию до инструкции call по адресу 00411A5C. Все происходит почти так же, как и в прошлый раз, за исключением того, что в этот раз на вершине стека находится значение 1.

Второй (и последний) рекурсивный вход в функцию Fact
В первую очередь, как обычно, проверяем стек вызовов:
Factor.exe!Fact(int N=1) Line 2 + 0x1 C++
Factor.exe!Fact(int N=3) Line 5 + 0xc C++
Factor.exe!main() Line 11 + 0x7 C++
Factor.exe!mainCRTStartup() Line 259 + 0x19 C
kernel32.dll!7c816d4f()
ntdll.dll!7c915b4f()
kernel32.dll!7c8399f3()

Пошагово выполняем функцию до инструкции cmp по адресу 00411A48. В этот раз сравниваемые значения у нас равны. Выполнив эту команду в окне Registers можно заметить, что значение флага ZR=1, что указывает на равенство операндов инструкции. Значит мы должны вернуть 1 и закончить выполнение функции, за это отвечают 2 инструкции:
00411A4E mov eax,1
00411A53 jmp Fact+48h (411A68h)

Далее выполняется восстановление сохраненных в стеке значений:
00411A68 pop edi
00411A69 pop esi
00411A6A pop ebx
00411A6B add esp,0C0h
00411A71 cmp ebp,esp
00411A73 call @ILT+935(__RTC_CheckEsp) (4113ACh)
00411A78 mov esp,ebp
00411A7A pop ebp

Наконец‑то мы достигли инструкции ret, которая осуществляет возврат из подпрограммы:
00411A7B ret
С этого момента начинается обратная раскрутка стека вызовов.

Стек вызовов: обратная раскрутка
Выполнив инструкцию ret, мы возвращаемся обратно в первый рекурсивный вызов функции:
Обратим внимание на окно Call Stack:
Factor.exe!Fact(int N=2) Line 5 + 0xc C++
Factor.exe!Fact(int N=3) Line 5 + 0xc C++
Factor.exe!main() Line 11 + 0x7 C++
Factor.exe!mainCRTStartup() Line 259 + 0x19 C
kernel32.dll!7c816d4f()
ntdll.dll!7c915b4f()
kernel32.dll!7c8399f3()
Остаток кода функции, который будет выполняться далее, имеет вид:
00411A61 add esp,4
00411A64 imul eax,dword ptr [N]

Инструкция imul выполняет целочисленное умножение. В данном случае будет вычислено произведение EAX*N, и результат будет занесен в регистр EAX.
В регистр EAX мы вроде бы ничего подходящего не заносили. Зачем мы используем его в инструкции умножения? При выходе из функции возвращаемое значение находится в регистре EAX. Таким образом, вызов Fact(1) завершился, вернув результат 1 в регистре EAX, который теперь и используется в инструкции умножения. В результате выполнения инструкции
EAX = 00000002
Однако, не совсем ясным остается использование инструкции add с регистром ESP:
00411A61 add esp,4
Данная команда очищает стек от параметров функции, мы уже упоминали тот факт, что параметры в функцию передаются посредством стека, соответственно, при завершении функции стек необходимо почистить – для этого просто смещаем указатель на вершину стека ESP.
Выполним оставшиеся инструкции в функции. Последняя инструкция ret завершает очередной вызов Fact(2), что можно заметить в окне Call Stack:
Factor.exe!Fact(int N=3) Line 5 + 0xc C++
Factor.exe!main() Line 11 + 0x7 C++
Factor.exe!mainCRTStartup() Line 259 + 0x19 C
kernel32.dll!7c816d4f()
ntdll.dll!7c915b4f()
kernel32.dll!7c8399f3()

Теперь мы вернулись в первый, нерекурсивный вызов Fact(3). Указатель текущей инструкции вновь находится на строках:
00411A61 add esp,4
00411A64 imul eax,dword ptr [N]
но в этот раз уже
EAX = 00000002
N = 3

Пошагово выполняем остаток инструкций функции и возврат в вызывающую функцию main(). Теперь у нас:
EAX = 00000006

Осталось рассмотреть теперь совсем немного. Инструкция
00411AC5 add esp,4
как мы уже знаем, очищает верхушку стека от аргумента предыдущего вызова (константы 3). Следующая инструкция:
00411AC8 mov dword ptr [F3],eax
заносит ответ (значение из EAX) в переменную F3.
Для выполнения «return 0;» следующая инструкция:
00411ACB xor eax,eax
заносит 0 в регистр EAX, который снова будет использован в качестве возвращаемого функцией main() значения (c точки зрения исполняющей системы main() – такая же функция, как и любая другая, за исключением того, что с нее начинается выполнение программы, и она так же точно может возвращать значение, которое используется системой в качестве кода завершения; обычно 0 – нормальное завершение).
Наконец, инструкции
00411ACD pop edi
00411ACE pop esi
00411ACF pop ebx
00411AD0 add esp,0CCh
00411AD6 cmp ebp,esp
00411AD8 call @ILT+935(__RTC_CheckEsp) (4113ACh)
00411ADD mov esp,ebp
00411ADF pop ebp
00411AE0 ret
0040102B C3 ret
осуществляет восстановление регистров в их состояние до запуска программы и возврат в исполняющую систему, которая выполнит код, необходимый для корректного завершения программы.

Заключение
В качестве примера был выбран наиболее простой вариант рекурсивной программы, который выполняет минимум действий и лишен каких бы то ни было средств ввода/вывода. Тем не менее, на этом примере мы смогли увидеть изменения, происходящие в стеке при работе рекурсивной программы, а также ознакомиться с некоторыми деталями передачи параметров в вызываемые функции. Кроме того, мы могли убедиться, что при работе рекурсивной функции стек использовался не столь уж расточительно.

Заработок золота, прокачка профессий, тактики, пвп: Блог по WoW. Интересные и нужные статьи, помогающие игроку!