Назначение процедурных типов
Процедурные типы позволяют трактовать процедуры и функции как значения, которые можно присваивать переменным процедурного типа и передавать в качестве параметров другим процедурам и функциям.
Процедурные переменные используются для вызова подпрограмм, которые присвоены этим переменным.
Процедурные переменные содержат ссылку на код процедуры или функции.
Описание процедурных типов и процедурных переменных
Существует две разновидности процедурных типов: тип-процедура и тип-функция.
Описание процедурных типов аналогично заголовку процедуры и функции, за исключением того, что отсутствует идентификатор процедуры и функции.
Например:
Type
TStrProc=procedure(n:integer; var S:string);{Описание типа-процедуры с целочисленным параметром
и параметром строкой}
TPr=procedure; {Описание типа-процедуры без параметров}
TFunc=function(a, b:integer):integer; {Описание типа-функции с двумя целочисленными параметрами
и целочисленным результатом}
varps: TstrProc; {Описание процедурных переменных}
p: Tpr;
f1,f2: TFunc;
Присваивание процедурным переменным. Вызов подпрограмм через процедурные переменные
Процедурной переменной можно присвоить:
1) процедуру или функцию, например, f1:=FMin; причем FMin должна быть описана;
В результате присваивания процедурная переменная будет содержать ссылку на функцию FMin.
2) значение другой процедурной переменной, например, f2:= f1;
Для присваивания должна выполняться совместимость по присваиванию:
Процедурный тип и заголовок присваиваемой процедуры (или функции) или процедурные типы двух переменных должны иметь одинаковое количество формальных параметров с одинаковыми типами на соответствующих позициях. Для функций типы возвращаемых значений должны совпадать.
Присваивание f1:=FMin(1,2) будет недопустимым из-за несовместимости типов: слева ‑ процедурный тип, справа – тип integer результата функции.
function FMin(a,b: integer): integer;
begin if a<b
then Result:= a
else Result:= b
end;
function FMax(a,b: integer): integer;
begin if a>b
then Result:= a
else Result:= b
end;
var x,y:integer;
begin
f1:=FMin; //Присваивание процедурной переменной ссылки на функцию FMin
x:=f1(1,2); //Вызов функции Fmin через переменную f1, x получит значение 1
f2:=FMax; //Присваивание процедурной переменной ссылки на функцию FMax
y:=f2(1,2); //Вызов функции Fmax через переменную f2 y получит значение 2
writeln(x,’ ’, y)
end.
Вызовы f1(1,2) и FMin(1,2) – это одно и то же.
Процедурные переменные в качестве параметров
Подпрограммы могут иметь параметры процедурных типов. При вызове подпрограммы фактическими параметрами тогда являются имена процедур и функций. Это прямой вызов.
При выполнении подпрограммы из нее будет вызвана процедура или функция, имя которой передано в подпрограмму.
Это обратный вызов (callback).
function MinMax(i,j:integer; f: TFunc): integer; //f ‑ параметр процедурного типа
begin
Result:= f(i,j); //Обратный вызов
end;
begin
… res:=MinMax(x,y,FMin);//Прямой вызов функции MinMax . Фактический параметр – имя функции FMin
… end.
Технику обратного вызова можно использовать для организации выполнения действий над элементами динамических структур (списков, деревьев).
Рекурсия
Что такое рекурсия
«Рекурсия – мощный метод программирования, который позволяет разбить задачу на части все меньшего и меньшего размера до тех пор, пока они не станут настолько малы, что решение этих подзадач сведется к набору простых операций» (Род Стивенс)
Рассмотрим задачу вычисления факториала n!, означающего число различных перестановок последовательности из n элементов. Факториал определяется через произведение n!=1×2×...×n. Оно конечно и вычисляется с помощью цикла
F:=1; for i:=1 to n do F:=F*i.
Рассмотрим рекуррентные формулы:
{1} 0!=1;
{2} n!=n×(n-1)!, для любого n>0.
Определение {2} сводит задачу вычисления n! к вычислению (n-1)! и т.д. до тех пор, пока задача не сведется к вычислению 0!, решение которой следует из определения {1}. Например:
3!=3×2!, 2!=2×1!, 1!=1×0!, 0!=1. Тогда, двигаясь в обратном порядке, получим:
1!=1×1=1, 2!=2×1!=2×1=2, 3!=3×2!=3×2=6
Рекурсивным определением объекта называют такое определение, которое содержит внутри себя ссылку на определяемый объект.
Объект называется рекурсивным, если он частично определяется через самого себя.
Рекурсивные подпрограммы
Рекурсия в программировании – это такой способ организации программы, при котором подпрограмма в ходе выполнения своих операторов обращается сама к себе.
Пример рекурсивной функции, вычисляющей факториал:
function RF(n:integer):integer;
begin
if n=0 then RF:=1
else RF:=n*RF(n-1)
end;
Глубина рекурсии – максимальное число рекурсивных вызовов подпрограммы без возврата во время ее выполнения.
Текущий уровень рекурсии – число рекурсивных вызовов в каждый конкретный момент времени.
Рекурсивным спуском называется процесс рекурсивных вызовов подпрограммы.
Рекурсивным возвратом называется поочередный рекурсивный выход из всех вызванных на данный момент копий рекурсивной подпрограммы.
На рекурсивном спуске в функции RF ничего не вычисляется, эта функция рекурсивно вызывается с параметром на 1 меньше в ожидании того момента, когда значение параметра станет 0. Например, при n=3:
Как только параметр станет равным 0, новых вызовов не будет, рекурсивный спуск заканчивается. Начнется рекурсивный возврат, т.е. завершение работы вызванных на рекурсивном спуске функций. При этом происходит вычисление факториала.