Основы программирования. Файлы. Рекурсия - 23 стр.

UptoLike

ВУЗ: 

ЮФУ | Ростов-на-Дону

Составители: 

Рубрика: 

25
Пример 5. Вычисление
n
a .
Рассмотрим рекурсивное определение
n
a
, которое является более эффектив-
ным, чем приведенное в начале главы, и, кроме того, учитывает случай
0
<
n :
⎪
⎪
⎩
⎪
⎪
⎨
⎧
<
−>⋅
−>
=
=
−
.0если,1
,нечетное,0если,
,четное,0если,)(
,0если,1
1
22/
na
nnaa
nna
n
a
n
n
n
n
Реализация также не вызывает затруднений:
function Power(a: real; n: integer): real;
begin
if n=0 then
Result:=1
else if n<0 then
Result:=Power(a,-n)
else if Odd(n) then
Result:=a*Power(a,n-1)
else Result:=Sqr(Power(a,n div 2));
end;
При программировании рекурсивных подпрограмм следует следить за глу-
биной рекурсии: она не должна быть очень большой, чтобы программный стек не
переполнился.
Нетрудно видеть, что при вычислении
16
a
глубина рекурсии равна 5:
При вычислении же
15
a
функция Power последовательно вызывается для аргу-
ментов 15, 14, 7, 6, 3, 2, 1, 0, и глубина рекурсии составляет 7.
Недостаток данного алгоритма состоит в том, что переменная a не меняется,
но передается в каждый рекурсивный вызов. Сделаем переменную a глобальной
по отношению к рекурсивной функции, для чего окаймим ее нерекурсивной
функцией с параметрами a и n, осуществляющей в своем
теле стартовый вызов
рекурсивной функции:
function Power(a: real; n: integer): real;
function Power0(n: integer): real;
begin
if n=0 then
Result:=1

Страницы