Сборник по задачам и примерам 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.




    Содержание  Назад  Вперед