Статическая и динамическая память программы

Лекция 11

Рекурсия. Косвенная рекурсия

Процедурные типы

В TP можно использовать переменные процедурного типа. Переменные процедурного типа позволяют передавать в подпрограмму имена процедур и функций. Вот примеры описаний процедурных типов:

Type Proc1 = Procedure (a,b,c:real; var d:real);

Proc2 = Procedure (var a,b:real);

Func1 = Function: string;

Proc3 = Function (var s:string):real;

PROC = procedure; { процедура без параметров }

PROC4 = procedure (var x : real; y : integer);

FUN2 = function (x, y : real) : real;

var f : FUN2;

Переменную f можно использовать, например, так:

{$F+}{Использование дальней адресации}

function deg(a,b:real):real;

begin {вычисляем степень: a**b}

deg:=exp(ln(a)*b);

end;{deg}

{$F-}

begin {программа}

f := deg; writeln('2**15=',f(2,15));

end.

Функция вычисления факториала:

1. Рекуррентное определение

function Factor(n:integer):integer;

var i,f:integer;

begin

f:=1;

for i:=2 to n do f:=f*i;

Factor:=f;

end.

2.Рекурсивное определение

function Fact(n:integer):integer;

var f:integer;

begin

if n=0 then f:=1 else f:=Fact(n-1)*n

end.

При описании рекурсивной процедуры или функции используется сама процедура или функция. Для корректности такого описания необходимо выполнение двух условий:

1. В алгоритме существует нерекурсивная ветка.

2. Необходимо убедиться, что последовательность рекурсивных обращений к подпрограмме, выведет на нерекурсивную ветку алгоритма.

Работа рекурсивной функции вычисления факториала показано на слайдах (прилагаются).

Если при описании процедуры А используется процедура В, а при описании процедуры В используется процедура А, то такая ситуация называется косвенной рекурсией. Чтобы избежать синтаксических проблем при описании таких функций используют опережающее описание. Сначала приводят заголовок процедуры В с директивой FORWARD, а затем описывают тела процедур А и В, соответственно.

Для выполнения оттранслированной программы объектный код ее загружается в оперативную память вычислительной машины. Под код программы и под ее данные отводится участок оперативной памяти, называемый статической памятью программы. При загрузке программы относительные адреса объектного кода и данных (констант, переменных, массивов и т.д.) заменяются на реальные адреса отведенного участка памяти. Если операционная система допускает многозадачный режим работы, статическая память программы не доступна другим программам, так же как и статическая память других программ не доступна данной программе. Однако, существует свободная, не используемая никакой программой, память, которая может быть временно задействована каждой из программ. Такая память называется динамической памятью.

В языке ТР имеются механизмы использования динамической памяти на этапе выполнения программы. Необходимость в использовании динамической памяти возникает, если по условию задачи не удается заранее предвидеть потребный объем статической памяти. Вот пример такой задачи: (*) Распечатать последовательность вводимых с клавиатуры символов в обратном порядке.