12. Рекурсивные процедуры. Область применения. Особенности написания рекурсивных процедур.

Рекурсия

В математике, да и не только в ней одной, часто встречаются объекты, определяемые при помощи самих себя. Они называются рекурсивными.

Например, рекурсивно определяется функция факториал:

0! =1
n! = n*(n-1)!, для любого натурального n.

Другим примером рекурсивного определения может послужить определение арифметического выражения, приведенное в лекции 2.

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

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

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

procedure rec1(k: byte); function rec2(k: byte): byte;
begin begin
... ...
rec1(k+1); x:= rec2(k+1);
... ...
end; end;

Если же несколько подпрограмм вызывают друг друга, но эти вызовы "замкнуты в кольцо", то такая рекурсия называется косвенной.

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

procedure rec_А(k: byte);
begin
...
reс_В(k+1);
...
end;
procedure rec_В(k: byte);
begin
...
rec_А(k+1);
...
end;

И здесь полезной оказывается возможность отрывать объявление подпрограммы от ее описания (см. лекцию 8). Например, для косвенной рекурсии в случае двух процедур, вызывающих друг друга (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;

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

Задача. Двумерный массив целых чисел представляет цвета клеток рисунка. Найдите самую большую связную область одного цвета. (Связи по диагонали не учитываются.)

Алгоритм решения

Будем считать, что цвета задаются целыми положительными числами. В процессе работы программы будем изменять значения пройденных клеток на 0. Кроме того, обрамим исходный массив каймой из нулей, чтобы предотвратить выход за его границы без дополнительных проверок на каждом шагу рекурсии. Теперь массив будет задан не как

array[1..N,1..M] of byte;

а как

array[0..N+1,0..M+1] of byte;

Теперь опишем рекурсивную процедуру, делающую по массиву один "шаг вперед":

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

Если цвет новой клетки не совпадает с цветом предыдущей "посчитанной" клетки, то нам она не нужна. Сделаем шаг назад. Если этот шаг выводит нас из массива наружу, то это означает, что мы просмотрели все клетки одной связной области: пора сравнивать их количество с ранее найденным максимумом.
Если клетка помечена тем же номером, что и предыдущая, увеличим счетчик найденных клеток, изменим пометку этой клетки на 0, а затем шагнем снова: поочередно вверх, вниз, влево и вправо (последовательность не принципиальна). Здесь важно понимать, что шагнем мы только в одну сторону, а остальные просто запомним. И лишь после того, как мы вновь возвратимся в эту же клетку, мы "вспомним", что из нее мы еще не пытались уйти туда-то и туда-то, и продолжим этот процесс.

После того как мы посетим все клетки, найденный максимум можно будет объявить итоговым.

Замечание. Рекурсивный алгоритм обхода можно представить в двух вариантах: "посмотрел-шагнул" и "шагнул-посмотрел". Другими словами, в первом случае мы сначала выбираем подходящее место для шага вперед и только потом делаем этот шаг (что очень хорошо сообразуется с правилами передвижения, скажем, по болоту). Во втором же случае мы сначала делаем шаг вперед и только потом проверяем, что же именно оказалось у нас под ногами. Все-таки "ходим" мы не по болоту и в любой момент можем "спастись" из неправильно выбранной клетки.