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

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

Большая часть всех шуток о рекурсии касается бесконечной рекурсии, в которой нет условия выхода, например, известно высказывание: «чтобы понять рекурсию, нужно сначала понять рекурсию».

В действительности итерация и рекурсия взаимозаменяемы.

Пример:

function fact (n: integer): longint;

begin

if n=0 then fact:=1

else fact:=n*fact(n-1);

end;

begin

f:=1;

for i:=1 to n do

f:=f*i;

end.

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

Для хранения этой информации используется стековая память, поэтому в данном случае предпочтительнее итерационная форма.

Реализуем вычисление факториала, как в виде функции, так и в виде процедуры на языке Pascal.

{Функция на Pascal}

Function Factorial(N:integer): longint;

Begin

If N<=1

Then Factorial:=1

Else Factorial:=Factorial(N-1)*N

End;

{Процедура на Pascal}

Procedure Factorial(N:integer; Var F:longint);

Begin

If N<=1

Then F:=1

Else Begin Factorial(N-1, F); F:=F*N End

End;

Пример вызова из основной программы:

x:= Fact(a);
writeln(a, ‘!= ', x);
Factorial(a, F);
writeln(a, '!= ', F);

Результат 5!= 120
5!= 120

Дата добавления: 2014-01-03