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

UptoLike

ВУЗ: 

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

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

Рубрика: 

26
else if Odd(n) then
Result:=a*Power0(n-1);
else Result:=Sqr(Power0(n div 2));
end;
begin
Result:=Power0(n);
end;
Пример 6. Минимум в массиве.
Чтобы найти минимум в массиве из n элементов, достаточно найти минимум
в массиве из первых n – 1 элементов, после чего выбрать минимальный из этого
минимума и последнего элемента массива. Если в массиве всего один элемент, то
он – минимальный
.
Запишем данный алгоритм в виде рекурсивной функции
MinA:
⎩
⎨
⎧
>−
=
=
.1)),1,(MinA],[(MinA
,1],[
),(MinA
nnAnA
nnA
nA
Реализация повторяет рекурсивное определение:
function MinA(const A: RArr; n: integer): real;
begin
if n=1 then Result:=A[n]
else
begin
Result:=MinA(A,n-1);
if A[n]<Result then
Result:=A[n];
end;
end;
Здесь
RArr – тип вещественного массива, индексируемого от единицы. От-
метим, что массив
A не меняется при передаче в каждый рекурсивный вызов, по-
этому следует воспользоваться приемом из предыдущего примера: окаймить
функцию
MinA нерекурсивной функцией и сделать параметр A глобальным по от-
ношению к MinA.
Сделаем несколько замечаний, касающихся рекурсивных подпрограмм.
Замечание 1. При каждом рекурсивном вызове на программный стек поме-
щается запись активации подпрограммы. Поэтому если количество рекурсивных
вызовов большое или локальные переменные рекурсивной процедуры имеют
большой размер, то программный стек может переполниться и возникнет ошибка
времени выполнения программы.
Замечание 2. Накладные расходы на рекурсивные
вызовы достаточно вели-
ки, поэтому если есть явное нерекурсивное решение, то следует предпочесть его.

Страницы