Пример вычисления факториала в предыдущем разделе превращал простую,
но неэффективную в сложную и неэффектив-
ную .
Труднее найти простую нерекурсивную версию для более сложных алгорит-
мов. Методы, описанные в предыдущем разделе, используются, когда алгоритм
содержит многократную или косвенную рекурсию.
Более интересный пример устранения рекурсии - .
procedure THilblForm.DrawHilbert(depth, dx, dy : Integer);
begin
with DrawArea.Canvas do
begin
if (depth>1) then DrawHilbertfdepth-1,dy,dx);
EineTofPenPos.X+dx,PenPos.Y+dy);
if (depth>1) then DrawHilbert(depth-1,dx,dy) ;
LineTo(PenPos.X+dy,PenPos.Y+dx);
if (depth>1) then DrawHilbert(depth-1,dx,dy);
LineTo(PenPos.X-dx,PenPos.Y-dy);
if (depth>1) then DrawHilbert(depth-1,-dy,-dx);
end;
end;
В следующем фрагменте кода первые строки каждого блока между рекурсив-
ными шагами пронумерованы. Это первая строка процедуры и любых других то-
чек, в которых возможно продолжение работы алгоритма после окончания мни-
мой рекурсии.
procedure THilblForm.DrawHilbert(depth, dx, dy : Integer);
begin
with DrawArea.Canvas do
begin
1 if (depth>1) then DrawHilbert(depth-1,dy,dx);
2 LineTo(PenPos.X+dx,PenPos.Y+dy);
if (depth>1) then DrawHilbert(depth-1,dx,dy);
3 LineTo(PenPos.X+dy,PenPos.Y+dx);
if (depth>1) then DrawHilbert(depth-1,dx,dy);
4 LineTo(PenPos.X-dx,PenPos.Y-dy);
if (depth>1) then DrawHilbert (depth-1,-dy,-dx);
end;
end;
Каждый раз, когда нерекурсивная процедура начинает мнимую рекурсию,
она должна сохранить значения локальных переменных depth, dx и dy, а также
следующего значения переменной рс. После возврата из мнимой рекурсии эти
значения восстанавливаются. Для упрощения подобных операций морено напи-
сать пару вспомогательных процедур для проталкивания и выталкивания этих
значений из группы стеков.
const
STACK_SIZE=10; // Максимальная глубина рекурсии.
type
THilb2Form = class(TForm) // Код опущен...
private
pc_stack, depth_stack : Array [1..STACK_SIZE] of Integer;
dx_stack, dy_stack: Array [1..STACK_SIZE] of Integer;
top_of_stack : Integer;
// Код опущен...
:
end;
// Проталкивание значений в стеки.
procedure.THilb2Form.PushValues(pc, depth, dx, dy : Integer):
begin
top_of_stack := top_of_stack+1;
depth_stack[top_of_stack] := depth;
dx_stack[top_of_stack] := dx;
dy_stack[top_of_stack] := dy;
pc_stack[top_of_stack] := pc;
end;
// Выталкивание значений из стеков.
procedure THilb2Form.PopValues(var pc, depth, dx, dy : Integer);
begin
depth := depth_stack[top_of_stack];
dx := dx_stack[top_of_stack];
dy := dy_stack[top_of_stack];
pc := pc_stack[top_of_stack];
top_of_stack := tpp_of_stack-1;
end;
Следующий код иллюстрирует нерекурсивную версию процедуры рисования
кривых Гильберта.
procedure THilbSForm.DrawHilbert(depth, dx, dy : Integer);
var
pc, tmp : Integer;
begin
pc := 1;
with DrawArea.Canvas do
while (True) do
begin
Case pc of
1 :
begin
if (depth>l) then // Рекурсия.
begin
// Сохранение текущих значений.
PushValues(2,depth,dx,dy);
// Подготовка к рекурсии.
depth := depth-1;
tmp := dx;
dx := dy;
dy := tmp;
pc := 1; // Возврат к началу рекурсивного
// обращения
end else begin // Основное условие.
// Достигли достаточной глубины рекурсии.
// Продолжаем с блоком 2.
рс := 2;
end;
end;
2 :
begin
LineTo(PenPos.X+dx,PenPos.Y+dy);
if (depth>l) then // Рекурсия.
begin
// Сохранение текущих значений.
PushValues (3 , depth, dx, dy) ;
// Подготовка к рекурсии.
depth := depth-1;
// dx и dy остаются теми же.
pc := 1 // Возврат к началу рекурсивного
// обращения.
end else begin // Основное условие.
// Достигли достаточной глубины рекурсии
// Продолжаем с блоком 3.
рс := 3;
end;
end;
3 :
begin
LineTo(PenPos.X+dy,PenPos.Y+dx);
if (depth>1) then // Рекурсия.
begin
// Сохранение текущих значений
PushValues(4,depth,dx,dy);
// Подготовка к рекурсии.
depth :=d epth-1;
// dx и dy остаются без изменения.
pc := 1; //В начало рекурсивного обращения.
end else begin //Основное условие.
// Достигли достаточной глубины рекурсии.
// Продолжаем с блоком 4.
pc := 4;
end;
end;
4 :
begin
LineTo(PenPos.X-dx,PenPos.Y-dy);
if (depth>l) then // Рекурсия.
begin
// Сохранение текущих значений.
PushValues(0,depth,dx,dy);
// Подготовка к рекурсии.
depth := depth-1;
tmp := dx;
dx := -dy;
dy := -tmp;
pc := 1; // В начало рекурсивного обращения.
end else begin // Основное условие.
// Достигли достаточной глубины рекурсии.
// Конец этого рекурсивного обращения.
рс := 0;
end;
end;
0 : // Возврат из рекурсии.
begin
if (top_of_stack>0) then
PopValues (pc,depth,dx,dy)
else
// Стек пустой. Задача выполнена.
break;
end; // Конец case pc of.
end; // Конец while (True).
end; // Конец with DrawArea.Canvas do.
end;
Сложность этого алгоритма достаточно трудно анализировать напрямую. По-
скольку методы преобразования рекурсивных процедур в нерекурсивные не ме-
няют сложности алгоритма, эта процедура так же, как и предыдущая, имеет время
выполнения порядка O(N^4). |
Главная
Каталог файлов
