Главная Промышленная автоматика.

begin

p:= FIRST (M) ;

whill p <> END (M) do begin

if RETRIEVE(p, M) .domain = d then begin r:= RETRIEVE (p, M) .range; return(true >

end;

p:= NEXT(p, M)

end;

retum(false) { d не принадлежит области определения } end; { COMPUTE }

2.6. Стеки и рекурсивные процедуры

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

Рекурсивные вызовы процедур упрощают структуру многих программ. Но в некоторых языках программирования процедурные вызовы более "дорогие" (по времени выполнения), чем непосредственное выполнение операторов, поэтому программа может работать быстрее, если из нее исключить рекурсивные процедуры. Здесь мы не выступаем в поддержку обязательного исключения рекурсивных или каких-либо иных процедур, очень часто структурная простота программы важна не менее, чем ее малое время выполнения. На практике бывают ситуации, когда после реализации части программного проекта возникает необходимость исключить рекурсию, и основная цель этого обсуждения заключается только в том, чтобы подвести к вопросу о том, как можно преобразовать рекурсивную процедуру в нерекурсивную с помощью стеков.

Пример 2.3. Рассмотрим рекурсивное и нерекурсивное рещения упрощенной версии классической задачи о ранце, где мы имеем целевое значение t и конечное множество положительных целых весов Wi, W2, , w„. Необходимо определить, можно ли из множества весов выбрать такой их набор, чтобы их сумма точно равнялась величине /. Например, если / = 10 и множество весов составляют числа 7, 5, 4, 4 и 1, то можно выбрать второй, третий и пятый веса, поскольку 5 -i- 4 -i- 1 = 10.

В листинге 2.14 представлена функция knapsack (ранец), работающая с массивом весов weights: яггяу[1..п] of integer. Функция knapsack{s, i) определяет, существует ли набор весов из множества весов от weights[t]ii.o weights[n], сумма которых равна s, и если есть, то печатает этот набор весов. В частном случае, когда s = О, пустое множество весов считается рещением. Если s < О или / > и (выход за заданное множество весов), то считаем, что рещение не существует или не найдено (функция knapsack возвращает значение false).

Если ни один из перечисленных случаев к текущей ситуации не применим, то снова вызывается knapsack(s - Wj, \ + 1), чтобы посмотреть, существует ли рещение, которое включает вес w,. Если в этом случае рещение существует, то оно является и рещением исходной задачи; это рещение, включая Ш(, распечатывается. Если рещения нет, то вызывается функция knapsack(s, / + 1) для поиска рещения без участия веса Ш(. П



Листинг 2.14. Рекурсивное решение задачи о ранце

function knapsack ( target: integer; candidate: integer) :boolean; begin

(1) if target:= 0 then

(2) return(true)

(3) else if (target < 0) or (candidate > л) then

(4) retum(false)

else { ищется решение с и без candidate }

(5) if knapsack(.target-weights[candidate] candidate+Dthen

begin

(6) writelnlweightslcandidate]) ;

(7) return (true) end

else { возможное решение без candidate }

(8) retum(JcnapsacA:( target, candidate + 1)> end; { knapsack )

Исключение „концевых" рекурсий

Часто можно чисто механически исключить последний вызов процедуры самой себя. Если процедура Р(х) на последнем шаге вызывает Р(у), то этот вызов можно заменить оператором присваивания х := у и последующим переходом в начало кода процедуры Р. Здесь у может быть выражением, а х должно принимать значение, т.е. это значение хранится в локальной переменной. Если процедура имеет несколько параметров, то с ними надо поступить точно так же, как описано для х и у.

Описанная схема вызывает повторное выполнение процедуры Р с новым значением параметра х с точно таким же конечным эффектом, какой был бы при рекурсивном вызове Р(у) и возврате из этого вызова. Отметим, что тот факт, что некоторые локальные переменные процедуры Р принимают новые значения, не имеет последствий, поскольку процедура уже не должна использовать старых значений этих переменных.

Подобный вариант исключения рекурсивного вызова можно проиллюстрировать на примере листинга 2.14, где последний шаг функции knapsack возвращает результат рекурсивного вызова без параметров. В такой ситуации также можно заменить вызов операторами присваивания значений параметрам и переходом в начало кода функции. В данном случае строку (8) в листинге 2.14 можно заменить следующими операторами:

candidate: = candidate + 1; goto beginning

где beginning (начало) - метка на оператор строки (1). Отметим, что параметр target не переприсваивается, так как сохраняет старое значение. Поэтому проверки его значения в строках (1) и (3) фактически не нужны, необходимо только проверить условие, что candidate > п в строке (3).

Полное исключение рекурсий

Описанная выше техника исключения рекурсивных вызовов полностью удаляет рекурсии только тогда, когда рекурсивные вызовы находятся в конце процедур и вызов осуществляется в форме, позволяющей его исключить. Существует более общий подход, позволяющий преобразовать любую рекурсивную процедуру (или функцию) в нерекурсивную, но этот подход вводит определяемые пользователем стеки. В общем случае этот стек хранит следующее.

1. Текущие значения параметров процедуры.



2. Текущие значения всех локальных переменных процедуры.

3. Адрес возврата, т.е. адрес места, куда должно перейти управление после завер-щения процедуры.

В случае функции knapsack положение упрощается. Во-первых, заметим, что при всех вызовах (при этом происходит вставка записи в стек) параметр candidate увеличивается на единицу. Поэтому мы можем хранить значение candidate как глобальную переменную, значение которой увеличивается на единицу при вставке записи в стек и уменьщается на единицу при извлечении записи из стека.

Во-вторых, следующее упрощение можно сделать, если в стеке хранить модифицированный адрес возврата. Отметим, что адрес возврата для этой функции может находиться или в другой процедуре, вызвавщей knapsack, или в строке (5), или в строке (8). Можно представить эти три возможности с помощью "статуса", который может принимать три значения.

1. попе (нет). Показывает, что вызов осуществлен из внещней процедуры.

2. included (включенный). Указывает на вызов из строки (5), которая включает вес weights[candidate]e возможное рещение.

3. excluded (исключенный). Указывает на вызов из строки (8), которая исключает вес weights[candidate]m возможного рещения.

Если мы сохраним статус как адрес возврата, то сможем рассматривать target как глобальную переменную. При изменении статуса с попе на included мы вычитаем вес weights[candidate] из target и прибавляем его обратно при изменении статуса с included на excluded. Чтобы показать, что рекурсивно вызываемой knapsack найдено рещение, используем глобальную переменную wtnflag{(\!П&т победы). Получив один раз значение true, winflag сохраняет это значение, из стека извлекаются записи, и те веса, которые имеют статус included, распечатываются. В описанной ситуации стек можно объявить как список статусов (statuses) следующим способом:

type

statuses = (поле, included, excluded) ; STACK = { подходящее объявление стека }

В листинге 2.15 приведена нерекурсивная процедура knapsack, оперирующая с массивом весов weights. Хотя эта процедура может выполняться быстрее, чем исходная рекурсивная функция knapsack, но видно, что код ее длиннее и она труднее для понимания. Поэтому исключение рекурсий следует применять только тогда, когда скорость выполнения программы является решающим фактором.

Листинг 2.15. Нерекурсивная процедуралэраэс

procedure knapsack ( target: integer ) ; var

candidate: integer ; winflag: boolean; S: STACK; begin

candidate:- 1; winflag:= false; MAKENULL is); PUSH (none, S) ;

{ инициализация стека для рассмотрения weig/]ts[l] } repeat

if winflag then begin

{ извлечение записи из стека и

печать весов, входящих в рещение } if TOp(S) = included then

2.6. СТЕКИ И РЕКУРСИВНЫЕ ПРОЦЕДУРЫ 71





0 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

0.002