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

 

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

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

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

то A называется рекурсивным, а f называется рекурсивной схемой программ для A(E). f называется также декомпозицией A(E), а A1(E1),..., An(En) — базисом этой декомпозиции. Конец определения 11.1.1.
рименение этого определения требует конкретизации больинства затрагиваемых им понятий. Во-первых, схема f здесь не обязательно схема программ в классическом смысле. Она может включать и совместные, и недетерминированные, и параллельные действия. Во-вторх, отн дь не все элемент обстановки могут представляться реальными программными объектами, они могут (и часто долны быть) призраками.
Рассмотрим пример. Если пополнить входные данные программы всеми их возможными комбинациями при помощи имеющихся функций (построить т. н. сколемовский универс), то мо но считать все Ei подмно ествами E . о такое разбиение данных, хотя полезно для анализа программы, в боль-
инстве случаев остается лиь концептуальным, и нет ну ды строить его явно: это не только нецелесообразно, но зачастую и просто невозможно. Более того, если явное построение осуществимо, а не остается призраком, то именно это свидетельствует о том, что, по-видимому, в данном случае более разумно итеративное реение, которое не ну дается дополнительной памяти рекурсивного вчисления.
то е время, необходимо научиться выстраивать последовательность данных (наборов данных), которая будет динамически предъявляться A1, . . . ,
11.1. МЕХАНИЗМЫ РЕКУРСИИ
637
An при каждом обращении к рекурсивно задаваемому действию. С разбиением действий чуть проще: это, собственного говоря, и есть декомпозиция алгоритма. Основные задачи здесь сводятся к следующему. Надо понять, что именно будет предохранять от бесконечного вчисления рекурсивнх схем и от повторного счета.
Определение 11.1.2. Пусть Q рекурсивная схема для A(E) с базисом A1 (Sj;), ..., An (En), пусть Ey — исполнение данной схемы. Пусть j 1 — номер компонента базиса, для которого Aj1(Ej1) присутствет в исполнении и приводит к исполнению A(E2). Тогда можно построить рекурсивную схему следующего уровня, совпадающую с Q по структуре, но имеющую базис
Ai(Ej), An(En).
Таким путем мо ет бть выстроена последовательность активизаций A, называемая пуем рекурсии:
A(E)=A(Ei), AjI(E1I), A(E2)A(Efc), Ajk (Ekfc), A(Efc+i),... . (11.1)
Если эта последовательность конечна, т. е. существует k такое, что в исполнении A(Ek) уже нет компонент, исполняющих A, то номер j, 1 ^ j ^ k, называется уровнем рекурсии, а k — глубиной рекурсии для исполнения Ey.
Рекурсивная схема называется конечной, если для всех данных, с которыми выполняется A, гарантируется конечность глубины рекурсии. Рекурсивная схема называется избыточной, если существует набор данных, с которыми выполняется A, для которого в последовательности (11.1) встречаются повторяющиеся элемента. Рекурсивная схема называется слабо избыточной, если суествует набор данных, с которыми выполняется A, для которого на двух путях рекурсии (11.1) встреча тся повторяиеся элементы.
Конечная и не избточная рекурсивная схема назвается слабо коррек -ной. Конечная, не избыточная и не слабо избыточная рекурсивная схема на-звается коррек ной. Конец определения 11.1.2.
у но всегда знать, чем в конкретном случае становятся контексты компонет рекурсивного вызова, а также обосновывать, что рекурсивная схема является корректной. Следуие примеры поясня т данное определение.
Пример 11.1.3. Разбиение данных и действий.
Процедура рекурсивного вычисления факториала (см. программу 8.7.1 на стр. 464) приводит к следующим контекстам данных и разбиениям действий:
638
11. ,
result = 1;
result = Fact (N-1);
result = result(A2) * N;
{1, result}; {N - 1, result}; {result(A2) * N};
ля дальнейих уровней рекурсии вра ения оста тся соверенно аналогичными выражениям для A3, Ef.
Разбиение аргумента N остается призраком. но представляет базу для соответствующих действий, второе из которых задает рекурсию, а третье -синтезирует результат. Условие из программы 8.7.1 и зависимость An+1 от An гарантируют сильную корректность схемы. Путь рекурсии всего один. Конец примера 11.1.3.
Анализ разбиений данных и контекстов действий является мощным инструментом для сло нх рекурсивных программ, но он требует во всех нетривиальных случаях дополнения аппаратом т. н. сигнализирующих функций.
а практике непосредственная проверка конечности глубины рекурсии мо ет оказаться затруднительной. оэтому, согласно парадоксу изобретателя, нужно вводить идеальные конструкции, гарантирующие конечность.
ервое, что здесь приходит на ум — ввести некоторое частичное упорядочение ^ на множестве контекстов E, такое, что на любом пути рекурсии
Это отношение лучше всего задать при помощи функции-призрака, отобра-аей мно ество контекстов в какое-либо обычное частично-упорядочен-ное (а чаще всего в линейно-упорядоченное) множество. Такая функция называется сигнализирующей функцией рекурсии. Итак, для сигнализирующей функции <р должно на каждом пути рекурсии выполняться
Когда <р становится достаточно малой (например, доходит до нуля), рекурсия заканчивается. а самом деле < мо ет принимать в качестве аргумента лиь входне части контекстов.
Предыдущая << 1 .. 217 218 219 220 221 222 < 223 > 224 225 226 227 228 229 .. 316 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100