Такую глубину можно считать хорошим свойством алгоритма. При каждом выполнении вызова происходит не более одного деления, возведения в квадрат и умножения, поэтому общее количество арифметических операций не больше 3log2n. При больших значениях n это существенно меньше “лобовых” n-1 умножений. Например, при n=1000 это примерно 30.

Отметим, что при некоторых значениях n приведённый алгоритм не даёт наименьшего количества умножений, необходимых для вычисления n-й степени. Например, при n=15 по этому алгоритму необходимо выполнить 6 умножений, хотя можно с помощью 3-х умножений вычислить х5, после чего помножить его на себя дважды (всего 5 умножений). Однако написать алгоритм, который задаёт вычисление произвольной степени с минимальным количеством умножений, – не совсем простая задача.

Построим нерекурсивный аналог приведённого алгоритма. Представим вычисление по рекурсивному алгоритму в таком виде:

х13=(х6)2*х1=((х3)2*х0)2*х1=(((х1)2*х1)2*х0)2*х1

Этому соответствует следующая обработка вычисляемых показателей степеней:

13=6*2+1=(3*2+0)*2+1=((1*2+1)*2+0)*2+1

Как видим, вычислению степеней соответствует вычисление значения 13, представленного полиномом относительно 2. Коэффициентами его являются цифры двоичного разложения числа 13. Нетрудно убедится, что вычислению степени с произвольным показателем n точно так же соответствует вычисление числа n, представленного двоичным разложением. Причём это разложение-полином записано по схеме Горнера. Раскроем в нём скобки:

1*23+1*22+0*21+1*20

Коэффициент при 20, 21, 22 и т.д. – это последовательные остатки от деления на 2 чисел:

n, n div 2, (n div 2) div 2 и т.д.

причём остатку 1 соответствует в рекурсивном алгоритме присваивание t:=x, а 0 – присваивание t:=1. Таким образом, двоичное разложение, например, числа 13 по степеням двойки соответствует такому представлению х13:

х2^3*x2^2*1*x2^0

Итак, достаточно вычислять степени:

x2^0= x, x2^1= x2, x2^2= (x2)2, x2^3= (x2^2)2 и т.д.

и соответствующие им остатки от деления на 2 показателей:

n, n div 2, (n div 2) div 2, ((n div 2) div 2) div 2 и т.д.

накапливая в произведении лишь те степени двойки, которые соответствуют остаткам 1. В следующем алгоритме произведение степеней накапливается в переменной t, а степени двойки – в переменной х:

function pow(x,n:integer):integer;

var t:integer; notfin:boolean;

begin

t:=1; notfin:=true;

while notfin do

begin

if odd(n) then t:=t*x;

n:=n div 2;

if n>0 then x:=x*x else notfin:=false

end;

pow:=t

end.

1.5.4. Вычисление факториала

Программируя формулы из комбинаторной математики, часто приходится использовать рекурсию. В качестве примера применения рекурсии в комбинаторике приведём, рассмотренную ранее, программу вычисления факториала (Листинг 3). Программа вводит с клавиатуры целое число N и выводит на экран значение N!, которое вычисляется с помощью рекурсивной функции FAC. Для выхода из программы необходимо либо ввести достаточно большое целое число, чтобы вызвать переполнение при умножении чисел с плавающей запятой, либо нажать Ctrl-Z и Enter.

При выполнении правильно организованной рекурсивной подпрограммы осуществляется многократный переход от некоторого текущего уровня организации алгоритма к нижнему уровню последовательно до тех пор, пока, наконец, не будет получено тривиальное решение поставленной задачи. В приведённой ниже программе решение при N=0 тривиально и используется для остановки рекурсии.

Листинг 3. Программа вычисления факториала.

ProgramFactorial;

{$S+} {Включаем контроль переполнения стека}

var n: Integer;

function Fac (n: Integer): Real;

{Рекурсивная функция, вычисляющая n!}

begin

if n<0 then

writeln (‘Ошибка в задании N’)

else

if n=0 then

Fac:=1

else Fac:=n*Fac(n-1)

end {Fac};

{----------}

begin {main}

repeat

ReadLn(n);

WriteLn(‘n! = ’,Fac(n))

untilEOF

end{main}.

Рекурсивная форма организации алгоритма обычно выглядит изящнее итерационной и даёт более компактный текст программы, но при выполнении, как правило, медленнее и может вызвать переполнение стека (при каждом входе в программу её локальные переменные размещаются в особым образом организованной области памяти, называемой программным стеком). Переполнение стека особенно ощутимо сказывается при работе с сопроцессором: если программа использует арифметический сопроцессор, результат любой вещественной функции возвращается через аппаратный стек сопроцессора, рассчитанный всего на 8 уровней. Если, например, попытаться заменить тип REAL функции FAC (см. листинг 3) на EXTENDED, программа перестанет работать уже при N=8. Чтобы избежать переполнения стека сопроцессора, следует размещать промежуточные результаты во вспомогательной переменной. Вот правильный вариант для работы с типом EXTENDED:

ProgramFactorial;

{$S+,N+,E+} {Включаем контроль стека и работу сопроцессора}

var n: Integer;

function Fac (n: Integer): extended;

varF: extended; {Буферная переменная

для разгрузки стека сопроцессора}

{Рекурсивная функция, вычисляющая n!}

begin{Fac}

if n<0 then

writeln (‘Ошибка в задании N’)

else

if n=0 then

Fac:=1

else

begin

F:=Fac(n-1);

Fac:=F*n

end;

end {Fac};

{----------}

begin {main}

repeat

ReadLn(n);

WriteLn(‘n! = ’,Fac(n))

untilEOF

end{main}.

Архитектура стека непосредственно поддерживает рекурсию, поскольку каждый вызов процедуры автоматически размещает новую копию локальных переменных. Например, при каждом рекурсивном вызове функции факториала требуется одно слово памяти для параметра и одно слово памяти для адреса возврата. То, что издержки на рекурсию больше, чем на итерацию, связано с дополнительными командами, затраченными на вход в процедуру и выход из неё. Некоторые компиляторы пытаются выполнить оптимизацию, называемую оптимизацией хвостовой рекурсии (tail-recursion) или оптимизацией последнего вызова (last-call). Если единственный рекурсивный вызов в процедуре – последний оператор процедуры, то можно автоматически перевести рекурсию в итерацию.

1.5.5. Числа Фибоначчи

С идейной точки зрения рекурсия аналогична методу математической индукции. Базе индукции соответствует база рекурсии. Предположению индукции соответствует предположение о том, что нужная процедура уже написана. Наконец, шагу индукции соответствует вызов создаваемой рекурсивной процедуры. В любой рекурсии необходимо предусмотреть условие завершения процесса, т.е. когда вызова больше не происходит.