Рекурсивные алгоритмы далеко не всегда неэффективны, как можно подумать, прочитав предыдущий раздел. Во многих задачах рекурсивные процедуры и функции очень полезны, кроме того, они исключительно просто записываются, что также немаловажно. Но каждый раз, когда вы захотите решить с помощью рекурсивного алгоритма более или менее сложную задачу, вы будете сталкиваться с нехваткой памяти в стеке (можно выделить стеку менее 64К байт), а некоторые языки программирования вовсе не разрешают рекурсию. Существует способ запрограммировать рекурсивный по сути алгоритм, не используя рекурсивных подпрограмм, этот прием называется стек отложенных заданий. Здесь термин “стек” означает, конечно, не область памяти, которую компилятор отводит для подпрограмм, а некоторую структуру данных, организованную по принципу LIFO; мы уже работали с такой структурой, когда изучали списки. Стек отложенных заданий не обязательно должен храниться в хипе - если максимальная глубина стека известна заранее и не очень велика, то можно хранить стек в массиве, это еще проще. Мы будем использовать и тот и другой способ. Решим в качестве примера известную задачу о Ханойских башнях. Ханойские башни - это три стержня, на первом из которых надето n дисков постепенно уменьшающегося размера, внизу лежит самый большой диск, на нем диск поменьше и так далее, а наверху самый маленький диск. Требуется перенести все диски на третий стержень, при этом класть больший диск на меньший запрещено. Один из алгоритмов решения этой задачи вполне очевиден: сначала перенесем n-1 дисков на второй стержень (операция 1), затем самый большой диск перенесем на третий стержень (операция 2) и, наконец, перенесем n-1 дисков, которые пока надеты на второй стержень, на третий (операция 3). Одна из операций в этом алгоритме (перенос самого большого диска) тривиальна, но как выполнить остальные две? Это очень просто - для того чтобы переместить n-1 дисков, применим тот же самый алгоритм, что и для перемещения n дисков. Если мы будем использовать рекурсивную подпрограмму, то алгоритм для нее готов, больше ничего придумывать не надо.
Procedure Moving(i{количество перемещаемых дисков}, m{откуда перемещаются}, n{куда перемещаются} : Word);
Var s : Word;
Begin
If i=1 Then Begin {тривиальный случай - 1 диск}
Write(m,'-->',n,' '); Exit; End;
s:=6-m-n; {номер третьего стержня (не n и не m)}
Moving(i-1,m,s); {перенесем i-1 дисков на s - операция 1}
Write(m,'-->',n,' ');{перенесем нижний диск на n - операция 2}
Moving(i-1,s,n); {перенесем i-1 дисков c s на n - операция 3}
End;
Const n = 5;
Begin
Moving(n,1,3);
End.
Как и было обещано, программа выглядит очень просто и красиво. Теперь предположим, что по каким-то причинам использование рекурсивной подпрограммы невозможно, попробуем переписать программу так, чтобы сущность алгоритма не изменилась, а рекурсии не было.
Type
PStack = ^TStack;
TStack = Record
{это стек отложенных заданий, содержащий тройки чисел. Num - сколько дисков переместить, From_ - откуда переместить, To_ - куда переместить. Будем хранить стек в хипе, так как неизвестно, насколько велико значение n}
Num,From_,To_ : Byte;
Next : PStack;
End;
Function EoS(Init : Pointer):Boolean;
{эта функция определяет, пуст стек или нет}
Begin
EoS:=Init=Nil;
End;
Procedure Read_From_Stack(Var Init:PStack; Var Count,n1,n2:Byte);
{эта процедура "забирает" из стека одну тройку чисел - одно задание}
Var ps : PStack;
Begin
Count:=Init^.Num;
n1:=Init^.From_;
n2:=Init^.To_;
ps:=Init;
Init:=Init^.Next;
Dispose(ps);
End;
Procedure Write_To_Stack(Var Init:PStack; Count,n1,n2:Byte);
{процедура записывает в стек одно задание}
Var ps : PStack;
Begin
New(ps);
ps^.Num:=Count;
ps^.From_:=n1;
ps^.To_:=n2;
ps^.Next:=Init;
Init:=ps;
End;
Procedure Moving(i,m,n:Byte);
Var
Init : PStack;
j,p,q,s : Byte;
Begin
Init:=Nil; {стек делаем пустым}
Write_To_Stack(Init,i,m,n);
{кладем в стек задание - переложить все диски с m на n}
While Not EoS(Init) Do Begin {пока в стеке есть задания}
Read_From_Stack(Init,j,p,q); {берем задание из стека}
If j=1 Then Write(p,'-->',q,' '){тривиальный случай}
Else Begin
s:=6-p-q; {вычисляем номер свободного стержня}
Write_To_Stack(Init,j-1,s,q);
{кладем в стек задание на операцию 3}
Write_To_Stack(Init,1,p,q);
{кладем в стек задание на операцию 2}
Write_To_Stack(Init,j-1,p,s);
{кладем в стек задание на операцию 1}
End;
End;
End;
Const n=5;
Begin
Moving(n,1,3);
End.
Итак, мы заменили рекурсию стеком отложенных заданий, “неправильная”последовательность операторов Write_to_Stack - это не ошибка: задание, которое надо будет выполнить первым, мы должны класть туда в последнюю очередь (принцип стека: последним вошел - первым вышел). Этот прием можно использовать в очень многих задачах, для которых известны рекурсивные алгоритмы, мы еще встретимся с ним в следующих разделах.