Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Сложная рекурсия

Косвенная рекурсия возникает в том случае, когда некоторая функция обращается к другой функции, а та в свою очередь вызывает первоначальную функцию.

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

Рис. 3. Уроборос – змей, пожирающий свой хвост. Рисунок из алхимического трактата «Synosius» Теодора Пелеканоса (1478г).

Рис. 4. Сложная рекурсия.

 

Итак, возможна чуть более сложная схема: функция A вызывает функцию B, а та в свою очередь вызывает A. Это называется сложной рекурсией.

При этом оказывается, что описываемая первой процедура должна вызывать еще не описанную. Чтобы это было возможно, требуется использовать опережающее описание.

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

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

Пример: Опережающее описание процедуры B позволяет вызывать ее из процедуры A.

Здесь forward - директива компилятору, указывающая, что текст процедуры В помещен ниже

 

procedure B(n: integer); forward; {Опережающее описание второй процедуры}

procedure A(n: integer); {Полное описание процедуры A}

begin

writeln(n);

B(n-1);

end;

procedure B(n: integer); {Полное описание процедуры B}

begin

writeln(n);

if n<10 then

A(n+2);

end;

 

Результат работы:

Если в основной программе вызвать А(1), или А(2) или …. А(9), то будут выведены числа

вида 9 8 10 9 11 10 (для А(9))
вида 7 6 8 7 9 8 10 9 11 10 (для А(7)) и т.п.

Если в основной программе вызвать А(10), то будут выведены числа 10 9 11 10

Если в основной программе вызвать А(11), то будут выведены числа 11 10

Если в основной программе вызвать А(56), то будут выведены числа 56 55

Если в основной программе вызвать А(888), то будут выведены числа 888 887

 

<== предыдущая лекция | следующая лекция ==>
Сущность рекурсии | Рекурсию следует использовать только в тех случаях, когда решение задачи на каждом шаге разбивается на несколько подобных подзадач более низкого ранга
Поделиться с друзьями:


Дата добавления: 2014-01-03; Просмотров: 1662; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.01 сек.