ВУЗ:
и должны разрабатываться так, чтобы иметь гарантии, что это условие будет обязательно выполнено. Фактически правильно
организованное управление рекурсией включает те же три операции, что и управление циклом, – инициализация, модифика-
ция и проверка условия окончания.
Разработка рекурсивных процедур. При создании рекурсивных процедур основным условием является выбор способа, с помо-
щью которого исходную задачу можно разделить на меньшие задачи того же типа, а также определить, как результаты решения этих
меньших задач могут быть использованы в качестве абстрактных инструментов нахождения решения исходной задачи. Давайте при-
меним этот подход к поиску выхода из лабиринта, подобного приведенному на этом рисунке. Будем продвигаться вперед до тех пор,
пока не подойдем к первому разветвлению. В этой точке мы будем считать, что каждый вариант дальнейшего движения представляет
собой вход в новый лабиринт меньшего размера. Если в любом из этих меньших лабиринтов выход будет найден, наша задача реше-
на. Такой способ рассуждений приводит к построению следующей процедуры:
procedure FindExit (<лабиринт>)
Продвигаться по лабиринту до развилки, тупика или выхода; В каждом из указанных случаев вы-
полнить соответствующие инструкции из числа приведенных ниже:
case 1: достигнут выход: (сообщить "выход найден")
case 2: достигнут тупик: (сообщить "неудача")
case 3: достигнута развилка:
(while (есть ветвь, ведущая к неисследованной территории,
и выход еще не найден) do
(применить процедуру FindExit к лабиринту, представленному
одной из неисследованных ветвей;
if (эта процедура сообщила, что выход найден)
then (сообщить "выход найден".)
)
if (все варианты этой развилки неудачны)
then (сообщить "неудача")
)
Обычно рекурсивная программа разрабатывается так, чтобы проверять условие окончания (часто называемое гранич-
ным условием, или условием вырождения) до того, как будут вызваны последующие активации. Если условие окончания еще
не достигнуто, то программа создает следующую свою активацию, задача которой – найти решение сокращенной версии
задачи текущей активации. Подразумевается, что эта сокращенная версия находится ближе к условию окончания, чем зада-
ча, которой занимается текущая активация. Как только условие окончания будет обнаружено, выбирается путь, вызывающий
завершение текущей активации без создания дополнительных активаций. Это означает, что одной из остановленных актива-
ций разрешается продолжить свое выполнение, завершить ее задачу и, в свою очередь, позволить следующей остановленной
активации возобновить свои действия. Таким образом, все порожденные активации в конечном счете будут завершены, что
приведет к завершению исходной задачи.
Теперь посмотрим, как операции инициализации и модификации механизма управления повторением реализованы в рекур-
сивной программе двоичного поиска (рис. 4.14). В этом случае создание дополнительных активаций прекращается, когда обнару-
живается искомое значение или задача сужается до поиска в пустом списке. Процесс инициализируется неявно, посредством зада-
ния исходного списка и искомого значения. Начиная с этой конфигурации, программа модифицирует свою задачу, что приво-
дит к поиску во все уменьшающемся списке. Поскольку длина исходного списка конечна, а каждый этап модификации
уменьшает длину рассматриваемого списка, можно гарантировать, что либо искомое значение будет найдено, либо задача
сузится до поиска в пустом списке. Следовательно, можно сделать заключение, что процесс повторения гарантированно
прекратится.
Рассматривая структуры управления рекурсией и итерациями, можно попробовать установить, одинаковы ли их воз-
можности. То есть, если некоторый алгоритм разработан с использованием циклической структуры, то можно ли для реше-
ния этой же задачи разработать другой алгоритм, применяющий только рекурсивные методы, и наоборот. Такие вопросы
важны с точки зрения компьютерных наук, так как ответы на них позволяют понять, какие функции необходимо реализовать
в языке программирования, чтобы получить как можно более мощную систему разработки программ. Мы вернемся к этой
проблеме в главе 11, где будут рассматриваться некоторые теоретические аспекты компьютерных наук и их математических
основ. Опираясь на сделанные в этой главе выводы, в приложении Д будет доказана эквивалентность итеративных и рекур-
сивных структур.
Вопросы для самопроверки
1. Какие имена будут проверены программой двоичного поиска (рис. 4.14) при поиске имени Joe в списке имен Alice,
Bob, Carol, David, Evelyn, Fred, George, Henry, Irene, Joe, Karl, Larry, Mary, Nancy и Oliver?
2. Какое максимальное количество элементов может потребоваться проверить при выполнении двоичного поиска в
списке из 200 элементов? В списке из 100 000 элементов?
4.6. ЭФФЕКТИВНОСТЬ И ПРАВИЛЬНОСТЬ
В этом разделе мы обсудим понятия, которые являются частью данного формального введения в теорию алгоритмов. О
Страницы
- « первая
- ‹ предыдущая
- …
- 95
- 96
- 97
- 98
- 99
- …
- следующая ›
- последняя »
