Рекурсивные процедуры и функции.

Рекурсия- это способ организации вычислительного процесса, при котором процедура или функция в процессе выполнения входящих в ее состав операторов обращается сама к себе непосредственно, либо через другие процедуры и функции.

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

Рекурсивная подпрограмма однократно вызывается извне. Условие полного окончания работы рекурсивной процедуры или функции должно находиться в ней самой.

Рассмотрим пример. Вычислить значение F=M! Рекурсивное определение значение факториала можно записать следующим образом:

при М=1 F=1

при М> 1 F= M!= M*(M-1)!, т.е. М! определяется через (М-1)!

a) Рекурсивная функция

Program Main;

Var M: integer;

F:real;

Function FACT (N:integer): real;

Begin

If N=1 then

FACT:=1

Else

FACT:= N* FACT(N-1);

End;

Begin

Readln(M);

F:= FACT ( M );

Writeln (' M!=', F);

End.

b) Рекурсивная процедура

Program Main;

Var M: integer;

F:real;

Procedure FACT(N:integer; Var F: real);

Var Q : real;

Begin

If N=1 then Q:=1

else FACT(N-1,Q);

F:=N*Q;

End;

Begin

Readln(M);

FACT ( M, F );

Writeln (' M!=', F);

End.

B варианте а) при м=4 выполняются следующие действия:

FACT:=4*FACT(3); FACT:=3*FACT(2); FACT:=2*FACT(1); FACT(1):=1.

При входе в функцию в первый раз отводится память под локальную переменную, соответствующую параметру-значению; ей присваивается значение фактического параметра (М). При каждом новом обращении строятся новые локальные переменные. Так как FACT(1)=1, то выполнение функции заканчивается. После этого выполняются действия:

FACT(1):=1; FACT:=2*FACT(1);

FACT(2):=2; FACT:=3*FACT(2);

FACT(3):=3*2=6; FACT:=4*FACT(3); т.е. FACT=24.

Предварительно-определенные процедуры.

При косвенной рекурсии одна подпрограмма вызывает другую, которая либо сама, либо посредством других подпрограмм вызывает исходную. В этом случае используется предварительное описание процедур (функций), так как в языке Турбо Паскаль все процедуры и функции должны быть описаны до их вызова. В этом случае отдельно от текста процедуры (функции) записывается ее заголовок и к нему после символа «;» добавляется ключевое слово FORWARD. Сам текст подпрограммы начинается урезанным заголовком, в котором задается только ее имя, а список параметров (и тип результата для функции ) отсутствует.

Например:

Program KOSV_R;

Var X,Y: integer;

Procedure LR ( A : integer); FORWARD;

Procedure TT (B: integer);

...

Begin

...

LR (...);

...

End;

Procedure LR ;

...

Begin

...

TT(...) ;

...

End;

Begin

...

TT(X) ;

LR(Y) ;

...

End.

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

Модули.

Процедуры и функции могут быть сгруппированы в отдельный модуль. Модуль (unit)- это программная единица, текст которой компилируется автономно (независимо от главной программы). Если модуль откомпилирован для реального режима, то результат имеет расширение TPU; модули, откомпилированные для защищенного режима, имеют расширение TPP.

Структура модуля отличается от структуры обычной программы на языке Турбо Паскаль. Модули имеют четыре основные части: заголовок, который следует за зарезервированным словом UNIT; описательную (интерфейсную) часть, которая начинается за зарезервированным словом INTERFACE (в ней помещаются объявления переменных, процедур, функций, констант и типов данных, которые должны быть доступны для других программных модулей, использующих данный модуль); исполнительную (внутреннюю) часть, которая начинается словом IMPLEMENTATION (в нее входит текст подпрограмм и локальные объекты, доступные только внутри данного модуля) и необязательную часть (секцию инициализации), расположенную после исполнительной части между словами BEGINи END (при этом, если инициализация модуля не нужна, то в секции помещается лишь слово END).

