Сборник по задачам и примерам Assembler
Реализация рекурсивных процедур - часть 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
В общем-то ничего необычного в этом коде нет. Передача параметров в рекурсивную процедуру производится через стек. При этом необязательно все данные помещать в стек. Возможен вариант, когда локальные данные определяют в сегменте данных или в выделенной динамической области памяти, а в стек помещается только указатель на них. В любом случае, начало рекурсивной процедуры будет содержать код пролога, подобный приведенному в программе выше:
fact ргос
push bp mov bp.sp mov cx.[bp+4]
Смысл этого фрагмента легче понять, наблюдая поведение программы вычисления факториала в отладчике. Как сказано выше, перед вызовом процедуры в стек помещаются данные (или указатель на них), информация о местонахождении которых должна быть сохранена в интересах как вызывающей, так и вызываемой процедуры. В нашем случае в процедуру fact передается переменная факториала. После этого производится вызов процедуры, в результате чего в стек помещается адрес возврата. В вызванной процедуре к данным переменным необходимо получить доступ. Для этого предназначен регистр ВР. Перед использованием его содержимое должно быть также сохранено в стеке. Для первого вызова его значение несущественно. В этот момент весь предыдущий контекст работы программы сохранен. Команда mov bp.sp загружает в регистр ВР указатель на текущую вершину стека, после чего можно обращаться к данным, переданным в процедуру. По сути, сейчас мы с вами сформировали кадр стека. Следующий рекурсивный вызов этой функции придает действию сохранения регистра ВР особый смысл. Команда push bp сохраняет в стеке адрес кадра стека для предыдущего вызова рекурсивной процедуры. Теперь для выхода из процедуры достаточно выполнить приведенные ниже команды эпилога, позволяющие корректно отработать обратную цепочку возврата в основную программу: будет рассмотрена в этой главе ниже. Далее сравним работу функций DrawPattern i и DrawPattern 1.
