Техника построения рекурсивных алгоритмов

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

• должно быть найдено представление общей задачи в терминах «более простой» задачи того же класса, которое определит последователь­ность рекурсивных вызовов;

• рекурсивные вычисления не должны создавать бесконечную цепочку вызовов; для этого, во-первых, алгоритм должен включать хотя бы одно предписание, в котором при определенных условиях вычисле­ние производится непосредственно, без рекурсивного вызова {тер­минальную ситуацию), а во-вторых, рекурсивные построения в конце
концов должны сводиться к этим простым терминальным случаям.

В общем виде рекурсивное описание подпрограммы должно иметь одну из следующих структур или некоторую эквивалентную форму:

if <условие> then

<терминальная ситуация> else

<рекурсивные вызовы>

или

while <условие> do

Begin

<рекурсивные вызовы>

end; <терминальная ситуация>

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

Пример 7.1 Вычисление факториала.

{Нисходящая рекурсия} Program Factorial;

Var

n: byte;

Function Fact(n: byte): longint;

Begin {Fact}

if n = 0 then

fact:= 1 {Терминальная ветвь }

Else

fact:= n*fact(n-1){Рекурсивная ветвь }

End; {Fact}

Begin {Factorial}

Writeln('Введите n');

ReadLn(n);

Writeln('Факториал', n:2, '=', fact(n))

End. {Factorial}

Вызов, например, fact (5) означает, что функция fact вызывает себя раз $а разом: fact (4), fact(3),... до тех пор, пока не будет достигнута терми­нальная ситуация. При каждом вызове текущие вычисления «откладыва­ются», локальные переменные и адрес возврата сохраняются в стеке. Tерминальная ситуация fact:= 1 достигается при п = 0. По достижении терминальной ситуации рекурсивный спуск заканчивается, начинается рекурсивный возврат изо всех вызванных на данный момент копий функ­ции: начинает строиться ответ: n*fact(n-1), сохраненные локальные параметры выбираются из стека в обратной последовательности, а получаемые промежуточные результаты: 1*1, 2*1, 3*2*1, 4*3*2*1, 5*4*3*2*1 -передаются вызывающим функциям. Латинское recurrere означает «воз­вращение назад».

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

Пример 7.2 Вычисление факториала.

{ Восходящая рекурсия} Program Factorial;

Var

N: byte;

Function Fact (n: byte, w: longint): longint;

Begin {Fact}

if n = 0 then

fact:= w {Терминальная ветвь }

Else

fact:= fact(n-1, n*w) {Рекурсивная ветвь }

End; {Fact}

Begin {Factorial}

Writeln('Введите N');

ReadLn(N):

