Формы рекурсивных подпрограмм
В общем случае любая рекурсивная подпрограмма P включает в себя некоторое множество операторов S и один или несколько условных операторов рекурсивного вызова P. Пока условие истинно, рекурсивный спуск продолжается. Когда условие становится ложным, спуск заканчивается и начинается рекурсивный возврат из всех вызванных на данный момент копий рекурсивной подпрограммы.
Рассмотрим четыре разные формы рекурсивных подпрограмм на примере процедур (для функций аналогично):
1) Действия выполняются до рекурсивного вызова (на рекурсивном спуске).
procedure P(n);
begin
S; //выполняется на рекурсивном спуске
if условие then Р(n-1)
end;
2) Действия выполняются после рекурсивного вызова (на рекурсивном возврате).
procedure P(n);
begin
if условие then P(n-1);
S; //выполняется на рекурсивном возврате
end;
3) Действия выполняются до и после рекурсивного вызова (на рекурсивном спуске и на рекурсивном возврате).
| procedure P(n); begin S1; //выполняется на рекурсивном спуске; if условие then P(n-1); S2; //выполняется на рекурсивном возврате end; | procedure P(n); begin if условие then begin S1; //выполняется на рекурсивном спуске P(n-1); S2 //выполняется на рекурсивном возврате end end. |
4) Каскадная рекурсия – рекурсивные вызовы образуют дерево, например, при рекурсивном вычислении чисел Фибоначчи, при обходе деревьев.
procedure P(n);
begin
S; //может отсутствовать
if условие1 then P(n-1);
S1; //может отсутствовать
if условие2 then P(n-1);
S2 //может отсутствовать
end;
Примеры рекурсивных программ
Вывод цифр целого числа в прямом порядке
procedure Print(x: integer);
begin
if x > 9 then Print(x div 10); //Рекурсивный вызов для числа x без младшей цифры
write(x mod 10 :3) //Вывод младшей цифры на рекурсивном возврате
end;
Цифры легче получать с конца числа. Поэтому на рекурсивном спуске мы путем деления на 10 получаем последовательность чисел, которые заканчиваются очередной цифрой с конца числа. На рекурсивном возврате мы эту младшую цифру получим как остаток от деления на 10 и выведем.
Пусть x=1234, тогда на рекурсивном спуске будут происходить следующие вызовы процедуры Print:
Print(1234); Print(123); Print(12); Print(1);
Рекурсивный спуск закончился, последний экземпляр Print выведет цифру 1.
На рекурсивном возврате Print(12) выведет цифру 2, Print(123) – цифру 3, Print(1234)‑ цифру 4.
В результате получим последовательность цифр: 1 2 3 4
Поиск максимального элемента массива
Суть рекурсивного поиска максимума в том, длина части массива, на которой ведется поиск, на каждом шаге рекурсивного спуска уменьшается на 1. Когда эта длина станет равной 1, принимаем за максимальный этот единственный рассматриваемый на данном шаге рекурсии элемент.
Больше рекурсивных вызовов не происходит, начинается завершение работы вызванных функций, т.е. рекурсивный возврат. На каждом шаге рекурсивного возврата к уже обработанной части массива добавляется один элемент. Если этот элемент A[L] больше найденного ранее максимума, то значение A[L] принимается за новое значение максимума.
const N=10;
type vector=array[1..N] of integer;
var V:vector; max:integer;
function RMax(const A:vector; L:integer):integer;
{ L – длина части массива, рассматриваемой на каждом шаге рекурсии.}
var M: integer;
begin
if L=1 then RMax:=A[1] //Считаем A[1] максимальным; рекурсивный спуск закончен
else begin
M:=RMax(A, L-1); //Уменьшение длины части массива на 1 на рекурсивном спуске
if A[L]>M then RMax:=A[L] //Сравнение на рекурсивном возврате
end
end;
begin ... max:=RMax(V, N); ...
end.
19.8.3. Быстрая сортировка – усовершенствованный метод сортировки обменом
Алгоритм быстрой сортировки, который разработал англичанин Чарльз Хоор (C. Hoare) в 1960 г., является наиболее популярным алгоритмом сортировки.