Ограничение глубины рекурсии
Рекурсивные подпрограммы
Рекурсия
Алгоритм УлПир
Для того чтобы отсортировать массив методом Пирамиды, необходимо выполнить такую последовательность действий:
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;
Теоретически, рекурсия может быть бесконечной. Однако рекурсивный алгоритм, как и любой нерекурсивный, обязан выдавать результат своей работы за некое обозримое время. Следовательно, каждая рекурсивная подпрограмма должна содержать в себе признак окончания, определяющий максимальную глубину вложенности для этой рекурсии. Признак конца рекурсии может быть как явным (например, в случае реализации факториала), так и неявным (в частности, процедура рано или поздно обязательно закончится, если на каждом шаге происходит уменьшение числа).