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



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



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

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

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

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

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

фективно организовать рекурсивную процедуру, подобную процедуре обхода дерева LRBeat из главы 2.

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

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

  • способы передачи параметров в процедуру и возврата результатов ее работы;



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