WriteLn(^‘Фaктopиaл', N:2, '=', fact(N, 1))

End. {Factorial}

Здесь w - рабочий параметр, применяемый для формирования ре­зультата. При первом вызове функции этот параметр надо инициализиро­вать (придать ему начальное значение - 1), далее при каждом рекурсив­ном вызове, например при вычислении 5!, он принимает последовательно значения: 5*1,4*5*1, 3*4*5*1, 2*3*4*5*1, 1*2*3*4*5*1.

Сравнивая нисходящий и восходящий варианты рекурсивного опре­деления факториала, видим: результат вычисляется в разном порядке. Поскольку умножение коммутативно, это не влияет на окончательный ответ. Однако есть классы задач, при решении которых программисту требуется сознательно управлять ходом работы рекурсивных процедур и функций. Такими, в частности, являются задачи, использующие списко­вые и древовидные структуры данных. Например, при разработке транс­ляторов применяются так называемые атрибутированные деревья разбо­ра, работа с которыми требует от программиста умения направлять ход рекурсии: одни действия можно выполнить только на спуске, другие -только на возврате. Поэтому понимание рекурсивного механизма и умение управлять им - это необходимые качества квалифицированного про­граммиста.

В следующем примере показана рекурсивная процедура с выполне­нием действий как до, так и после рекурсивного вызова (с выполнением действий как на рекурсивном спуске, так и на рекурсивном возврате).

Пример 7.3 Счет от и до 1 на рекурсивном спуске и от 1 до и на ре­курсивном возврате. При этом видно, как заполняется и освобождается стек.

{Выполнения рекурсивных действий до и после рекурсивного вызова}

Program Stack; Var

n: integer;

Procedure Rekursion (i: integer);

Begin {Rekursion}

WriteLn(i:30); {Вывод на рекурсивном спуске }

If i>1

Then

Rekursion(i-1);

WriteLn(i:3); {Вывод на рекурсивном возврате}

End; {Rekursion}

Begin {Stack}

WriteLn ('Введите n:');

ReadLn(n);

WriteLn;

WriteLn ('Рекурсия:');

Rekursion(n);

End. {Stack}

В процедуре Rekursion операция WriteLn(i:30) выполняется перед ре­курсивным вызовом, после чего WriteLn(*:3) освобождает стек. Посколь­ку рекурсия выполняется от и до 1, вывод по WriteLn(i:30) выполняется в обратной последовательности: п, п- 1,..., 1, а вывод по writeln(i:3) -в прямой: 1, 2,..., п (согласно принципу LIFO - «последним пришел, пер­вым обслужен»).

Возможная глубина рекурсивных вычислений определяется размером используемого стека. Насколько велик стек, можно установить с помо­щью бесконечной рекурсии. Причем использование директивы {$S+} при переполнении стека приведет к прерыванию программы с выдачей сообщения «Error 202: stack overflow error» («Ошибка 202: переполнение стека»).

Пример 7.4 Определение размера стека.

{Программа проверки размера стека}

Program Stack_test;

{$S+} {Включить контроль переполнения стека}

Procedure proc(i: integer);

Begin {proc}

if i mod 1024 = 0 then

WriteLn(i:6);

proc(i+l);

End; {proc}

Begin {Stackjest}

proc(l);

End. {Stackjest}

Стек связан с другой структурой памяти - с динамической облает С помощью директивы {$М} можно управлять размером стека.

Формы рекурсий

Простая линейная рекурсия

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

Пример 7.5 Нахождение НОД двух натуральных чисел по алгоритму Евклида. Алгоритм заключается в следующем: если т является точным делителем и, то НОД = т, в противном случае нужно брать функцию НОД от т и от остатка деления п на т.

{Линейная рекурсия } {Алгоритм Евклида}

Function NOD(n, m: byte): byte;

Begin {NOD} if m >n then

NOD:= NOD(m,n) {Рекурсивная ветвь }

Else

if m = 0 then

NOD:= n {Терминальная ветвь }

Else

NOD:= NOD(m, n mod m) {Рекурсивная ветвь }

End; {NOD}

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

Параллельная рекурсия

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

F(0) = 0, F(1) = 1,F(N) = F(N-1) + F(N-2).

Каждый элемент ряда Фибоначчи является суммой двух предшествующих элементов: 1 1 2 3 5 8 13 21 34 55...

Пример 7.6 Вычислить n-й член ряда Фибоначчи.

{Параллельная рекурсия. Числа Фибоначчи}

Function fib(n: integer): integer;

Begin {fib}

If n = 0 then

fib:= 0 {Терминальная ветвь }

Else

if n = 1 then

fib:= 1 {Терминальная ветвь }

Else

fib:= fib(n-1)+ fib (n-2){Рекурсивная ветвь }

End; {fib}

Для определения текущего значения F(N) функциями вызывает себя дважды в одной и той же рекурсивной ветви - параллельно. Заметим, что параллельность является лишь текстуальной, но никак не временной: вы­числение ветвей в стеке производится последовательно. В отличие от линейной рекурсии, при которой структура рекурсивных вызовов ли­нейна, нелинейная рекурсия ведет к древовидной структуре вызовов. Вы­зовы лавинообразно ведут к экспоненциальному нарастанию возникаю­щих рекурсивных вызовов - «каскаду вызовов», отсюда еще одно назва­ние - каскадная рекурсия.

Взаимная рекурсия

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

Пример 7.7 Программа выдает простые числа от 1 до и, для чего используются функции next и prim, которые вызываются перекрестно.

{Взаимная рекурсия. Простые числа}

Program Primzahlen;

Var

n, i: integer; {Опережающее описание}

Function Next (i: integer): integer;

forward; {Prim определяет: j - простое число или нет}

Function Prim(j: integer): Boolean;

Var

к: integer; Begin {Prim}

k:=2;

while (k*k <= j) and (j mod к <> 0) do

к:= Next(k);{Prim вызывает Next}

if j mod к = 0 then

Prim:= false

Else

Prim:= true;

end{Prim};

{Next вычисляет, каково следующее за j простое число. Параметры функции уже стоят в ссылке вперед}

Function Next, Var

k: integer;

Begin {Next}

k:= i+l;

While not(Prim(k)) do

k:= k+1; {Next вызывает, в свою очередь, Prim}

next:= k;

End {Next};

Begin {Primzahlen}

Writeln('Введите положительное число п,');

ReadLn(n);

Writeln('Предшествующие ему простые числа');

for i:= 2 to n do

If Prim(i) then

Write(i:6)

End. {Primzahlen}

Функция Prim определяет, является ли j простым числом, для этого просматриваются все простые числа начиная с двух, вплоть до корня изу, и проверяется, делится ли у на одно из таких простых чисел. Для поиска следующего простого числа используется функция Next, которая, в свою очередь, для идентификации простых чисел использует функцию Prim. Однако в Паскале любой идентификатор перед употреблением должен быть описан и при использовании подобных функций возникает пробле­ма ссылок вперед. Для того чтобы такого рода вызовы стали возможны, вводится опережающее описание функции Next, которое предшествует обращению к ней и состоит из ее заголовка с указанием директивы forward, заменяющей тело функции. Теперь в функции Prim можно ис_: пользовать обращение к Next - ее формальные параметры уже известны и компилятор может правильно организовать ее вызов. Полное описание функции Next помещается в программе после описания Prim, и в этом описании уже можно не указывать объявленные ранее формальные пара­метры.