Ограничение глубины рекурсии

Рекурсивные подпрограммы

Рекурсия

Алгоритм УлПир

Для того чтобы отсортировать массив методом Пирамиды, необходимо выполнить такую последовательность действий:

0-й шаг: Превратить исходный массив в пирамиду (с помощью просеивания).

1-й шаг: Для N-1 элементов, начиная с последнего, производить следующие действия:

• поменять местами очередной "рабочий" элемент с первым;

• просеять (новый) первый элемент, не затрагивая, однако, уже отсортированный хвост последовательности (элементы с i-го по N-й).

Реализация алгоритма УлПир

Часть программы, реализующую нулевой шаг алгоритма УлПир, мы привели в пункте "Просеивание", поэтому здесь ограничимся только реализацией основного шага 1:

for i:= N downto 2 do

begin x:= a[1];

a[1]:= a[i];

a[i]:= x;

j:= 1;

while j<=((i-1)div 2) do

begin k:= 2*j;

if (k+1<=i-1) and (a[k]<a[k+1])

then k:= k+1;

if a[k]>a[j]

then begin x:= a[j];

a[j]:= a[k];

a[k]:= x;

j:= k

end

else break

end

end;

Пирамидальная сортировка хорошо работает с большими массивами, однако на маленьких примерах (N<20) выгода от ее применения может быть не слишком очевидна. Его сложность - N*log N.

В математике, да и не только в ней одной, часто встречаются объекты, определяемые при помощи самих себя. Они называются рекурсивными. Например, рекурсивно определяется функция факториал: 0! =1 n! = n*(n-1)!, для любого натурального n.

В программировании рекурсивной называется подпрограмма, исполнение которой приводит к ее же повторному вызову. Если подпрограмма просто вызывает сама себя, то такая рекурсия называется прямой.

Например:

procedure rec1(k: byte); function rec2(k: byte): byte;

begin begin

... rec1(k+1);...... x:= rec2(k+1)...

end; end;

Eсли же несколько подпрограмм вызывают друг друга, но эти вызовы "замкнуты в кольцо", то такая рекурсия называется косвенной. В случае косвенной рекурсии возникает проблема с описанием подпрограмм: по правилу языка Pascal, нельзя использовать никакой объект раньше, чем он был описан. Следовательно, невозможно написать в программе:

procedure rec_А(k: byte);

begin

... reс_В(k+1);...

end;

procedure rec_В(k: byte);

begin

... rec_А(k+1);...

end;

И здесь полезной оказывается возможность отрывать объявление подпрограммы от ее писания. Например, для косвенной рекурсии в случае двух процедур, вызывающих друг друга (rec_A -> rec_B -> rec_A), нужно такое описание:

procedure rec_А(k: byte); forward;

procedure rec_В(k: byte);

begin

... reс_А(k+1);...

end;

procedure rec_A;

begin

... rec_В(k+1);...

end;

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

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