Реализация рекурсивных процедур
Реализация рекурсивных процедур
Принимаясь за дело, соберись с духом. Козьма Прутков
В предыдущей главе, посвященной структурам данных, достаточно интенсивно использовались рекурсивные процедуры. Данный вопрос требует дополнительного пояснения.
Процедура называется рекурсивной, если она прямо или косвенно обращается к себе самой. Рекурсия является естественным свойством для большого числа математических и вычислительных алгоритмов. Важно отметить, что любой рекурсивный алгоритм можно сделать итеративным, но это не всегда целесообразно. В теории программирования рекурсия как правило воспринималась неоднозначно. В конечном итоге была выработана следующая рекомендация — рекурсию следует избегать в случаях, когда имеется очевидное итерационное решение. Как мы убедимся из приведенного ниже обсуждения, очевидная рекурсивная задача вычисления факториала не дает никакого выигрыша в попытке программной реализации с помощью рекурсивных процедур. Настоящий эффект возникает в тех задачах, где рекурсия использована в определении обрабатываемых данных. Такими данными могут являться, например, динамические структуры данных — стеки, деревья, списки, очереди и т. п.
Как показал материал, посвященный структурам данных, это действительно верно. При небольшом усилии в программе на ассемблере можно достаточно эф-
фективно организовать рекурсивную процедуру, подобную процедуре обхода дерева 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. Попробуйте самостоятельно исправить этот «дефект».
