Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Непейвода Н.Н. -> "Основания программирования " -> 224

Основания программирования - Непейвода Н.Н.

Непейвода Н.Н., Скопин И.Н. Основания программирования — Институт компьютерных исследований , 2002. — 919 c.
Скачать (прямая ссылка): osnovanprogramm2002.pdf
Предыдущая << 1 .. 218 219 220 221 222 223 < 224 > 225 226 227 228 229 230 .. 316 >> Следующая

о да е это не всегда гарантирует конечности. усть, например, значениями < являются рациональные числа и на пути рекурсии она выдает убывающую последовательность
E0 > E1, > • • • > El > • • •
1
1,
2
k
1
11.1. МЕХАНИЗМЫ РЕКУРСИИ
639
Сами видите, что такая рекурсия бесконечна. К счастью, в логике накоплен багаж фундированных чумов, в которых любая убывающая последовательность конечна. Самым часто применяемым из них является множество ординалов (см., например, [63]). ля построения сигнализируей функции для любой практической программы достаточно ординалов до е0 .Другим полез-нм примером фундированного чума является лексикографически упорядоченная последовательность n-ок натуральных чисел.
Пример 11.1.4. Корректность процедуры MCD и избыточность функции F из § 8.7.
Проанализируем процедуру MCD (программа 8.7.3), предназначенную для вычисления наибольшего общего делителя двух чисел. Воспользуемся одним из стандартнх реений: лексикографическим порядком на парах натуральных чисел. Каждая из входных частей In(Ekk) множеств Ekk является парой чисел, и очевидна монотонность последовательности In(Ekk). таким образом, здесь сигнализируая функция просто выделяет входну часть E. тсутствие избыточности вчислений обеспечивается структурой зависимостей действий процедуры, благодаря которой последовательность (11.1) не содержит повторений. В функции F (процедура 8.7.2), вычисляющей числа ибоначчи, действия в синтезируей части схем (сло ение двух результатов) прямо указва т на повторное появление рекурсивно вызываемых действий на различных путях рекурсии. Это повторение появляется в связи с тем, что от кадого уровня рекурсии возника т по две независимх друг от друга последовательности вызовов, а потому внутри каждой из них нет способа узнать о повторениях вычислений на другой последовательности. Но каждый из путей рекурсии упорядочен отношением < для аргументов взовов функции, и эта процедура слабо корректна. Конец примера 11.1.4.
ри задании рекурсивных алгоритмов вано хороо представлять, в какой последовательности вполня тся действия
A1(E™), An(E™),
относяиеся к разнм уровням рекурсии. т этого порядка, в частности, зависит накапливаемый результат вычислений, и, если не заботиться о нем, то выходные данные будут порождаться, но совершенно не соответствующие тому, что требуется. На рис. 11.1 приводится схема, иллюстрирующая
640
ГЛАВА 11. МЕТОДЫ, ОСНОВАННЫЕ НА РЕКУРСИИ
д°
1
рекурсия
|Д до рекурсии ! А рекурсия

А послерекурсии!
до рекурсии j
рекурсия
после рекурсии
4
к-1
рекурсия"
*
4
[TF--------} Ak ПЛГ
до рекурсии і ^ рекурсия после рекурсии!
U
к+1
рекурсия ^^^^^i без рекурсии Iі
I______________1
Рис. 11.1. Порядок действий при использовании рекурсии
порядок исполнения действий из разбиений, относящихся к разным уровням рекурсии. Он показан стрелками, соединяющими элемента разбиений (пунктирные блоки).
Определение 11.1.5. При последовательной организации рекурсивных вычислений их порядок задается как один из следующих вариантов рекурсивных схем:
• префиксная схема, когда делается попытка сначала выполнить действие А (т. е. первое исполняемое действие из Ai, ..., An приводит к А), а затем выполняются остальные действия;
• постфиксная схема, когда сначала выполняются все действия из A1, ..., An, не приводящие к А, после чего делается попытка выполнить действие Ai, которое приводит к А;
• иниксная схема, когда поптке вполнить действие A предествует некоторое число действий из A1,..., An, а после выполнения A выполняются остальные действия;
• смешанные схемы — комбинации предыдущих случаев. Конец определения 11.1.5.
11.2. ЗАКРАШИВАНИЕ ЗАМКНУТЫХ ОБЛАСТЕЙ
641
остфиксная схема обладает свойством, которое на первй взгляд мо ет повысить эффективность выполнения рекурсивных программ: за счет того, что после выполнения действия на максимальной глубине рекурсии, нет действий других уровней рекурсии, которые требуется выполнить, мо но последовательный возврат по уровням заметить заверением сразу всей цепочки рекурсивнх вызовов. днако при блиайем рассмотрении становится ясным, что в общем случае здесь никакого выигрыша нет. В обоих случаях корректное завершение требует последовательной ликвидации в обратном порядке (см. рис. 11.1) процессов, поро деннх на кадом уровне рекурсии, а это как раз то, что происходит при последовательном возврате. В то е время явное указание возмо ности заверения всех уровней рекурсии сразу может повысить выразительность алгоритма.
При префиксной схеме в принципе возможно бесконечное углубление рекурсии, если не гарантируется, что данне, поставляемые для переработки на кадй новй уровень рекурсии, ведут к некоему пределу, обеспечива-
ему конечность уровней. ля этого предела долно бть предусмотрено действие, которое у е не приводит к рекурсии. ри использовании инфиксной и постфиксной схем оба эти условия можно выполнить за счет начальных действий, предествуих рекурсии.
Рассмотренные ве поло ения никак не привязан к моделям вчи-слений языков. Здесь выделено то, что в полной мере присуще как операционному стил структурного программирования, так и неимперативному функциональному стилю. По существу, речь идет об алгоритмах, т. е. о том, что ну но иметь ввиду программисту, когда он намерен применять в своей практике методы, основанные на рекурсии.
Предыдущая << 1 .. 218 219 220 221 222 223 < 224 > 225 226 227 228 229 230 .. 316 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100