infa_1 / 11.Рекурсивный подход в программировании

11.Рекурсивный подход в программировании.

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

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

Если некоторая процедура Р содержит явную ссылку на саму себя, то ее называют прямо рекурсивной, а если Р ссылается на другую процедуру Q, содержащую вызов Р, то Р называется косвенно рекурсивной.

Пример: Напечатать все возможные перестановки из n различных объектов.

, , ..., - объекты

Пусть объекты совпадают со своим номером i. Т.е. нужно сгенерировать таким образом все возможные перестановки из n натуральных чисел.

Program Sort

const

N=5

type M=array [1..N] of integer;

var

a: M;

i: integer;

Procedure vivod_Perest

var

i: integer;

begin

for i := 1 to N do

write (a[i]:3);

writeln;

end;

Procedure Swip (var x, y: integer);

var

k: integer;

begin

k:=x;

x:=y;

y:=k;

end;

Procedure Perest (n: integer);

var

i: integer;

begin

if n=1 then vivod_perest;

else

begin

perest (n-1);

for i:=1 to n-1 do

begin

swap (a[n], a[i]);

perest (n-1);

swap(a[n], a[i]);

end;

end;

end;

begin

for i:=1 to N do a[i]:=1;

writeln ('перестановка');

perest (N)

end.