Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 28
Текст из файла (страница 28)
Дело в том, что при каждом рекурсивном вызове процедуры Р выделяется некоторая память для размещения ее переменных. Кроме этих локальных переменных нужно еще сохранять текущее состояние вычислений, чтобы вернуться к нему, когда закончится выполнение новой активации Р и нужно будет вернуться к старой. Мы уже наблюдали подобную ситуацию при разборе процедуры быстрой сортировки в гл. 2. Было обнаружено, что при «наивном» составлении программы из оператора, разделяющего и элементов на две части, и двух рекурсивных вызовов, сортирующих эти две части, глубина рекурсии в худшем случае может приближаться к и.
При разумном изменении процедуры оказалось, что можно ограничить эту глубину !пан. Разница между значениями н и !оп и вполне достаточна для того, чтобы случай, крайне не подходящий для использования рекурсии, превратить в тот, в котором рекурсия вполне практична.
Подобно операторам цикла, рекурсивные процедуры могут привести к бесконечным вычислениям. Поэтому необходимо рассмотреть проблему окончания работы процедур. Очевидно, что для того, чтобы работа когда-либо завершилась, необходимо, чтобы рекурсивное обращение к процедуре Р подчинялось условию В, которое в какой-то момент перестает выполняться. Поэтому более точно схему рекурсивных алгоритмов можно представить так: Р =— И В !Ьеп У (5ь Р] (3.2) дд Когда не нужно иснольеоеать рекурсию 15в 2.2. КОТДА НЕ НУЖНО ИСПОЛЬЗОВАТЬ РЕКУРСИЮ (3.7): (3.6) (3.7) Р= — 11В1(теп(5; Р) Р = (Я; 1! В ((теп Р) Эти схемы естественно применять в тех случаях, когда вычисляемые значения определяются с помощью простых рскуррентных соотношений.
Рассмотрим, например, широко известный пример вычислений факториалов ~; = В: ! = О, 1, 2, 3, 4, 5, ..., 1г = 1, 1, 2, 6, 24, !20, .... (3.8) «Нулевое» число определяется явным образом как )о = 1, а последующие числа обычно определяются рекурсивно — с помощью предшествующего значения: Рю ~1 = (г + 1) ' го (3.9) Эта формула предполагает использование рекурсивного алгоритма для вычисления и-го факториального числа. Если мы введем две переменные! и Р для значений !и 1; на 1-м уровне рекурсии, то увидим, что для перехода к следующему числу в последовательности (3.8) необходимы следующие вычиспения: ! ь== 7+ 1; Г г= 7 е Р (3,10) и, подставив (3.10) вместо 5 в (3.6), мы получаем рекурсивную программу Р=-.)1 I < и 1(топ (7:=7+ 1; Р:=! «Р; Р) 7;=О; Р:=1; Р (3.1 1) Рекурсивнь|е алгоритмы наиболее пригодны в случаях, когда поставленная задача или используемые данные определены рекурсивно.
Но это не значит, что при яаличии таких рекурсивных определений лучшим способом решения задачи непременно является рекурсивный алгоритм. В действительности из-за того, что обычно понятие рекурсивных алгоритмоа объяснялось на неподходящих примерах, в основном и возникло широко распространенное предубеждение против использования рекурсии в программировании и прправнпвание ее к неэффективности. Повлиял на это и тот факт, что широко распространенный язык программирования Фортран запрещает рекурсивное использование подпрограмм и тем самым не допускает рекурсию, даже когда ее применение опра вда ни о. Программы, в которых следует избегать использования рекурсии, можно охарактеризовать следующей схемой, изображающей их строение.
Это схема (3.6) и эквивалентная ей д Ренургненые алгоригмы !в! Первую строку в (3.1!) можно так записать на принятом нами языке программирования Паскаль: ргосеооге Р; Ьея!и !Х Х < и тйеп Ьеа!и Х:= Х + 1. Г;=- Х*Г. Р ево а (3.12) Чаще употребляемая, но эквивалентная, по существу, форма дана в (3.13).
Вместо процедуры здесь вводится так называемая процедура-функция, т. е. некоторая процедура, с которой явно связывается вычисляемое значение. Поэтому функцию можно использовать непосредственно как элемент выражения. Тем самым переменная Г становится излишней, а роль ! выполняет явный параметр процедуры. Хансе!оп Г(Х: !лгедег): !лгеяег; Ьей!п !Х Х > О тйеп Г:= Х Р(Х вЂ” 1) (3,!3) е!ее Г:= 1 евй Совершенно ясно, что здесь рекурсию можно заменить обы и ной итерацией, а именно программой Х:=О; Р;=1; пЫ!еХ< ибо Ьей!п Х:= Х + 1; Г:= Х*Р епй В общем виде программы, соответствующие схемам (3.6) или (3.7),'нужно преобразовать так, чтобы они соответствовали схеме (3.15): Г=(х:=хо, эеЬ!!е Вг!оЯ) (3.! 5) Ханс!!оп ПЬ(л: !лееаег): улгеаег; Ьеа!п !Е и = О тйеп Гй:= О е!яе !Х л = 1 4Ьеп Рй:= 1 е)эо Гй:= Гй(л — Ц + Рй(л-2) опп (3.17) Есть и другие, более сложные рекурсивные схемы, которые можно и должно переводить в итеративную форму.
Примером служит вычисление чисел Фибоначчи, определяемых с помощью рекуррентного соотношения 1!Ь„,г, = ВЬ„+ ВЬ„, для п > О (3.!6) и !)Ь, =1, ВЬе=О. При непосредственном, «лобовом» подходе мы получим программу Ю.2. Когда не нрскно испольвовагь рекурсию 1ББ При вычислении 1)Ь, обращение к функции Г(Ь(п) приводит к рекурсивным активациям этой процедуры.
Сколько раз? Мы можем заметить, что каждое обращение при и ~ 1 приводит к двум дальнейшим обращениям, т. е. общее число обращений растет экспоненциально (см, рис. 3.2). Ясно, что такая программа непригодна для практического использования. Рис 32. 1Б вызовов с1Ь(п) при и = Б. (вычисление х = у)б, длл п > 0) 1:= 1; х:= 1)у:= 0; ттЫ)е г < и йо Ьей(п х:= х; 1:= г' + 1; х:= х + у; у:= х епй (З.18) (Заметим, что три присваивания х, у и а можно выразить всего лишь двумя присваиваниями без использования вспомогательной переменной а: х:= х+ у; у:= х — у.) Итак, вывод таков; следует избегать рекурсии, когда имеется очевидное итеративное решение поставленной задачи. Но это не означает, что всегда нужно избавляться от рекурсии любой ценой. Во многих случаях она вполне применима, как будет показано в следующих разделах этой главы и в последующих главах.
Тот факт, что рекурсивные процедуры можно реализовать на нерекурсивных по сути машинах, говорит о том, что для практических целей любу1о рекурсивную программу можно преобразовать в чисто итеративную. Но это требует явного манипулирования со стеком рекурсий, и эти операции до такой степени заслоняют суть программы, что понять ее становится очень трудно. Следовательно, алгоритмы, которые по своей природе скорее рекурсивиы, чем итеративны, нужно представлять в виде Однако очевидно, что числа Фибоначчн можно вычислять по итеративной схеме, при которой использование вспомогательных переменных х = ЯЬ; и у = ЯЬ; ~ позволяет избежать повторного вычисления одних и тех же значений: 156 3. Рекурсивные алгоритмы рекурсивных процедур. Чтобы лучше понять это, мы предлагаем читателю сравнить программы 2.!О и 2.11.
Оставшаяся часть этой главы посвящена разработке некоторых рекурсивных программ в тех случаях, когда рекурсия полностью оправданна. Кроме того, в гл. 4 и 5 также широко используется рекурсия, если, конечно, структуры данных естественно и очевидно приводят к рекурсивным решениям. З.З. ДВА ПРИМЕРА РЕКУРСИВНЫХ ПРОГРАММ Симпатичный узор на рис. 3.5 состоит нз суперпозицни пяти кривых.
Эти кривые строятся на пснопе некоторого регулярного образца, и предполагается, что пх можно нарисовать с помощью графопостроителя, управляемого вычислительной машиной. Наша задача — найти рекурсивную схему, по которой можно написать программу, управляющую графопостроителем, Рассматривая рисунок, мы обнаруживаем, что н, нт На Рис. З.З. Кривые Гиаьбсрта порвдка 1, л и 3, три наложенные друг на друга кривые и веют форму, показанную на рис.
3.3. Мы обозначаем их через Нь Ни и На. На рисунках видно, что Нты получается соединением четырех Н, вдвое меньшего размера, соответствующим образом повернутых и связанных вместе тремя соединительными линиями. Отметим, что можно считать, что Н, состоит из четырех пустых Ны связанных тремя прямыми лнниямн. Кривая Н, называется кривой Гпльберта !-го порядка в честь его первооткрывателя Д. Гнльберта (1391), Предположич, что у нас имеются следующие основные средства для построения графов: две координаты — переменные х и у, процедура зсгр!ог (устанавливающая перо в точку с координатами х и у) и процедура р!ог (передвигающая перо, которое прн этом чертит прямую из текущей точки в точку, обозначенную х и у). Поскольку каждая криная Н, состоит нз четырех вдвое меньших копий Н; ь то естественно построить процедуру, ри- ргепгаш 11!!Ьегг(р5 оигрш); изобралсение кривых !"альберта порядки огп 1 до и) еопз1 и = 4; ЬО = 512; айаг 1,Ь,х,у,хО,уО: !о!еяег! р!'.
61е о1 и!егег; '1р!огЯе) ргосебпге А(1: !о!еяег)' Ъеп(п 11! > О йеп Ъеп(п Ю(! — 1); х:= х — Ь; р!ог; А(1-1); у:= у — Ь; р!ог; А(1-1); х:= х+Ь; р!ог; б(~ — 1) епй епд; ргосебпге В(1: !огеяег); ЪеП(п11! ) О йеп Ъеа(п С(! — 1); у:= у+Ь; р1ог; З(1 — 1); х:= х+Ь; р!ог; Ж вЂ” 1); у:= у-Ь; р!ог; А(1 — 1) епб епб; ргосебпге С(Ю !я!еяег); Ъеп1п 11 1 > О йеп Ъеп(п З(! — 1); х:= х+Ь; р!ог; С(1 — 1); у:= у+Ь; р!о!! С(! — 1); х:= х — Ь; р!ог; Ю(! — 1) епб епй 1 пгоеейпе Ю(1: !нгегег)! Ъеп(п11 г' > О йеп Ъек(п А(! — 1); у:= у-Ь; р!о!1 Ю(! — 1); х:= х-Ь; р!о1; Р(1 — 1); у: у+Ь; р!ог; С(1 — 1) еа$ еПЬ 1 Ъеп(п згаг!р!ог; 1:= О; Ь:= ЬО1 хО: Ь 41г 2; уО;=хО, гереаг (изображение кривой Пиьберва порядка !) 1: = !+1; Ь: = Ь йг 2; хО:= хО + (Ь йг 2); уО: = уО + (Ь йг 2); х:= ьО; у;= уО; зегр!ог; 168 8.
Рекурсивные алгоритмы А(!) ввб1 т ° и; елыр!о! евд . Программа 3.1. Кривые Гааьоерта. сующую Н» в виде композиции четырех частей, каждая из которых рисует Н; 1 соответствующего размера и с нужным поворотом. Если мы обозначим эти четыре части А, В, С н Р, а подпрограммы, рисующие соединительные линии, — в виде стрелок, указывающих соответствующее направление, то получим следующую рекурсивную схему (см.
рис. 3.3): Г~ А: Ю вЂ” А,)А-+В Г) В: С7В-+В)А 1с: в- с7с -л 1Ю: А1Р» — В~С (3.19) Эта процедура инициируется один раз основной программой для каждой кривой Гильберта, которые накладываются одна на другую, образуя данный рисунок. Основная программа задает исходную точку для кривой, т. е. начальные значения х и у, н единичное приращение Ь. Величина )го соответствует ширине всей страницы и должна удовлетворять равенству ЬО= 2' для некоторого й ) и (см. рис, 3А). Программа рисует всего и кривых Гильберта (см, программу 3.1 и рис. 3.5).
Похожий, но несколько более сложный и эстетически утонченный рисунок приведен на рис. 3.7. Он также получен с помощью наложения нескольких кривых; две такие кривые показаны на рис З.б. Кривая 5; называется кривой Серпинского Ого порядка. Какова рекурсивная схема для такой Если длину соединительной линии обозначить через й, то процедуру, соответствующую схеме А, можно легко выразить с помощью рекурсивных обращений к описанным аналогичным образом процедурам В и Р и самой процедуры А: ртосеивте А(П тгеаег); Ъей1в 1а ! > О тйев Ьеи)в Ю(! — 1); х:= х — Ь; Р!ог) А(1' — 1); У:= У вЂ” Ь; р!от; (3,2О) А(! — 1); х:= х+Д; р!ог; В(г — 1) евв евй 166 Л, Рекурсивные алгоритмы кривой? Попробуем в качестве основного строительного блока выделить лист Вы возможно, без одного ребра. Но это ие приводит нас к нужному решению.
Принципиальное различие мел<ду кривь1ми Серппнского и Гильберта заключается в том, что кривые Серпинского являются замкнутыми (без соединительных линий). Это означает, что основная рекурсивная схема дочжна давать разомкнутую кривую, а четыре части соединяются линиями, не принадлежащими самому рекурсивному узору, Действительно, эти связи представляют собой о1 за Рис, 3.6. Кривые Серпииското порядка ! и 2 четыре прямые в четырех внешних «углах», изображенных на рис. 3.б жирными линиямн. Можно считать, что%ни принадлежат к непустой начальной кривой Во, представляюшей собой квадрат, стояшнй на одном угле.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
