2.5.6. Pекурсия

Понятие, которое частично определяется через самого себя, называется рекурсивным Например, о факториале числа. N можно сазать, что

либо

N! = 1 * 2 *.. * (N-1) * N, или 1, если N = 1;

либо

N1= 1. если N=1 или N1 = (N - 1)! * N..

Второе определение — рекурсивное,

Любое рекурсивное определение состоит из двух частей. Одна часть определяет понятие через него же. Другая часть — через иные понятия

Рекурсивный алгоритм - эти алгоритм, который при вычислениях. обращается сам. к себе. Например, вычисление функции F(M) может потребовать вычисления F(M—I) и еще каких-то операций. Иными словами, частью алгоритма вычисления функции будет вычисление этой же функции с другими аргументами.

Записать рекурсивный алгоритм на Паскале можно при помощи рекурсивной процедуры. Процедура является рекурсивной, если она обращается сама к себе прямо или косвенно:(через другие процедуры (рис 2.2).

Рис. 2.2

Заметим, что при косвенном обращении все процедуры в цепочке — рекурсивные.

Все сказанное о процедурах целиком относится и к функциям.

Вернемся к рекурсивному определению факториала. Достаточно переписать его на Паскале и получится описание рекурсивной функции.

Пример. Рекурсивное вычисление факториала.

function Factorial (М: integer): integer ;

begin

If N = 1 then

Factorial := 1 else

Factorial := Factorial (N—1) * N end;

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

Kак правило, это делается: при помощи условного оператора.

Пример. Возведение действительного числа X в целую степень N.

procedure Power (X: real; N: integer; var Y: real);

begin

if N = O then Y:= 1

else

begin

Power (X,N-1,Y); Y:=Y*X

end;

end;

Вызов процедурой самой себя ничем не отличается от вызова другой процедуры. Проследим за процессом выполнения вызова Power (4, 3, Y).

вызывается Power(4,3,Y); вызывается Power(4,2,Y); вызывается Power(4,l,Y);

вызывается Power(4,0,Y);

завершается Power(4,0,Y); (* Y равен 1*) завершается Power(4,l,Y); (* Y равен 4*) завершается Power(4,2,Y); (* Y равен 16*) завершается Power(4,3,Y); (* Y равен 64*)

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

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

Пример. Ввести строку символов и вывести ее в обратном направлении.

Program reverse_string;

procedure reserve; var ch, char;

begin

while not eoln do begin

read(ch);

reserve;

write(ch);

end;

end;

begin reserve;

end.

Здесь используется стандартная функция EOLN, которая возвращает TRUE, если при вводе с клавиатуры считаны все символы строки и FALSE - в противном случае.

Процедура RESERVE считывает один символ и если строка не закончена, то вызывает себя снова. При этом в памяти ЭВМ будет сохранено столько копий локальной переменной ch, какова глубина рекурсии.

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

При этом символ, введенный последним, выведется первым, введенный предпоследним - выведется вторым и так далее.

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

Применение рекурсии упрощает как алгоритм решения задачи, так и используемые структуры данных.

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

Это, с одной стороны, упрощает алгоритм, так как не надо явно сохранять все переменные (это происходит автоматически), а с другой - это часто ведет к избыточному расходу памяти ЭВМ.

Все рассмотренные примеры просты и легко выполняются без использования рекурсии.

Рассмотрим задачу, где применение рекурсии позволяет существенно упростить алгоритм.

Задача заключается в получении всех перестановок N элементов. Известно, что число таких перестановок равно N!. В качестве таких элементов будем рассматривать целые числа от 1 до N. Например, для N=3 нужно получить 3! = 6 перестановок

123

213

132

312

231

321

Это реализуется рекурсивной программой

program rearrangement;

type mas 1 = array [1.. 10] of integer;

var i,n: integer;

p:masl; procedure reverse(m:integer);

var i,j,tmp:integer;

begin

i:=l;j:=m;

while i<j do

begin

tmp:=p[j];

p[j]:=p[i];

p[i]:=tmp;

i:=i+l;

j:=j-i;

end;

end;

procedure rearrange(m:integer);

var i,j,tmp:integer;

begin

if m=l then

begin

for j:=l to n do write(p[i]],''); writeln;

end

else

for i:=l to m do

begin

rearrange(m-l);

if i<m then

begin

tmp:=p[m]; p[m]:=p[i]; p[i]:=tmp;

reverse(m-l);

end;

end;

end;

begin

Write ('Введите длину перестановки ');read(n);

for i:=l to n do p[i]:=i;

rearrange(n);

end.