Рекурсия
Если алгоритм содержит непосредственное или опосредованное (через другой вызываемый алгоритм) обращение к самому себе как к вспомогательному алгоритму, то такой алгоритм называется рекурсивным. В первом случае имеет место прямая рекурсия, во втором – косвенная. |
|
В подпрограмме обязательно должно присутствовать условие останова рекурсии.
При рекурсивных вызовах подпрограммы в стеке сохраняются наборы локальных переменных для каждого ее вызова.
ПРИМЕРЫ РЕКУРСИВНОГО ОПРЕДЕЛЕНИЯ ФУНКЦИИ
Вычислить n!
Вычислить xn:
Function fact(i:Byte):Longint;
Begin
if i=0 then fact:=1
Else fact:=i*fact(i-1);
End;
function power(x,n:Byte):Longint;
begin
if n=0 then power:=1
else power:=x*power(x,n-1);
end;
ПРИМЕР 3. Вычислить сумму ряда ex=1+X1/1!+X2/2!+X3/3!+...+Xn/n! c точностью до EPS
Program Recursion;
Function exx(x,eps:real):real;
var
s,sum: real;
i: integer;
function sl(x,i:real):real; // вложенная функция для вычисления слагаемого
begin
if i=0 then sl:=1 // условие останова рекурсии
else sl:=x/i*sl(x,i-1) // рекурсивный вызов функции
end;
begin
i:=0;
s:=1;
sum:=s;
while s>eps do
begin
inc(i);
s:=sl(x,i);
sum:=sum+s;
end;
exx:=sum;
end;
begin
writeln (’Стандартное значение=’, exp(0.99));
writeln (’Сумма ряда=’, exx(0.99,0.00000001))
end.
КОСВЕННАЯ РЕКУРСИЯ (для самостоятельного изучения)
См. 519 П54. Поляков Д., Круглов И. Программирование в среде Турбо Паскаль. - М:МАИ,1992
Опережающее описание
Содержит только заголовок и директиву forward после него.
Определяющее описание
Записывается после опережающего описания, содержит выполняемые операторы.
Полное описание процедуры
Опережающее описание + определяющее описание.
Между опережающим и определяющим описанием могут описываться другие подпрограммы, которые могут обращаться к процедуре с опережающим описанием.
ОТКРЫТЫЙ ПАРАМЕТР-МАССИВ (array of <тип-элемента>)
Используется для передачи в подпрограмму одномерных массивов произвольной длины.
Фактический параметр должен быть переменной или массивом элементов типа <тип-элемента>
В подпрограмме переданное значение рассматривается как массив с объявлением
Array[0..N-1] of <тип-элемента>,
где N - число элементов в фактическом параметре.
ИСПОЛЬЗУЕМЫЕ ФУНКЦИИ:
Low - индекс первого элемента в фактическом параметре-массиве (равен 0);
High - индекс последнего элемента в фактическом параметре-массиве;
SizeOf - размер фактического параметра-массива в байтах.
ПРИМЕР. ПРОЦЕДУРЫ ЗАПОЛНЕНИЯ/СОРТИРОВКИ/ВЫВОДА ОТКРЫТОГО ПАРАМЕТРА-МАССИВА
Пример содержит подпрограммы обработки для массивов разных типов (массивы содержат различное число элементов, элементы проиндексированы с помощью различных типов, но тип элементов совпадает).
-
Program OpenArray;
...
Type
TYP1_4=Array[1..4] of integer;
TYPa_z=Array['a'..'z'] of integer;
Var
A:TYP1_4;
B:TYPa_z;
{ Заполнение массива }
Procedure Init(var M: array of Integer);
Var
i:integer;
begin
Randomize;
for I := 0 to High(M) do
M[i]:=Random(High(M)*10);
End;
{ Вывод содержимого массива на экран }
Procedure Print(M: array of integer);
Var
i:integer;
begin
for I := Low(M) to High(M) do
write(M[i]:4);
writeln;
end;
Procedure Bubble(var M:array of Integer);
{ Сортировка модифицированным методом пузырька. Переменная t отмечает позицию последней перестановки элементов }
Var
Bound,I,t: Word;
tmp:Integer;
begin
Bound:=High(M);
Repeat
t:=0;
for I := 0 to Bound-1 do
if M[i]>M[i+1] then
begin
tmp:=M[i];
M[i]:=M[i+1];
M[i+1]:=tmp;
t:=i {позиция перестановки элементов}
end;
Bound:=t;
Until t=0;
End;
Begin
Init(A); Print(A);
Bubble(A); Print(A);
Init(B); Print(B);
Bubble(B); Print(B);
End.
См. также: Динамические массивы (Delphi).