3.1. Beedei)!

рераторов Si (не содержащих Р) й,., i лой Р:

P\St,Pf

151-

(3.1).

Необходимое и достаточное средство для рекурсивного рдставления программ - это описание процедур, или под- ограмм, так как оно позволяет присваивать какому-либо !!LpaTOpy имя, с помощью которого можно вызывать этот ператор- Если процедура Р содержит явное обращение к самой себе, то она называется прямо рекурсивной; если Р содержит обращение к процедуре Q, которая содержит (прямо-

Рис. 3.1. Рекурсивное изображение.

или косвенно) обращение к Р, то Р называется косвенно ре-Щрсивной. Поэтому использование рекурсии не всегда сразу видно из текста программы.

С процедурой принято связывать некоторое множество локальных объектов, т. е. переменных, констант, типов и процедур, которые определены локально в этой процедуре, а вне ее не существуют или не имеют смысла. Каждый раз, огда такая процедура рекурсивно вызывается, для нее соз-эется новое множество локальных переменных. Хотя они Имеют те же имена, что и соответствующие элементы множества локальных переменных, созданного при предыдущем Ращении к этой же процедуре, их значения различны. Сле-Ующие правила области действия идентификаторов позво-яют исключить какой-либо конфликт при использовании мен: идентификаторы всегда ссылаются на множество пе-нных, созданное последним. То же правило относится к

арам,

етрам процедуры.

или

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

P=iffithen[Si, Р] (3..

P = [Sf, If В thenР] (33

Основной способ доказать, что выполнение операторО| цикла когда-либо заканчивается, - определить функцию (х - множество переменных программы), такую, что f(jt;)l удовлетворяет условию окончания цикла (с предусловием щ, с постусловием), и доказать, что при каждом повторении уменьщается. Точно так же можно доказать, что вьшолненц, рекурсивной процедуры Р когда-либо заверщится, показав' что каждое выполнение Р уменьшает /(л;). Наиболее наце , ный способ обеспечить окончание процедуры - связать с f параметр (значение), скажем п, и рекурсивно вызывать f; со значением этого параметра п-1. Тогда замена условия J ял п > О гарантирует окончание работы. Это можно изобра .знть следующими схемами программ:

P(n)=lfn>Othen[S£, Р(и-1)] (3.i

P(n) = [Si, Ifn>OthenP(и-1)] (3.5

На практике нужно обязательно убедиться, что наиболь щая глубина рекурсии не только конечна, но и достаточш мала. Дело в том, что при каждом рекурсивном вызове проч цедуры Р выделяется некоторая память для размещения переменных. Кроме этих локальных переменных нужно ещ сохранять текущее состояние вычислений, чтобы вернуться к нему, когда закончится выполнение новой активации РА нужно будет вернуться к старой. Мы уже наблюдали подо ную ситуацию при разборе процедуры быстрой сортиров в гл. 2. Было обнаружено, что при наивном составлени программы из оператора, разделяющего п элементов на Д^ части, и двух рекурсивных вызовов, сортирующих эти Д^ части, глубина рекурсии в худшем случае может приближат' ся к п. При разумном изменении процедуры оказалось, можно ограничить эту глубину log п. Разница между знач пнями п и log и вполне достаточна для того, чтобы случ крайне не подходящий для использования рекурсии, превр^ тить в тот, в котором рекурсия вполне практична.

3.2. Когда не нужно использовать рекурсию \5S

когда не нужно использовать рекурсию

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

Программы, в которых следует избегать использования рекурсии, можно охарактеризовать следующей схемой, изображающей их строение. Это схема (3.6) и эквивалентная ей (3.7):

Piffithen(S; Р) (3.6>

P = (S; IffithenP) (3.7).

Эти схемы естественно применять в тех случаях, когда вычисляемые значения определяются с помощью простых рекуррентных соотношений. Рассмотрим, например, широко известный пример вычислений факториалов fi = i\:

t = 0, 1, 2, 3, 4, 5.....

/,= 1. 1, 2, 6, 24, 120,...... (-

Нулевое число определяется явным образом как fo=l, а последующие числа обычно определяются рекурсивно - с помощью предшествующего значения:

/i-M = ( + l)-/i- (3.9>

Эта формула предполагает использование рекурсивного алгоритма для вычисления и-го факториального числа. Если мы введем две переменные / и Р для значений / и ft на i-m уровне Р^урсии, то увидим, что для перехода к следующему числу * последовательности (3.8) необходимы следующие вычис- ения:

/:=/-Ь1; Р:=/*Р (3.10>

й> подставив (3.10) вместо S в (3.6), мы получаем рекурсив-УК) программу

Plf /<п then (/:=/-}- 1; Р:=У*Р; Р) у. 0;Р:=1;Р (3.11).