Управление рекурсивными структурами

Алгоритмы двоичного и последовательного поиска похожи тем, что и тот и другой требуют многократного выполнения одного процесса. Однако реализуется это условие в каждом случае по-разному. В то время как при последовательном поиске имеет место циклическая форма повторного выполнения, при двоичном поиске каждое повторное выполнение является подзадачей предыдущего выполнения процедуры. Такой метод называется рекурсией (recursion).

Как мы уже говорили, во время выполнения процедуры, включающей рекурсию, создается иллюзия существования множества копий этой процедуры, которые называются активизацией процедуры (activation of the procedure). Эти активизации создаются способом, подобным выдвижению отдельных элементов телескопической антенны, и исчезают по мере выполнения алгоритма. В каждый момент времени работает только одна из существующих активизаций. Остальные находятся в состоянии неопределенности, ожидая завершения работы других активизаций процедуры.

Представляя собой итеративные процессы, рекурсивные системы, гак же как и циклы, зависят от правильного управления ими. Их работа также зависит от проверки условия завершения и правильного их построения, которое обеспечивает выполнение этого условия завершения. Фактически, правильное управление рекурсивными структурами включает в себя те же три составляющие, которые необходимы при управлении циклами: инициализацию, модификацию и проверку условия завершения.

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

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

При рассмотрении итеративных и рекурсивных структур возникает вопрос, обладают ли они одинаковыми возможностями, то есть если алгоритм был построен с использованием цикла, можно ли создать другой алгоритм, в котором используются только рекурсивные структуры, решающий ту же самую задачу, и наоборот? Такие вопросы играют важную роль в вычислительной технике, поскольку ответы на них помогают понять, какими характеристиками должен обладать язык программирования. Мы еще вернемся к этим вопросам в главе 11, в которой обсуждаются некоторые теоретические аспекты и математические принципы, лежащие в их основе. Обладая такими знаниями, мы докажем эквивалентность итеративных и рекурсивных структур (приложение Д).