Итеративная и рекурсивная схема организации

     вычислительного процесса

Для того чтобы лучше понять особенности рекурсивных алгоритмов, полезно сопоставить итеративнную и рекурсивную огранизацию процесса вычислений в программе. Особенности итеративного и рекурсивного вычислительного процесса рассмотрим на примере вычисления значения факториала некоторого натурального числа N.

 

Итеративная схема организации вычислительного процесса

Итеративный процесс можно проиллюстрировать с помощью схемы, приведенной на рис. 55. Этот процесс состоит из четырех блоков: инициализации, принятия решения (о продолжении вычислений), вычисления и модификации.

 

 

Рис. 55. Схема итеративного процесса

 

В основе итеративного вычислительного процесса лежит итеративный цикл While, Repeat-Until, For. Наиболее общим является цикл While:

While < условие цикла > do < тело цикла >;

 

Итеративная схема вычисления факториала:

 

N! = 1 * 2 * 3 * … * N.

 

Процедура, реализующая итеративную схему вычисления факториала:

 

Procedure Iter_Fact (n: word; var f: word);
Var i: word;
begin
i:=1; f:=1;	{ инициализация }
while i < = n do begin	{ решение о завершении }
f:= f * i;	{ вычисления }
inc(i);	{ модификация }
end;
end;

 

Существует два важных положения, известных в математике и в программировании, определяющих соотношение между итерацией и рекурсией.

1. Любой итеративный цикл может быть заменен рекурсией.

2. Рекурсия не всегда может быть заменена итерацией.

 

Рекурсивная схема организации вычислительного процесса

Общая схема рекурсивного вычислительного процесса представлена на рис. 56.

 

 

 

 

Рис. 56. Схема рекурсивного вычислительного процесса

 

Так как обращаться к рекурсивной процедуре можно как из нее самой, так и извне, каждое обращение к рекурсивной процедуре вызывает ее независимую активацию. При каждой активации образуются копии всех локальных переменных и формальных параметров рекурсивной процедуры, в которых “оставляют следы” операторы текущей активации. Таким образом, для рекурсивной процедуры может одновременно существовать несколько активаций. Для обеспечения правильного функционирования рекурсивной процедуры необходимо сохранять адреса возврата в таком порядке, чтобы возврат после завершения каждой текущей активации выполнялся в точку, соответствующую оператору, непосредственно следующему за оператором рекурсивного вызова. Совокупность локальных переменных, формальных параметров рекурсивной процедуры и адреса возврата однозначно характеризует текущую активацию и образует фрейм активации. Фрейм активации необходимо сохранять при очередной активации и восстанавливать после завершения текущей активации.

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

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

Общая схема рекурсивного цикла:

 

Procedure Рекурсивный_Цикл (…);

begin

if < условие цикла > then

begin

< тело рекурсивного цикла; >

Рекурсивный_Цикл (…);   

end;

end;

 

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

Общая схема бесконечного рекурсивного цикла:

 

Procedure Бесконечный_Рекурсивный_Цикл (…);

begin

if < условие цикла > then

   begin

    Бесконечный_Рекурсивный_Цикл (…);

  < тело рекурсивного цикла; >

 end;

end;

 

Рекурсивная схема вычисления факториала:

Базисная часть:

0! = 1;    1! = 1;

Рекурсивная часть:

N! = N * (N-1)! = N * (N-1) * (N-2)! = N * (N-1) * … * (N – (N-1))! =

 

Процедура, реализующая рекурсивную схему вычисления факториала:

 

Procedure Recurs_Fact (n: word; var f: word);
begin
if n <= 1 then	{ принятие решения о завершении вычислений:}
f:=1;	{ да - окончательные вычисления для базисной части }
else begin
Recurs_Fact (n-1, f);	{ нет - промежуточные вычисления и обращение процедуры к самой себе }
{ 1 }  f:=f * n;	{ окончательные вычисления для рекурсивной части }
end;
{ 2 } end;

{ 1 } – адрес возврата после завершения активации,

{ 2 } – завершение активации.

 

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

Так как при выходе из текущей активации самым первым должен быть восстановлен фрейм, который был позже всех сохранен, для хранения фреймов используется автоматическая память, т.е. область системного стека (см. 3.2.2). Таблица 3 и рис. 57 поясняют механизм рекурсивных вычислений.

Таблица 3. Трасса вычисления 3!

 

 

Рис. 57. Фреймы активации при вычислении 3!