Образовательный сайт -> Рекурсия и ее свойства -> Рекурсия и ее свойства продолжение 2

Рекурсия продолжение

НАЗАД
Во всех примерах рекурсивных алгоритмов, которые будут далее приведены, имеется некоторая убывающая неотрицательная управляющая величина, обеспечивающая завершимость программы, когда данные принадлежат соответствующим областям.
Поиск рекурсивных алгоритмов увлекателен: он имеет собственную технику, развитую, в частности, сторонниками языка ЛИСП, который дал с 1959 г. методику рекурсивного программирования. Простота и изящество этого языка особенно поразительны в связи с использованием рекурсивных структур данных .
Задача особенно удобна для рекурсивного анализа, если она может быть разложена на совокупность подзадач того же типа, но меньшей размерности. В таком случае общая методика такого анализа содержит три этапа:

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

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

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

Рассмотрим первый случай. Отношения на языке Пролог описываются с помощью правил. Правило, содержащее свой заголовок в качестве предиката в правой части этого правила, называется рекурсивным. Рекурсивное правило реализует повторяющиеся действия. Рекурсивные правила эффективны при программировании циклических задач, при формировании запросов к базам данных и при обработке списков.
Для того, чтобы рекурсивная процедура завершалась, необходимо, чтобы в процедуру было включено условие выхода, гарантирующее окончание работы процедуры. Правило, содержащее условие выхода из рекурсии, является нерекурсивным.
В общем случае рекурсивная процедура имеет следующий вид:
<заголовок рекурсивного правила>:<предикат условия выхода>,   <предикаты>.
<заголовок рекурсивного правила >:<предикаты>,
<заголовок рекурсивного правила >,<предикаты>.
<заголовок рекурсивного правила >:<предикаты>,
<заголовок рекурсивного правила >,<предикаты>.
  …………………………………………..
<заголовок рекурсивного правила >:<предикаты>,
<заголовок рекурсивного правила >,<предикаты>.

НАЗАД                         Читать ДАЛЕЕ

Поступайте к нам!
Уважаемые абитуриенты! Мы рады приветствовать Вас на нашем сайте и сегодня сообщаем Вам о том, что Вы всё ещё можете подавать заявления и поступать в ВФ МГИУ. Напоминаем, что на некоторые специальности Вы можете поступить по результатам ЕГЭ. Помните, у нас Вы сможете получить прекрасное образование по следующим направлениям: "Прикладная информатика в экономике", "Бухгалтерский учёт, анализ и аудит", Автомобиле- и тракторостроение", "Менеджмент организации"!

подробнее >>>

все новости...

{LTS}