Приклад

 

«Індійський алгоритм» піднесення числа х до натурального степеня п реалізує таке рекурсивне означення степеня числа:

Алгоритм обчислення хⁿ

1.Якщо показник степеня дорівнює нулю, то значення хⁿ покласти рівним одиниці та вийти з рекурсії, інакше виконати дії, зазначені в пунктах 2-5.

2.Якщо показник степеня дорівнює одиниці, то значення хⁿ покласти рівним х та вийти з рекурсії, інакше виконати дії, зазначені в пунктах 3-5.

3.Обчислити значення х^{n div 2} та піднести його до квадрата.

4.Якщо показник степеня непарний, то обчислене в пункті 3 значення помножити на число х, а отриманий результат вважати значенням хⁿ.

5.Інакше, коли показник степеня парний, то обчислене в пункті 3 значення вважати значенням хⁿ.

program ех8_9:; {індійський алгоритм піднесення до степеня}

var base,exponent:integer; {число, показник степеня}

procedure Init;

begin

writeln (‘ Indian algorithm’);

writeln (‘enter base, exponent’);

readln (base,exponent);

end;

{============піднесення до степеня ==================}

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

var t: integer; {допоміжна змінна}

begin

if n = 0 then pow:=l

else

if n = l then pow := x {рекурсивне повернення}

else

begin

t := sqr(pow(x, n div 2)); {рекурсивне занурення}

if odd(n) then pow:=t*x {рекурсивне повернення}

else pow := t; {рекурсивне повернення}

end;

end;

{===========основна програма ===============}

begin

Init;

writeln (base, ‘٨’, exponent, '=', pow(base, exponent));

end.

Глибина рекурсії функції pow не перевищує log₂ п.