Главная  Терминология Хоора 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 [ 50 ] 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133

Первую строку в (3.11) можно так записать на принято .нами языке программирования Паскаль:

procedure Р; .

begin if J < и then

begin / := / + !;/-:= I*F; P {Щ

Чаще употребляемая, но эквивалентная, по существу, фор ма дана в (3.13). Вместо процедуры здесь вводится так на. зываемая процедура-функция, т. е. некоторая процедура с которой явно связывается вычисляемое значение. Поэтому функцию можно использовать непосредственно как элемент выражения. Тем самым переменная F становится излишней, а роль / выполняет явный параметр процедуры. ,

function F{I: integer): integer; begin if / > 0 then F :== - I) /3 ,

else F := 1

Совершенно ясно, что здесь рекурсию можно заменить обычной итерацией, а именно программой

/:= 0; F:= 1; while / < и do

begHi/:=/+ 1;F у'

В общем виде программы, соответствующие схемам (3.6) или (3.7), нужно преобразовать так, чтобы они соответствовали схеме (3.15): i Р = (х:=Хо; while В do S) (3.15)

Есть и другие, более сложные рекурсивные схемы, которые можно и должно переводить в итеративную форму. Примером служит вычисление чисел Фибоначчи, определяемы)! с помощью рекуррентного соотношения

fib ., = fib -f fib i для п>0 (3.16)

и fibi = l, fibo = 0. При непосредственном, лобовом подходе мы получим программу

function integer): integer;

begin if и = 0 then Fib := 0 else

if и = 1 then Fib := 1 else (3.17) I

Fib := Л6(и-1) -f Л&(в-2)

сна




rjpH вычислении fib обращение к функции Fib{n) приво-к рекурсивным активациям этой процедуры. Сколько Мы можем заметить, что каждое обращение при п > 1 Р^родит к двум дальнейшим обращениям, т. е. общее число Ррдщений растет экспоненциально (см. рис. 3.2). Ясно, что а^ая программа непригодна для практического использо-.


1 вызовов Fib{n) при п == 5.

Однако очевидно, что числа Фибоначчи можно вычислять по итеративной схеме, при которой использование вспомогательных переменных х ~ fib; и у = fib, i позволяет избежать повторного вычисления одних и тех же значений:

[вычисление X = fib для и > 0) i I; X I; у:= 0; while i < и do

begin z := x; i := i + 1;

X := X + y; у := 2

(3.18)

(Заметим, что три присваивания х, у и z можно выразить всего лишь двумя присваиваниями без использования вспомогательной переменной г: х:=х-\-у; у:=х - у.)

Итак, вывод таков: следует избегать рекурсии, когда имеется очевидное итеративное решение поставленной задачи.

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

Рограммы, что понять ее становится очень трудно. Следова-льно, алгоритмы, которые по своей природе скорее рекур-

ивны, чем итеративны, нужно представлять в виде



рекурсивных процедур. Чтобы лучше понять это, мы пред. гаем читателю сравнить программы 2.10 и 2.11.

Оставшаяся часть этой главы посвящена разработке ц которых рекурсивных программ в тех случаях, когда реку сия полностью оправданна. Кроме того, в гл. 4 и 5 также щ роко используется рекурсия, если, конечно, структуры да ных естественно и очевидно приводят к рекурсивным рец1 ниям. \

3,3. два примера рекурсивных программ

Симпатичный узор на рис. 3.5 состоит из суперпозиции пяти кривых. Эти кривые строятся на основе некоторого ре. гулярного образца, и предполагается, что их можно нарисо-вать с помощью графопостроителя, управляемого вычислительной машиной. Наша задача -найти рекурсивную схему, по которой мО,?кно написать программу, управляющую графопостроителем. Рассматривая рисунок, мы обнаруживаем, что


Н

1 2 пз

Рис. 3.3. Кривые Гильберта порядка 1, 2 и 3.

три наложенные друг на друга кривые имеют форму, показанную на рис. 3.3. Мы обозначаем их через Ни Яд и Яз. рисунках видно, что Hi+i получается соединением четырех Hi вдвое меньшего размера, соответствующим образом повернутых и связанных вместе тремя соединительными линиями. Отметим, что можно считать, что Hi состоит из четырех пустых Но, связанных тремя прямыми линиями. Кривая Я, называется кривой Гильберта i-го порядка в честь его первс открывателя Д. Гильберта (1891).

Лредположик. что у нас имеются следующие основные средства для построения графов: две координаты - перемеН' ные X к у, процедура setplot (устанавливающая перо в точ ? с координатами х я у) и процедура plot (передвигаюша перо, которое при этом чертит прямую из текущей точки точку, обозначенную х к у).

Поскольку каждая кривая Hi состоит из четырех вдво-меньших копий Я,- 1, то естественно построить процедуру, Р




1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 [ 50 ] 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133