Рекурсивные процедуры

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

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

Для примера рассмотрим рекурсивную процедуру вычисления факториала целого беззнакового числа. Процедура получает параметр через стек и возвращает результат через регистр EAX.

factorial proc

mov eax, [esp + 4]; Заносим в регистр EAX параметр процедуры

test eax, eax; Проверяем значение в регистре EAX

jz L1; Если EAX = 0, то обходим рекурсивную ветвь

dec eax; Уменьшаем значение в регистре EAX на 1

push eax; Кладём в стек параметр для следующего рекурсивного вызова

call factorial; Вызываем процедуру

add esp, 4; Очищаем стек, т.к. процедура использует RET без параметров

mul dword ptr [esp + 4]; Умножаем EAX, хранящий результат предыдущего вызова, на параметр текущего вызова процедуры

jmp L2; Переходим к возврату из процедуры

L1: inc eax; Если EAX был равен 0, записываем в EAX единицу

L2: ret; Возврат из процедуры (без параметров)