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

procedure P;
begin
if Ithen
begin
I  I+1; F  F*I; P
end
end (4.12)

Вместо процедуры можно ввести чаще используемую процедуру-функцию, т.е. некоторую процедуру, с которой явно связывается вычисляемое значение. Поэтому функцию можно использовать непосредственно как элемент выражения. Тем самым переменная F становится излишней, а роль I выполняет явный параметр процедуры.

function F(I);
begin
if I>0 then F  I*F(I-1)
else F  1
end (4.13)
Совершенно ясно, что здесь рекурсию можно заменить обычной итерацией, а именно программой

I  0; F  1;

while Ido
begin
I  I+1; F  I*F
end (4.14)

В общем виде программы, соответствующие схемам (4.6) или (4.7), нужно преобразовать так, чтобы они соответствовали схеме

P  (x  xo; while B do S). (4.15)
Есть и другие, более сложные рекурсивные схемы, которые можно и должно переводить в итеративную форму. Примером служит вычисление чисел Фибоначчи, определяемых с помощью рекуррентного соотношения
fib_n+1 = fib_n + fib_n-1 для n>0 (4.16) и fib₁=1, fib₀=0.
При непосредственном подходе мы получим программу


function Fib(n);
begin
if n=0 then Fib(n)  0 else
if n=1 then Fib(n)  1 else
Fib  Fib(n-1) + Fib(n-2)
end (4.17)

При вычислении fib(n) обращение к функции Fib(n) приводит к рекурсивным активациям этой процедуры. Сколько раз? Мы можем заметить, что каждое обращение при n>1 приводит к двум дальнейшим обращениям, т.е. общее число обращений растет экспоненциально. Ясно, что такая программа непригодна для практического использования.

Однако очевидно, что числа Фибоначчи можно вычислить по итеративной схеме, при которой использование вспомогательных переменных x=fib_i и y=fib_i+1 позволяет избежать повторного вычисления одних и тех же значений :

/* вычисляем x=fib_n для n>0 */

i  0; x  1; y  0;