Var X:Integer;

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;

Begin

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

End;

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

Var j : integer; Buf: Char;

Begin

{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)

End.

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

Program All_permutations;

Const n = 4;

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