Программирование рекурсивных алгоритмов

Чтобы рекурсия не зациклилась, внутри рекурсивной процедуры/функции ОБЯЗАТЕЛЬНОдолжен присутствовать оператор IF. Общая схема построения рекурсивных программ такова:

P = IF B THEN P[S,P] END;
или
P = P[S, IF B THEN P END]

Пусть n – параметр рекурсии. Тогда:

P(n) = IF n>0 THEN P[S,P(n-1)] END
или
P(n) = P[S, IF n>0 THEN P(n-1) END]

Если есть возможность заменить рекурсию циклом – заменяйте! Например, факториал можно спокойно вычислить в обычном цикле без рекурсии:

FUNCTION fact(n:WORD):LONGINT;
VAR I:WORD;
BEGIN
fact := 1;
FOR I := 1 TO n DO
fact := fact * n
END;

Такой алгоритм снимает ограничения по памяти (экспериментальная проверка показала, что при рекурсии n£608, затем возникает ошибка переполнения памяти).

В то же время в ряде случаев очень легко написать рекурсивную программу, а превратить ее в обычную не так-то просто. Яркий пример рекурсивного "по своей природе" алгоритма – вычисление чисел Фибоначчи. Числа Фибоначчи определяются как:

Проще говоря, каждое число Фибоначчи является суммой двух предыдущих. Последовательность имеет вид 1, 1, 2, 3, 5, 8, 13, 21, 34, 55… Числа Фибоначчи играют важную роль в технике и даже в биологии (в соответствии с законом Фибоначчи растет численность живых организмов).

Рекурсивно вычислять числа Фибоначчи очень просто:

FUNCTION Fib(n:WORD):WORD;
BEGIN
IF n=0 THEN Fib := 0 ELSE
IF n=1 THEN Fib := 1 ELSE
Fib := Fib(n-1) + Fib(n-2)
END;

Алгоритм получается простым и очевидным. Увы, он сильно расходует память, и много чисел Фибоначчи так не вычислишь. Попробуем сделать нерекурсивную реализацию:

FUNCTION Fib(n:WORD):WORD;

VAR I,x,y:WORD;

BEGIN
I :=1; x := 1; y := 0;
WHILE (I<n) DO
BEGIN
x := x+y; y := x-y; INC(I)
END;
Fib := x
END;

Алгоритм заметно усложнился, пришлось ввести дополнительные переменные x и y для хранения двух предыдущих чисел Фибоначчи. Зато снялись ограничения по памяти.

Рекурсия широко используется в алгоритмах сортировки. Самый лучший на сегодняшний день алгоритм, который так и называется QuickSort(быстрая сортировка), является рекурсивным и был предложен С. Хоаром (C. Hoare) в 1970. Лежащая в основе QuickSort идея проста: для большей скорости работы лучше сначала производить перестановки элементов на большие расстояния. Алгоритм можно описать следующим образом:

1. Берем любой элемент массива х
2. Ищем в массиве слева элемент a_i>x
3. Ищем в массиве справа элемент a_j<x
4. Меняем местами a_i и a_j.
5. Повторить с п. 1

Рассмотрим пример выполнения быстрой сортировки (Рис. 12.2).

Рис. 16.2. Выполнение быстрой сортировки.

Возьмем произвольный элемент массива x=42. Будем искать в массиве слева первый элемент, больший 42. Он равен 44. Теперь ищем в массиве справа первый элемент, меньший 42. Он равен 18. Меняем 44 и 18 местами. Повторяем процедуру, теперь меняются 6 и 55. Массив постепенно сортируется.

Рекурсивная реализация QickSort довольно сложна:

PROCEDURE QuickSort;
PROCEDURE Sort(L,R:WORD);
VAR I,j:WORD; w,x: INTEGER;
BEGIN I := L; j : =R;
X: = a[(L+R) DIV 2];
REPEAT
WHILE (A[I]<X) DO
INC(I);
WHILE (X<A[J]) DO
DEC(J);
IF I<=J THEN
BEGIN
W:=A[I]; A[I] := A[J]; a{J}:=W; INC(I); DEC(J)
END
UNTIL I>J;
IF L<J THEN Sort(L,J); IF (I<R) THEN Sort(I,R)
END;
BEGIN

sort(1,n)

END;

Несмотря на сложность, это самый быстрый из имеющихся алгоритм сортировки массивов.