Вернемся к ранее представленным функциям для
и . Также вспомним функцию BigAdd, которая
исчерпывает память стека для относительно малых входных значений.
function Factorial(num : Integer) : Integer;
begin
if (num<=0) then
Factorial := 1
else
Factorial := num*Factorial(num-1);
end;
function Gcd(A, В : Longint) : Longint;
begin
if (B mod A)=0 then
Gcd := A
else
Gcd := Gcd(B mod A,A);
end;
function BigAdd(n : Double) : Double;
begin
if (n<=l) then
BigAdd := 1
else
BigAdd := n+BigAdd(n-l) ;
end;
Во всех этих функциях перед окончанием работы делается один рекурсивный
шаг. Этот тип рекурсии в конце процедуры называется остаточной или хвостовой рекурсией (tail recursion).
Поскольку после рекурсивного шага в процедуре ничего не происходит, мож-
но запросто ее удалить. Вместо рекурсивного вызова функции процедура изменя-
ет свои параметры, устанавливая в них те значения, которые бы она получила при
рекурсивном вызове, и затем выполняется снова.
Рассмотрим эту общую рекурсивную процедуру:
procedure Recurse(A : Integer);
begin
// Выполнение каких-либо действий, вычисление В, и т.д.
Recurse(B);
end;
Эту процедуру можно переписать без рекурсии следующим образом:
procedure NoRecurse(A : Integer);
begin
while (не выполнено) do
begin
// Выполнение каких-либо действий, вычисление В, и т.д.
А := В;
end;
end;
Данный процесс называется устранением остаточной рекурсии или устране-
нием хвостовой рекурсии (tail recursion removal или recursion removal). Такой при-
ем не уменьшает время выполнения программы. Просто рекурсивные шаги заме-
нены циклом while.
Устранение остаточной рекурсии тем не менее позволяет избежать вызова про-
цедуры, поэтому может увеличить скорость алгоритма. Важно то, что этот метод
экономит стековое пространство. Алгоритмы, подобные функции BigAdd, кото-
рые ограничены глубиной рекурсии, могут от этого значительно выиграть.
Некоторые компиляторы автоматически удаляют остаточную рекурсию, но
компилятор Delphi этого не делает. Иначе функция BigAdd, представленная в пре-
дыдущем разделе, не вызывала бы переполнение стека.
Если устранить хвостовую рекурсию, переписать функции вычисления фак-
ториала, НОД и BigAdd достаточно просто.
function Factorial(num : Integer) : Integer;
begin
Result := 1;
while (num>l) do
begin
Result := Result*num;
Num := num-1; // Подготовка к рекурсии.
end;
end;
function Gcd(A, В : Longint) : Longint;
var
b_mod_a : Longint ;
begin
b_mod_a := В mod A;
while (b_mod_a<>0) do
begin
// Подготовка аргументов к рекурсии.
В := А;
А := b_mod_a;
b_mod_a := В mod A;
end;
Result := А;
end;
function BigAdd(n : Double) : Double;
begin
Result := 1;
while (n>l) do
begin
Result :=. Result+N;
N := n-1;
end;
end;
Алгоритмы вычисления факториала и НОД практически не отличаются в сво-
их рекурсивном и нерекурсивном вариантах. Обе версии выполняются достаточ-
но быстро и могут оперировать большими (в разумных пределах) значениями. |
Главная
Каталог файлов
