Var s : Sequence;

Buf : char; i : Integer;

Procedure WriteSequence;

begin

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

end;

Procedure P(k : Integer);

Var j : integer;

Procedure Swap(i, j : Integer);

begin

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

end;

Begin

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

End;

Begin

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

WriteSequence;

P(n)

End.

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

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

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

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

В примере 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;

Begin

Case n of

0,1: F := 1

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

end

End;

Тело функции F содержит два рекурсивных вызова, выпол­няемых последовательно. Поэтому полная картинка рекурсии имеет вид дерева! Построим ее при n = 5.

Каждая рекурсивная копия, если ее параметр k >= 2, вызывает две новых копии. Полная картинки вызовов имеет вид дерева, из каждого ветвления которого выходят две ветви. (с параметрами k-1, k-2).

В каждый момент времени в памяти компьютера хранится только один путь - тот, который соответствует состоянию процесса вычислений.

В памяти компьютера, отведенной под рекурсивные вычисления, хранятся те копии, путь через которые лежит к исполняемой.

Время исполнения этого алгоритма пропорционально обще­му числу рекур­сивных копий,

Максимальная память, требу­е­мая для хранения данных, пропор­цио­нальна длине макси­мального пути - от первой копии до копии нижнего уровня.

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