Сборник по задачам и примерам Assembler

             

Реализация рекурсивных процедур



Реализация рекурсивных процедур

Принимаясь за дело, соберись с духом. Козьма Прутков

В предыдущей главе, посвященной структурам данных, достаточно интенсивно использовались рекурсивные процедуры. Данный вопрос требует дополнительного пояснения.

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

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

фективно организовать рекурсивную процедуру, подобную процедуре обхода дерева 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

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

    fact ргос

    push bp mov bp.sp mov cx.[bp+4]

    Смысл этого фрагмента легче понять, наблюдая поведение программы вычисления факториала в отладчике. Как сказано выше, перед вызовом процедуры в стек помещаются данные (или указатель на них), информация о местонахождении которых должна быть сохранена в интересах как вызывающей, так и вызываемой процедуры. В нашем случае в процедуру fact передается переменная факториала. После этого производится вызов процедуры, в результате чего в стек помещается адрес возврата. В вызванной процедуре к данным переменным необходимо получить доступ. Для этого предназначен регистр ВР. Перед использованием его содержимое должно быть также сохранено в стеке. Для первого вызова его значение несущественно. В этот момент весь предыдущий контекст работы программы сохранен. Команда mov bp.sp загружает в регистр ВР указатель на текущую вершину стека, после чего можно обращаться к данным, переданным в процедуру. По сути, сейчас мы с вами сформировали кадр стека. Следующий рекурсивный вызов этой функции придает действию сохранения регистра ВР особый смысл. Команда push bp сохраняет в стеке адрес кадра стека для предыдущего вызова рекурсивной процедуры. Теперь для выхода из процедуры достаточно выполнить приведенные ниже команды эпилога, позволяющие корректно отработать обратную цепочку возврата в основную программу: будет рассмотрена в этой главе ниже. Далее сравним работу функций DrawPattern i и DrawPattern 1.



    Вызов функции DrawPattern_1 из основной программы осуществляется следующим фрагментом кода (полный текст приведен в в каталоге программ для данной главы).

    :prg3_1.asm - фрагмент оконного приложения, вызывающего рекурсивную процедуру :DrawPattern_l

    объявление пользовательских процедур (из maket_dll.DLL) extrn DrawPattern_l:PROC extrn DrawPattem_2:PR0C

    .data

    определение констант для фигуры "Узор из окружностей"

    р dd 5 ;порядок узора

    г dd 60 :радиус окружности

    y_Pdd 140 начальная у-координата центра окружности

    х_Р dd 200 начальная х-координата центра окружности

    .code

    обработка сообщений от меню

    MenuProc proc

    arg (a@hwnd: DWORD. №wparam: DWORD, @(ahdc: DWORD.@@hbrush: DWORD

    uses eax.ebx

    mov ebx.@@wparam :в Ьх идентификатор меню

    onpbx.IDMJ)LL_LACESJ je @@idmdlllaces_l cmpbx.IDM_DLLJ_ACES_2 je @@idmdlllaces_2 jmp@@exit

    e@1 chndl 11 aces_l:

    ;рисуем узор из окружностей, рекурсивная функция для рисования находится

    ;в DLL-библиотеке:

    ;DrawPattern_l(hwnd.hdc,x.y.r.p) - функция не работает с локальными переменными:

    push p :порядок узора

    push г :радиус окружности

    push y_P :у-координата центра окружности

    push x_P ;х-координата центра окружности

    push memdc :контекст устройства

    push @@hwnd

    call DrawPattern_l

    jmp@@exit :.........

    Фрагмент файла maket_dll.DLL, содержащий процедуру DrawPattern_l, приведен ниже:

    iinaket_dn.DLL - фрагмент DLL-библиотеки, содержащей рекурсивную процедуру DrawPatternJ

    объявление процедур DLL-библиотеки общедоступными publicdll WriteCon publicdll DrawPatternJ publicdll DrawPattern_2

    .code DrawPatternJ proc

    :DrawPattern_l - рекурсивная процедура рисования узора :(без использования локальных переменных)

    arg @@hwnd:dword.@@hdc:dword.@@x:dword.@@y:dword.@@r:dword.@@p:dword

    :рисуем окружность

    :рекурсивно вызываем DrawPattern_l(hwnd.hdc,x.y.r,p)

    :BOOL Ellipse(HDC hdc. int nLeftRect. int nTopRect. int nRightRect.int nBottomRect):

    :готовим параметры в стеке для вызова Ellipse

    call Ellipse:рисуем окружность :и еще четыре меньшего порядка



    dec @@p

    стр @@р, 0

    je @@End_Draw

    shr@@r,l -.делим на 2

    :готовим параметры в стеке для вызова DrawPatternJ

    call DrawPattern_l :готовим параметры в стеке для вызова DrawPattern_l

    call DrawPatternJ :готовим параметры в стеке для вызова DrawPatternJ

    call DrawPattern_l :готовим параметры в стеке для вызова DrawPatternJ.

    call DrawPatternJ

    @@End_Draw:

    генерация сообщения WM_PAINT для вывода изображения на экран

    call InvalidateRect endp DrawPatternJ

    Такой вариант процедуры не требует внимания к параметрам, которые пере-, даются в стеке при вызове рекурсивной процедуры, так как после возврата из [ нее они попросту не нужны и удаляются из стека. Но стоит нам в процедуре DrawPattern изменить порядок обращения к процедуре Ellipse, как ситуация резко меняется. Рассмотрим второй вариант организации процедуры DrawPattern.

    VOID DrawPattern (HWND hwnd.HDC hdc.INT_DWORD x.INT_DWORD y.INTJMRD r,INT_DWORD p)

    //DrawPattern - рекурсивная процедура DrawPatten (вариант 2) вывода на экран узора

    //из окружностей на псевдоязыке (фрагмент)

    //Вход: х и у - координаты центра окружности; г - радиус окружности:

    //р - порядок узора, hwnd - дескриптор окна. HDC - контекст устройства.

    ПЕРЕМЕННЫЕ

    HWND hwnd: HDC hdc;

    INT_DWORD hdc. x. y. r.p

    НАЧ_ПРОГ

    ЕСЛИ (р) ТО //пока р*0

    НАЧ_БЛОК_1

    //рисуем еще четыре окружности по с центрами по краям этой DrawPattern (hwnd. hdc. х-г. у. г, р-1) DrawPattern (hwnd. hdc. х. у-г. г. р-1) DrawPattern (hwnd. hdc. х+г. у, г, р-1) DrawPattern (hwnd. hdc. х. у+г. г. р-1)

    //Ellipse - функция Win32 API для вывода эллипса (окружности), вписанного //в прямоугольник (квадрат) с координатами правого верхнего угла (x_up. y_up) //и левого нижнего угла (x_low. y_low):

    //Ellipse(HDC hdc. INT_DW0RD x_up. INT_DWORD y_up. INTJMJRD x_low. INT_DWORD yjow) //так как для рисования нужны координаты прямоугольника, а не центра окружности, //то преобразуем их при вызове Ellipse: .

    Ellipsethdc. x_up-r. y_up-r. x_low+r, y_low+r)

    КОН_БЛОК_1 КОН_ПРОГ

    Если в первом варианте процедуры DrawPattern — DrawPatternl окружности рисовались перед очередной рекурсивной передачей управления в процедуру DrawPattern, то во втором варианте это делается в последнюю очередь — во время обратного хода по цепочке вызовов процедуры DrawPattern. Это уже требует наличия локальных переменных в процедуре и их сохранения на период пока осуществляются рекурсивные вызовы процедуры DrawPattern. Приведем соответствующие фрагменты основной программы и функции DrawPattern_2 из DLL-библиотеки maket dll.DLL

    Из этого фрагмента хорошо видно, в чем разница между размещением параметров, передаваемых в рекурсивную процедуру, и локальными переменными этой процедуры. Для доступа к параметрам используются положительные смещения относительно адреса в ВР (это скрыто от нас с помощью директивы ARG), а для доступа к локальным параметрам — отрицательные смещения.

    Разница в изображениях возникла из-за разных мест в программе, где вызывается функция InvalidateRect. Попробуйте самостоятельно исправить этот «дефект».

     

    Содержание раздела