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

 

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

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

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

14 И занести соответствующие приемы в свою базу технологических решений для использования в других подобных ситуациях.
Глава 11
Методы, основанные на рекурсии
спользование рекурсии явля тся характернм для нескольких стилей программирования. Прежде всего, надо отметить функциональное и структурное программирование, а затем нужно упомянуть многие разновидности объектно-ориентированного. Это можно объяснить, вспомнив наблюдение, что при структурном программировании и действия, и условия локальн . Такая локальность приводит к достаточно гибким средствам оперирования с контекстами, причем как раз к тем, которе дан в современнх функциональных языках в качестве базовых возможностей комбинирования функций.
Языковые средства задания рекурсии в этих стилях различаются, прежде всего, в следующих отношениях. Для функционального программирования рекурсия — атомарное действие, реализация которого остается за рамками модели вычислений. В структурном программировании средства задания рекурсии основываются на оперировании со стековой структурой контекстов.
ни да т возмо ность говорить об экземплярах действий, о других элементах данных и действий абстрактного вычислителя языка, необходиых для исполнения рекурсивнх процедур. а уровне методов разделение стилей проявляется в том, что при программировании в функциональном стиле по-оряется свободное применение рекурсии над значениями высих типов, что расиряет потенциальне возмо ности стиля. о, как у е неоднократно говорилось, реализация значений высих типов в настояее время без-надено плоха. на всегда проецирует (причем оибочно во многих тонких случаях) программу на операционные вычисления. Даже если нет ошибок, то программы, написанные в функциональном стиле, могут проигрывать в эффективности на три-четыре порядка. о этой причине в изло ении мето-
634
11.1. МЕХАНИЗМЫ РЕКУРСИИ
635
дов, основанных на рекурсии, мы преимуественно будем придериваться стиля структурного программирования. Это позволит давать более прямые и реалистичные по отношению к существующим реализациям оценки алгоритмов.
§11.1. МЕХАНИЗМЫ РЕКУРСИИ
ри обсу дении подпрограмм у е говорилось о рекурсивнх процедурах. Была указана связь рекурсивных алгоритмов с рекуррентными соотно-ениями меду даннми. о суеству это основа обирного класса рекурсивных методов, которые можно охарактеризовать как проецирование рекуррентности на программу .Но рекуррентное соотношение является лишь предпосылкой к тому, чтоб строить рекурсивну программу. частности, рекурсивная программа проигрывает итеративной схеме по эффективности, когда конкретная задача фактически не требует дополнительной памяти, вовлекаемой в вчисления при рекурсии. менно здесь, где целесообразно динамически выделять и освобо дать память, но мо но сделать это без явного обраения к механизмам распределения памяти, проходят границ разумного применения рекурсивных методов1.
Подводный камень рекурсии, также рассмотренный ранее, — повторный счет. увидели это на примере прямолинейной реализации рекуррентного соотноения. В реальной практике подобное встречается и в более завуалированной форме, что, собственно говоря, и приводит к отрицательному отношению к рекурсии среди программистов, привыкших к операционным моделям вычислений. Если же обратиться к функциональному программи-ровани , то, во-первх, среди его приемов есть достаточно полезные средства преодоления повторения вычислений, а во-вторх, автоматический анализ программ этого стиля, направленный на вявление повторений, гораздо легче и продуктивнее, чем для императивных программ. Тем не менее, опасность повторного счета остается всегда.
етод , основанне на рекурсии, укладва тся в следуу универ-
1 Заманчиво выглядят применения автоматической трансформации рекурсивной программы в итеративную, когда дополнительная память фактически нужна лишь для организации рекурсивных вызовов. Однако соответствующие алгоритмы довольно трудны и далеко не всегда распознают ситуацию, а потому такой путь нельзя рекомендовать как универсальный. К тому же, если программист составляет рекурсивный алгоритм по той причине, что он просто не проанализировал реальную потребность в ресурсах для решаемой задачи, то это свидетельствует о его низкой квалификации. И очень часто такой анализ прямо ведет разработчика к ручной трансформации решения.
636
ГЛАВА 11. МЕТОДЫ, ОСНОВАННЫЕ НА РЕКУРСИИ
сальну схему.
Определение 11.1.1. Пусть E — набор данных, обрабатываемых при выполнении некоторого действия A(E). E рассматривается как обстановка вычислений действия A (см. п. 7.3.5 и § 8.3), и, таким образом, она может включать как входные данные, так и результаты вычислений: AIn U AOut (AIn П AOut = 0 не обязательно выполнено). Если даті наборы данных E1, ..., En, действия A1,..., An, и схема программ ft над A1(E1), ..., An(En), с входными данными AIn и результатами AOut, такая, что:
• выполнение f приводит к выполнению A(E) в целом;
• каждое из Ai является либо атомарным, либо в свою очередь описано через декомпозицию;
• среди A1, . . . , An или среди реализуих их схем представлено один или более раз A;
Предыдущая << 1 .. 216 217 218 219 220 221 < 222 > 223 224 225 226 227 228 .. 316 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100