Case n of

Begin

End.

P(n)

Begin

End

Begin

Begin

Begin

End.

Begin

Begin

Begin

x:= 0;

... E(M);...

Write(x); {На экран будет выведен 0}

x:= 1

end;

Параметры (параметры-значения) рекурсивной процеду­ры (функции) формируют свои новые зна­че­ния в момент рекурсивного вызова. Эти значения передаются в новую копию рекурсивной процедуры. При возврате из рекурсии параметры-значения восста­нав­ливают свои прежние значения.

Параметры - переменные по существу передают в новую копию рекурсивной процедуры свои имена. Поэтому при выходе из рекурсии их значения определяются в той копии, из которой произошел выход.

Пример 5. Перестановки. Сгенерировать (распечатать) все переста­новки элементов конечной после­до­вательности, состоящей из первых N букв латинского алфавита и найти их количество.

Решение

Сведем задачу к нескольким подзадачам, более простым, чем исходная.

Пусть S = [ s₁, s₂,..., s_n ] - конечный набор символов.

Через P(S) обозначим множество всех перестановок S, a через P(S,i) - множество всех перестановок, в которых на последнем месте стоит элемент s_i. Тогда

P(S) = P(S,n) È P(S, n-1) È... È P(S,1)

Элемент множества P(S, i) имеет вид [s_j2,..., s_jn, s_i], где j2,..., jn - всевозможные перестановки индексов, не равных i. Поэтому

P(S, i) = (P(S \ s_i), s_i) и P(S)=(P(S \ s₁),s₁)È...È (P(S \ s_n), s_n).

Полученное соотношение выражает множество P(S) через множества перестановок наборов из (n-1) символа. Дополнив это соотношение определением P(S) на одно­эле­ментном множестве, получим:

1. P({s}) = {s}

2. P(S) = (P(S\s₁), s₁) È... È (P(S\s_n), s_n)

Уточним алгоритм, опираясь на представление S в виде массива S[1..n] of char.

Во первых, определим параметры процедуры P:

k - количество элементов в наборе символов;

S - набор переставляемых символов.

Алгоритм начинает работу на исходном наборе и генерирует все его перестановки, оставляющие на месте эле­мент s[k]. Если множество перестановок, в которых на последнем месте стоит s[j], уже порождено, меняем местами s[j-1] и s[k], выводим на печать полученный набор и применяем рекурсивно алгоритм к этому набору. Параметр k управляет рекурсивными вычи­сле­ни­ями: цепочка вызовов процедуры P обрывается при k=1.

Program Permutations; {Все перестановки множества S}

Const N = 10;

Type Sequence = array [1..N] of Char;

Var S: Sequence;

Ch: Char;

Proсedure WriteSequence (Var A: Sequence);

{вывод на печать перестановки массива}

Var i: Integer;

{Блок вывода массива А на экран}

End;

Procedure P(k: Integer; Q: Sequence);

Var j: integer; Buf: Char;

{Count:= Count + 1;}

if k<>1 then P(k-1, Q);{ Рекурсивный вызов Р}

{Все перестановки с элем. S[k] на последнем месте}

For j:= k - 1 downto 1 do begin

Buf:= Q[j]; Q[j]:= Q[k]; Q[k]:= Buf;

{Меняем местами S[j] и S[k]}

WriteSequence(Q); {Печать очередной перестановки}

P(k - 1, Q) {Рекурсивный вызов Р}

end {Все перестановки с S[j] на последнем месте}

End;

Begin {Раздел операторов программы}

For Сh:= ‘a’ to Chr(Ord(‘a’)+N) do S[Ch]:= Ch;

{Генерация исходного массива S}

WriteSequence(S); {Печать исходной перестановки }

Count:= 0; {Счетчик количества вызовов процедуры P}

P(N, S); {Вызов P из основной программы}

Write(‘ Count = ’, Count)

Рассмотрим другой вариант этого алгоритма. Используем S как глобальную перемен­ную. Тогда при вызове P S будет изменяться. Следовательно, при выходе из рекурсии массив S нужно восстанавливать, используя обратную перестановку!

Program All_permutations;

Const n = 4;

Type Sequence = array[1..n] of char;

Var S: Sequence;

Buf: char; i: Integer;

Procedure WriteSequence;

For i:= 1 to n do Write(S[i]); Writeln

end;

Procedure P(k: Integer);

Var j: integer;

Procedure Swap(i, j: Integer);

Buf:= S[j]; S[j]:= S[i]; S[i]:= Buf

end;

if k > 1 then P(k - 1);

For j:= k - 1 downto 1 do begin

Swap(j, k); {Прямая перестановка}

WriteSequence; P(k - 1);

Swap(k, j) {Обратная перестановка}

End;

{Генерация исходного набора S}

WriteSequence;

Важнейшую роль в реализации рекурсивных алгоритмов играет контроль выхода из рекурсии (ее окончания).

Если не предусмотреть выхода из рекурсии, цепочка рекур­сивных вызовов станет (теоретически) бесконечной. На практике это приведет к переполнению той части памяти компьютера, в которой рекурсия реализуется.

Рекурсивный алгоритм всегда имеет так или иначе реализованное условное ветвление, одна или несколько ветвей которого - нерекурсивные действия, а другая (другие) - рекурсив­ный вызов. Логическое значение условия, управляющего этим ветвлением, зависит от параметров рекур­сии.

При определенных значениях параметров алгоритм не вызывает новую рекурсивную копию, а выполняет нерекурсивные действия, тем самым обрывая цепочку рекурсивных вызовов. Эти нерекурсивные действия будем называть базисом рекурсии. Вторую ветвь естест­венно назвать шагом рекурсии, а условие - условием рекурсии.

В примере 2 это ветвление имеет вид

If n = 1 {условие рекурсии}

then F:= 1 {базис рекурсии}

else F:= F(n - 1) * n {шаг рекурсии}

В примере 3 это выглядит так:

If x <> y { условие рекурсии }

Then If x < y { шаг рекурсии }

then GCD:= GCD(x, y - x)

else GCD:= GCD(x - y, y)

Else GCD:= x { базис рекурсии }

В примере 3 ветвление реализовано оператором Case.

В примере 4 выбор управляется условием k > 1, а вет­вле­ние реализовано с помощью арифметического цикла, который не исполнится, если k <= 1. Базис рекурсии вырожден: при выходе из рекурсии никакие действия не выполняются.

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

Аналогично будет выглядеть полная картинка рекур­сив­ных вызовов в примере 2. Нарисуем ее при исходных значениях параметров x = 26, y = 16. { НОД(26, 16) }

Линейность картинки рекурсивных вызовов обусловлена тем, что в соответствующей рекурсивной функции возможен только один рекурсивный вызов.

Если в рекурсивной фун­к­­ции (процедуре) возможны два и более вызовов, осуществляемых последовательно, полная картинка рекурсии будет ветвящейся.

Пример 6. Последовательность Фибоначчи. Требуется построить алгоритм вычи­сле­ния n-того числа последова­тель­нос­ти F(n), определенной рекурсивными соотно­ше­ниями:

F(0) = F(1) = 1; F(n+2) = F(n+1) + F(n).

Переведя определение F(n) на Паскаль, получим:

Function F(n: Integer): Integer;

0,1: F:= 1

else F:=F(n-1)+F(n-2) {Два последовательных вызова}

Дата добавления: 2014-01-06