Рекурсивні означення та підпрограми, Детальна інформація

begin

if odd(n) then t:=x

else t:=1;

if n=1 then pow:=x

else pow:=t*sqr(pow(x, n div 2))

end;

Як бачимо, проміжні множники зберігаються в локальній пам'яті процесів виконання викликів функції, а саме в тих змінних, що ставляться у відповідність її імені.

Тепер спробуємо описати залежність глибини рекурсії викликів функції від значення аргументу. У кожному наступному вкладеному виклику значення аргументу n менше від попереднього значення принаймні вдвічі. Оскільки за n=1 відбувається повернення з виклику, то таких зменшень значення аргументу n не може бути більше, ніж log2n. Отже, глибина рекурсії виклику з аргументом n не перевищує log2n.

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

Зауважимо, що при деяких значеннях n наведений алгоритм не дає найменшої кількості множень, необхідних для обчислення n-го степеня. Наприклад, при n=15 за цим алгоритмом необхідні 6 множень, хоча можна за допомогою 3-х множень обчислити x5, після чого помножити його на себе двічі (разом 5 множень). Проте написати алгоритм, який задає обчислення довільного степеня з мінімальною кількістю множень, – не зовсім проста задача. Залишимо її для наполегливих читачів.

Побудуємо нерекурсивний аналог наведеного алгоритму. Подамо обчислення за рекурсивним алгоритмом у такому вигляді:

x13 = (x6)2\xF0B4 x1 = ((x3)2\xF0B4 x0)2\xF0B4 x1 = (((x1)2\xF0B4 x1)2\xF0B4 x0)2\xF0B4 x1

Цьому відповідає така обробка показників степенів, що обчислюються:

13 = 6\xF0B4 2+1 = (3\xF0B4 2+0)\xF0B4 2+1 = ((1\xF0B4 2+1)\xF0B4 2+0)\xF0B4 2+1.

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

1\xF0B4 23+1\xF0B4 22+0\xF0B4 21+1\xF0B4 20.

Коефіцієнти при 20, 21, 22 тощо – це послідовні остачі від ділення на 2 чисел

n, n div 2, (n div 2) div 2 тощо,

причому остачі 1 відповідає в рекурсивному алгоритмі присвоювання t:=x, а 0 – присвоювання t:=1. Таким чином, двійковий розклад, наприклад, числа 13 по степенях двійки відповідає такому поданню x13: x23\xF0B4 x22\xF0B4 1\xF0B4 x20.

Отже, достатньо обчислювати степені

x20=x, x21=x2, x22=(x2)2, x23=(x22)2 тощо

та відповідні їм остачі від ділення на 2 показників

n, n div 2, (n div 2) div 2, ((n div 2) div 2) div 2 тощо,

накопичуючи в добутку лише ті двійкові степені, які відповідають остачам 1. У наступному алгоритмі добуток степенів накопичується в змінній t, а двійкові степені – в змінній x:

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

var t : integer; notfin : boolean;

begin

t:=1; notfin:=true;

while notfin do

begin