Опережающее определение процедур и функций.

⇐ ПредыдущаяСтр 16 из 23Следующая ⇒

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

Procedure A

Например: при уточнении подпрограммы (процедуры) А было решено, что она уточняется с помощью вызова двух подпрограмм (процедур) В и С.

Procedure С

Procedure B

В С

2-й случай: сложная (взаимная) рекурсия

Каждый из этих двух рассмотренных случаев связан с необходимостью определения порядка описания в программе используемых процедур: А, В, С, (1-й случай), P, Q (2-й случай).

Компилятор рассматривает текст программы сверху вниз. При этом все используемые (вызываемые) процедуры, функции, константы, переменные и метки должны быть известны (описаны) до момента их использования. В противном случае компилятор сообщит, что используется неизвестное имя, и воспримет это как ошибку. В первом случае, если описать процедуры в том порядке, в котором они появлялись в поле зрения разработчика программы (A – B – C), то в процедуре А неизвестными окажутся имена В и С.

Есть две возможности устранения подобных ошибок:

1. Изменить порядок описания процедур в тексте программы.

В 1-ом случае, чтобы устранить ошибку нужно поместить описание процедур В и С перед описанием процедуры А.

Во 2-ом случае перестановка P и Q не к чему не приведет. Для устранения этой ошибки для процедур и функций есть директива forward. При ее использовании оба примера были бы записаны следующем образом:

1-й случай:

Одни заголовки (прототипы в Си)

procedure B (...); forward;

procedure C (...); forward;

procedure A (...);

Описание А

begin

...

Вызов процедуры В и С

B(...);

C(...);

...

end;

procedure B;

Описание В и С

begin

...

Замечания: 1) директива forward указывает компилятору, что описывается только заголовок. Полное описание будет сделано ниже по тексту программы. Задача оператора forward сделать известными имена процедур и функций (т.н. внешние имена). 2). В прототипе (опережающем описании) подпрограммы все параметры должны быть описаны полностью. А в заголовке подпрограммы при ее объявлении имена параметров можно опустить (оставить лишь тип): procedure B, procedure C, procedure Q. Можно опустить и список параметров и (для функций) тип возвращаемого значения, оставив лишь имя подпрограммы.

end;

procedure C;

begin

...

end;

2-й случай:

procedure Q(...); forward;

procedure P(...);

begin

вызов Q(…);

...

end;

procedure Q;

begin

вызов Р(…);

...

end;

Рекурсия и итерация.

Рекурсия- это определение понятия самого через себя.

Например, идентификатор:: = < буква> |< идентификатор> < буква> |< идентификатор> < цифра>

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

Например, одно и то же вычисление факториала можно сделать несколькими способами:

Нерекурсивное (итерационное) решение:

fact(n) =1*2*3*4*...*n =

Рекурсивное решение имеет вид:

1, при n=0

Понижение размерности задачи

fact(n) =

fact(n-1)*n при n > 0.

4! =(3! )*4

Примеры итерационных вычислений, например, при вычислении значений многоместных (n-арных) операций уже рассматривались выше (когда роль идет о вычислении n – арных операций)

Вычисление с помощью итерации: Рекурсивное определение той же функции:

Предопределенная

константа

Type type

natural=0.. maxint; natural=0.. maxint;

function fact(n: natural): Longint; function fact(n: natural): Longint;

var begin

i: integer; if n = 0 then

f: Longint; fact: = 1;

begin else fact: = n * fact(n-1); end;

f: = 1; end.

for i: = 1 to n do вычисление значения этого

f: = f * i; выражения будет производиться

fact: = f; на рекурсивном возврате (после

end; рекурсивного вызова)

переменная где формируется

результат функции

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

Fact(3) à 3*Fact(2) à 3*( 2* Fact(1) ) à 3*( 2*( 1* Fact(0)))

Нерекурсивный вызов Fact(0)=1 завершает цепочку рекурсивных вызовов.

В общем случае при вызове любой процедуры или функции происходят следующие действия:

1). В стеке сохраняются значения локальных объектов подпрограммы (фактические параметры и локальные для вызываемой подпрограммы переменные);

2). Запоминается адрес возврата в вызывающую подпрограмму (или программу);

3). Управление передается вызванной подпрограмме.

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

Рассмотрим процесс рекурсивного определения более подробно на примере вызова y: =fact(3).

Fact(3) Первичный вызов n 3

Fact? 6

Fact(2) n 2 fact(2)*3

спуск рекурсивные вызовы Fact? 2 возврат

Fact(1) n 1 fact(1)*2

Fact? 1

Fact(0) n 0 fact(0)*1

содержимое стека Fact 1

имя

значения имя при рекурсивных вызовах

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

Такой процесс последовательного вызова функции самой себя естественно с разными значениями аргумента называется рекурсивным спуском. В процессе рекурсивного спуска при каждом рекурсивном вызове в стеке выделяется память под копию каждого локального параметра. Процесс рекурсивного спуска будет продолжаться до тех пор, пока выражение в правой части оператора присваивания для вычисления возвращаемого значения не примет вполне определенный вид (в этом случае функция сама себя не вызывает). В данном случае конец наступит, когда при очередном рекурсивном вызове аргумент будет равен 0, после этого процесс начнет раскручиваться в обратную сторону - будет происходить рекурсивный возврат. Этот процесс сопровождается освобождением памяти (в стеке), занимаемой очередной копией локальных объектов процедур или функций.

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

то, что получено после рекурсивного вызова

fact(n) = fact(n-1) * n.

Количество вызовов функцией самой себя при рекурсивном спуске называется глубиной рекурсии.

Необходимыми условиями для успешного завершения рекурсии процедур или функций являются следующие:

1 ). необходимо точно определить ситуацию, при которой должен завершиться рекурсивный спуск. В данном случае такая ситуация имеет вид: n =0 - один признак у этой ситуации Но может быть и более сложный случай.

2 ) необходимо предусмотреть в теле рекурсивной подпрограммы тех действий, которые должны приближать наступление указанной выше ситуации.

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

У рекурсивной процедуры или функции имеются следующие недостатки: на выполнение рекурсии процедуры или функции требуется большое количество машинного времени и памяти.

Времени требуется больше потому, что многократно вызываются процедуры и функции, т.е. тратиться время на то, чтобы выйти и войти в нее. Память тратится больше из-за того что при каждом рекурсивном вызове резервируется память в стеке для каждого локального объекта процедуры или функции. Для контроля переполнения стека используется директива {$S+}. Для сокращения памяти в стеке (при этом увеличатся затраты памяти в сегменте данных) при рекурсивном вызове (при предполагаемом большом числе рекурсивных вызовов), целесообразно использовать статические локальные переменные - на Паскале это типизированные константы (память под них выделяется не в стеке, а сегменте данных).

Не каждый алгоритм может быть успешно реализован с помощью рекурсии. Успешно алгоритм может быть реализован, если удалось определить ситуацию, при наступлении которой завершится процесс рекурсивного спуска.

⇐ Предыдущая 11 12 13 14 151617 18 19 20 Следующая ⇒