Реализация рекурсивных процедур
Если бы строители строили здания так же, как программисты пишут программы,
первый же залетевший дятел разрушил бы цивилизацию.
Второй закон Вейнберга
(Прикладная Мерфология)
В учебнике достаточно полно был рассмотрен вопрос организации работы с процедурами, но некоторые проблемы остались за кадром. В этой главе мы остановимся на трех из них: реализации рекурсивных и вложенных процедур на ассемблере, а также разработке динамических (DLL) библиотек.
Принимаясь за дело, соберись с духом.
Козьма Прутков
В предыдущей главе, посвященной структурам данных, достаточно интенсивно использовались рекурсивные процедуры. Данный вопрос требует дополнительного пояснения.
Процедура называется рекурсивной, если она прямо или косвенно обращается к себе самой. Рекурсия является естественным свойством для большого числа математических и вычислительных алгоритмов. Важно отметить, что любой рекурсивный алгоритм можно сделать итеративным, но это не всегда целесообразно. В теории программирования рекурсия как правило воспринималась неоднозначно. В конечном итоге была выработана следующая рекомендация – рекурсию следует избегать в случаях, когда имеется очевидное итерационное решение. Как мы убедимся из приведенного ниже обсуждения, очевидная рекурсивная задача вычисления факториала не дает никакого выигрыша в попытке программной реализации с помощью рекурсивных процедур. Настоящий эффект возникает в тех задачах, где рекурсия использована в определении обрабатываемых данных. Такими данными могут являться, например, динамические структуры данных – стеки, деревья, списки, очереди и т. п.
Как показал материал, посвященный структурам данных, это действительно верно. При небольшом усилии в программе на ассемблере можно достаточно эффективно организовать рекурсивную процедуру, подобную процедуре обхода дерева LRBeat из главы 2.
В ассемблере нет средств прямой поддержки рекурсивных алгоритмов, но есть косвенные – нужно только немного подыграть этому процессу. По сравнению с языками высокого уровня, имеющими встроенную поддержку рекурсии, в программе ассемблера все действия по ее организации приходится предусматривать самому программисту. А для этого необходимо иметь представление о процессах, происходящих при рекурсивном вызове процедуры.
Планируя использование рекурсивных процедур, необходимо продумывать следующие вопросы:
- способы передачи параметров в процедуру и возврата результатов ее работы;
- способ сохранения локальных переменных процедуры;
- организацию выхода из процедуры.
Подробно эти вопросы обсуждались в уроке 14 "Модульное программирование" учебника. Но при организации рекурсии они приобретают особый смысл, так как требуется не просто вызвать процедуру, а вызвать ее из себя несколько раз, обрабатывая при каждом вызове свои локальные данные, и в конечном итоге возвратить управление в точку программы, расположенную следом за первым вызовом данной процедуры.
Как правило, для работы с локальными данными процедуры и параметрами, передаваемыми в процедуру, используется стек. При этом необязательно использовать для этого только системный стек, иногда удобнее создать его модель, работу с которой осуществлять средствами самой программы. Пример организации такого программного стека мы использовали при написании программы обхода дерева с рекурсивной процедурой LRBeat.
Рассмотрим характерные моменты рекурсивного вызова процедур на примере классической рекурсивной задачи – вычисления факториала. Вспомним алгоритм вычисления факториала:
F(0)=l: F(i)=ixF(i-1)
Как было отмечено выше, с точки зрения скорости работы кода рекурсивный вариант вычисления факториала неэффективен, его лучше вычислять итеративно в цикле, но в учебных целях этот пример оправдан.
.data r_fact dw 0 .code fact proc push bp nrav bp.sp mov cx.[bp+4] mov ax.ex mul r_fact mov r_fact.ax dec ex jcxz end_p push ex call fact end_p: mov sp.bp