Содержание

• Содержание
  • Пример рекурсивного алгоритма
    • Алгоритм решения
  • Стековая организация рекурсии
  • Ограничение глубины рекурсии
• Примечания

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

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

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

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

а как

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

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

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

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

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

Стековая организация рекурсии

В момент вызова подпрограммы в памяти создается её контекст: выделяется место под все её параметры, локальные переменные и константы. Уничтожается этот контекст только после того, как будет достигнут оператор end, закрывающий подпрограмму, либо в её тексте встретится оператор Exit, досрочно прерывающий её выполнение.

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

Таким образом, на внутреннем уровне организован стек контекстов подпрограмм.

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

Для n = 24 стек контекстов этой программы пройдёт последовательно такие стадии (значения параметров указаны на моменты вызова процедуры, состояния стека приведены только на моменты времени, предшествующие закрытию очередного контекста):

Непосредственно перед закрытием самого верхнего контекста происходит печать на консоль. Таким образом, на экране появляются результаты:

2*2*2*3
2*2*6
2*3*4
2*12
3*8
4*6
24

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

Теоретически, рекурсия может быть бесконечной. Однако такой вариант вряд ли кого–нибудь устроит: рекурсивный алгоритм, как и любой нерекурсивный его собрат, обязан выдавать результат своей работы за некое обозримое время. Кроме того, память у компьютера не резиновая, в ней может поместиться лишь конечное число контекстов одновременно открытых экземпляров рекурсивной подпрограммы.

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

Примечания