При описании подпрограмм модуля допустимо использовать сокращенные заголовки (без параметров и указания типа результата для функции) как, например, в случае использования директивы FORWARD. Начинается модуль заголовком, состоящим из зарезервированного слова UNIT и имени модуля. Имя модуля обязательно должно совпадать с именем файла (имеющим расширение PAS), в котором он находится. Модуль имеет следующую структуру:

UNIT <имя модуля>;

INTERFACE

USES<список подключаемых модулей>;

TYPE<описание типов, определенных в данном модуле

и доступных для других модулей>;

CONST<описание констант, определенных в данном

модуле и доступных для других модулей >;

VAR<описание переменных, определенных в данном

модуле и доступных для других модулей >;

PROCEDURE<заголовки процедур, определенных в данном

модуле и доступных для других модулей >;

FUNCTION<заголовки функций, определенных в данном

модуле и доступных для других модулей >;

IMPLEMENTATION

USES<список подключаемых модулей>;

TYPE<описание типов, определенных в данном модуле

и недоступных для других модулей>;

CONST<описание констант, определенных в данном

модуле и недоступных для других модулей >;

VAR<описание переменных, определенных в данном

модуле и недоступных для других модулей >;

PROCEDURE<реализация процедур, определенных в

данном модуле и доступных для других модулей >;

FUNCTION <реализация функций, определенных в данном

модуле и доступных для других модулей >;

PROCEDURE <заголовки и реализация процедур,

определенных в данном модуле и недоступных для

других модулей >;

FUNCTION <заголовки и реализация функций,

определенных в данном модуле и недоступных для

других модулей >;

BEGIN<это слово необходимо, если имеются операторы

секции инициализации>

<Необязательная часть модуля>

END.

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

Рассмотрим пример. Требуется написать главную программу, в которой вводится размер вектора и его элементы и вызывается процедура сортировки одномерного массива целых чисел в порядке возрастания. Длина массива не превышает 100. Процедуру оформить в виде модуля.

Uses Crt,Modsort;

Var A:mas;

I:byte;

N:byte;

Begin

Writeln('Ввод исходных данных:');

Readln(N);

For I:=1 to N do

Readln(A[I]);

SORT(A,N);

For I:=1 to N do

Writeln(A[I]);

Readkey

End.

Первым предложением программы является Uses,в котором подключается стандартный модуль Crt и модуль Modsort, где находится процедура сортировки.

Кроме того, тип, с которым описывается массив, отсутствует в главной программе, т.к. он присутствует в модуле.

Unit Modsort;

Interface

Type mas=array[1..100] of integer;

Procedure SORT(Var A:mas; N:byte);

Implementation

Procedure SORT;

Var I,J:byte;

X:integer;

Begin

For J:=1 to N-1 do

For I:=1 to N-J do

If A[I]>A[I+1] then

Begin

X:=A[I]; A[I]:=A[I+1]; A[I+1]:=X

End;

End;

End.

В интерфейсной части модуля описан тип masи заголовок процедуры сортировки. При подключении этого модуля с помощью предложения Usesвлюбой программе становятся доступными рассматриваемые тип и процедура. Это продемонстрировано в главной программе.

Вопросы к главе 4.

1. Назначение процедур и функций.

2. Возможность подключения процедур и функций с помощью опции компилятора.

3. Описание заголовка процедуры.

4. Описание заголовка функции.

5. Описание процедуры.

6. Как осуществляется вызов процедуры?

7. Особенности описания функции.

8. Особенности вызова функции.

9. Понятие глобальных и локальных переменных.

10. Область действия имен в программах сложной структуры.

11. Особенности использования формальных и фактических параметров.

12. Как осуществляется передача информации в процедурах без параметров?

13. Особенности использования рекурсивных процедур и функций.

14. С какой целью и как описываются предварительно определенные процедуры и функции?

15. Назначение модулей.

16. Особенности описания модулей.

Не нашли, что искали? Воспользуйтесь поиском по сайту: