Назначение процедурных типов

Процедурные типы позволяют трактовать процедуры и функции как значения, которые можно присваивать переменным процедурного типа и передавать в качестве параметров другим процедурам и функциям.

Процедурные переменные используются для вызова подпрограмм, которые присвоены этим переменным.

Процедурные переменные содержат ссылку на код процедуры или функции.

Описание процедурных типов и процедурных переменных

Существует две разновидности процедурных типов: тип-процедура и тип-функция.

Описание процедурных типов аналогично заголовку процедуры и функции, за исключением того, что отсутствует идентификатор процедуры и функции.

Например:

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, новых вызовов не будет, рекурсивный спуск заканчивается. Начнется рекурсивный возврат, т.е. завершение работы вызванных на рекурсивном спуске функций. При этом происходит вычисление факториала.