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

 

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

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

Непейвода Н.Н., Скопин И.Н. Основания программирования — Институт компьютерных исследований , 2002. — 919 c.
Скачать (прямая ссылка): osnovanprogramm2002.pdf
Предыдущая << 1 .. 158 159 160 161 162 163 < 164 > 165 166 167 168 169 170 .. 316 >> Следующая

ри изучении этого понятия следует обратить внимание на две сторон рекурсивности: способы задания рекурсивных алгоритмов (описание их на языке программирования) и механизм выполнения рекурсивного алгоритма в ходе работ программы.
Чтоб задать рекурсивный алгоритм, ну но уметь обозначать в его программе для повторяемых обраений. о алуй, единственным язковым средством такого рода явля тся операционные подпрограммы: обозначение алгоритма — имя процедуры или функции, снабженное списком фактических параметров — используется при взове подпрограмм для исполнения. В -зов подпрограммы, помееннй непосредственно в тело подпрограммы (т. е. в описание алгоритма на языке) приводит к активизации повторного впол-нения алгоритма ее до того, как первое выполнение подпрограмм не завершено.
464
ГЛАВА 8. ПОДПРОГРАММЫ
Рассмотрим следующий пример. Пусть требуется вычислить N! для небольших значений N. Определение этой функции как произведения
1 * 2 * • • • * N
приводит к почти однозначному описани требуемого алгоритма в виде цикла — итеративная схема: F := 1;
for I := 2 to N do F := F * I;
C *
F = 1;
for (int i = 2; i<= N; i++) F = F*I;
Если же N! определяется рекуррентным соотношением: 1! = 1;
N! = (N — 1)! * N, при N > 1,
то для такого определения итеративная схема не очень естественна. Более согласуется с ним следующее описание функции, которое называется рекурсивным алгоритмом, или, точнее, алгоритмом, построенным по рекурсивной схеме:
Программа 8.7.1
function FACT ( N : Integer): Integer; begin if N < 2
then FACT := 1
else FACT := FACT ( N - 1 ) * N
end;
C
int FACT ( int N ) if (N<2) return 1;
else return ( FACT (N-1)*N);
}
8.7. РЕКУРСИВНЫЕ ПРОГРАММЫ
465
(Здесь для простоты функция N! при неположительном целом аргументе доопределена как единица).
Выполнение рекурсивных программ проще всего пояснить, отслеживая процесс вычислений и сопоставляя его с процессом вчислений по итеративной схеме. В рассматриваемом примере сопоставля тся два способа в -числения N! при N, равном четырем.
По итеративной схеме произведение 1 * 2 * 3 * 4 вычисляется путем накапливания его в переменной F. F инициализируется единицей, затем при I, равном 2, 3, и 4, увеличивается, соответственно, в 2, 3, и 4 раза (после выполнения оператора F := F * I), и, как следствие, становится равной 2, 6 и 24. I, равное 4 — последнее значение, при котором перевычисляется F, и именно при этом значении I формируется последнее F (равное 24), которое является результатом выполнения итеративной программы.
о рекурсивной схеме 4! вычисляется как произведение 3! на 4. Если 3! вчислено, то 4! есть результат умно ения этого значения на 4. Таким образом, чтобы подсчитать 4! по рекурсивной схеме, надо сначала вчислить 3!, что требует вычисления 2!, для которого требуется предварительно вычислить 1!. Последнее, согласно алгоритму, есть 1, т. к. N, равное 1, меньше, чем 2. 2! есть 1! (уже вычисленное и равное 1), умноженное на 2. 3! — это произведение 2 * 3, где 2 = 2! = (3 — 1)!, а 3 — величина N, использованная при вызове алгоритма для нахо дения 3!. аконец, коль скоро 3! получено, мо но продолить вчисление 4! как 3! * N при N = 4.
8.7.1. Сопоставление итеративной и рекурсивной схем
Главная цель сопоставления двух схем программирования закл чается в реении вопроса о том, когда в реальных программах использовать ту или иную из них. Можно показать, что любой итеративный алгоритм допускает трансформаци в рекурсивнй и наоборот с сохранением вчислительной эквивалентности. бое математическое утвердение об эквивалентности или об изоморфизме структур не следует понимать буквально: будто бы в -бор схем или структуры данных непринципиален. Как правило, трансформации, предоставляемые доказательством эквивалентности, могут оказаться сложными, к тому же они никак не учитывают заботы о модифицируемости и чае всего абстрагиру тся от вопросов сло ности вчислений. оэтому для практического программирования весьма вано знать теоретические результаты об эквивалентности либо изоморфности, но интерпретировать их
466
8.
стоит как наличие нескольких альтернативных структур, выбор одной из которых нужно осуществить в соответствии с условием задачи.
Как правило, рекурсивные программы с точки зрения расхода времени и памяти менее эффективны, чем итеративные: во-первых, кадое поро де-ние экземпляра связано с отведением для него определенной памяти, а во-вторых, алгоритмически обусловленное время вычислений увеличивается за счет затрат на организацию вызова подпрограммы и возврата из нее, и хотя некоторые вычислительные машины осуществляют эти действия на аппаратном уровне (и как следствие, делают работу с подпрограммами оптимальной), далеко не все архитектуры машин допускают такую поддержку процедурного механизма.
Вместе с тем, рекурсивный алгоритм во многих случаях проще и нагляднее, чем итеративный, особенно, когда имеется рекуррентное соотношение, определяее задачу (приведенный пример слу ит тому иллстрацией).
о ет оказаться, что задача рекурсивна по суеству, т. е. для ее реения удобнее всего воспользоваться алгоритмом с поро дением вчислительнх процессов, подчиненнх стековой дисциплине. теративное описание такого алгоритма, как правило, будет завуалированной рекурсией, и потому разумно сразу е составлять рекурсивну программу.
Предыдущая << 1 .. 158 159 160 161 162 163 < 164 > 165 166 167 168 169 170 .. 316 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100