4. способы повышения эффективности алгоритмов

end;
C : NUM[ND]  COT;
COT  COT +1;
if RIS[ND]  0 then
begin
ND  RIS[ND];
goto L;
end;
if STK  0 then
begin
ND  ETS; (* ETS - номер элемента в вершине стека *)
POP; (* вытолкнуть узел из стека *)
goto C;
end
end.
Примечание:
L - Left;
C - Center.
`
Рис.4.2. СА без рекурсии для внутреннего порядка

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

P  if B then R [Si, P] (4.2)
или
P  R [Si,if B then P]. (4.3)
Наиболее надежный способ обеспечить окончание процедуры - связать с Р параметр (значение) n и рекурсивно вызвать Р со значением этого параметра n-1. Тогда замена условия В на n>0 гарантирует окончание работы. Это можно изобразить следующими схемами программ:
P(n)  if n>0 then R [S_iiP(n-1)], (4.4)
P(n)  R [S_i,if n>0 then P(n-1)]. (4.5)
На практике нужно обязательно убедиться, что наибольшая глубина рекурсии не только конечна, но и не слишком велика. Дело в том, что при каждом рекурсивном вызове процедуры Р выделяется некоторая память для размещения ее переменных. Кроме этих локальных переменных, нужно еще сохранять текущее состояние вычислений, чтобы вернуться к нему, когда закончится выполнение новой активации Р и нужно будет вернуться к старой.
Рекурсивные алгоритмы наиболее пригодны в случаях, когда поставленная задача или используемые данные определены рекурсивно. Но это не значит, что при наличии таких рекурсивных определений лучшим способом решения задачи непременно является рекурсивный алгоритм.
Программы, в которых следует избегать использования рекурсии, можно охарактеризовать следующей схемой, изображающей их строение :
P  if B then (S; P) (4.6) или эквивалентной ей
P  (S; if B then P). (4.7)
Эти схемы естественно применять в тех случаях, когда вычисляемые значения определяются с помощью простых рекуррентных соотношений. Рассмотрим, например, широко известный пример вычисления факториалов f_i = i! :


i = 0, 1, 2, 3, 4, 5,... ,
f = 1, 1, 2, 6, 24, 120,... (4.8)
"Нулевое" число определяется явным образом как f₀=1, а последующие числа обычно определяются рекурсивно - с по- мощью предшествующего значения :
f_(i+1)=(i+1)·f_i (4.9)
Эта формула предполагает использование рекурсивного алгоритма для вычисления n-го факториального числа. Если мы введем две переменные I и F для значений i и f_i на i-м уровне рекурсии, то увидим, что для перехода к следующему числу в последовательности (4.8) необходимы следующие вычисления :
I  I+1; F  I*F (4.10) и, подставив (4.10) вместо S в (4.6), мы получим рекурсивную программу
P  if Ithen (I  I+1; F  F+1; P)
I  0; F  1; P (4.11)
Первую строку в (4.11) можно записать следующим образом