Рекурсивные подпрограммы

Язык Object Pascal допускает создание и использование рекурсивных подпрограмм. Это означает, что внутри подпрограммы можно обращаться к самой подпрограмме. Однако, чтобы такое обращение имело смысл, подпрограмма должна быть организована должным образом, т.е. реализовала бы именно рекурсивный алгоритм. Например, составим функцию, вычисляющую сумму элементов одномерного массива. Если использовать известный прием накопления суммы, предусматривающий вычисление суммы в цикле, то такая функция может иметь следующий вид:

program Fun2rec;

{$APPTYPE CONSOLE}

uses

SysUtils;

const

nn=20;

type

mas=array[1..nn] of Real;

var

a:mas;

i,n:Integer;

s:Real;

function Sum(a:mas;n:Integer):Real;

var i:Integer;

begin

Result:=0;

for i:=1 to n do

Result:=Result+a[i];

end;

begin // РАЗДЕЛ ОПЕРАТОРОВ ПРОГРАММЫ

ReadLn(n);

for i:=1 to n do

Read(a[i]);

ReadLn;

s:=sum(a,n);

WriteLn('s= ',s:6:1);

ReadLn;

end.

Внутри функции для накопления суммы использовалась внутренняя переменная Result. Использование внутри цикла оператора присваивания Sum:=Sum+a[i] привело бы к ошибке, так как появление в правой части оператора присваивания имени функции означало бы обращение к этой функции. Поскольку после имени функции отсутствуют параметры, то это означало бы синтаксическую ошибку. Но поскольку внутри функции реализован циклический алгоритм, а не рекурсивный, то оператор Sum:=Sum(a,n)+a[i] приводил бы также к ошибке (подпрограмма зацикливается).

Для построения рекурсивного варианта подпрограммы следует сформулировать рекурсивное утверждение и условие окончания рекурсии. В нашем случае рекурсивное утверждение будет заключаться в том, что сумма элементов массива из n элементов может быть вычислена как сумма (n-1)-го начальных элементов и последнего элемента, то есть S_n =S_n-1 + a_n (n>1). Условие окончания рекурсии S₁ = a₁. Рекурсивный вариант функции приведен ниже.

function Sum(a:mas;n:Integer):Real;

begin

if n=1 then

Sum:=a[n]

else

Sum:=a[n]+Sum(a,n-1)

end;

Рекурсивное описание обычно является более компактным и выглядит более наглядно, если природа самого алгоритма рекурсивна. Однако надо принимать во внимание и то, как реализуется рекурсивный алгоритм в ЭВМ. Например, при n=4 (массив состоит из четырех элементов) производится первое обращение к функции со значениями параметров массива a и n=4. При этих значениях выполняется оператор Sum:=a[4]+Sum(a,3). Затем выполняется обращение к функции со значениями a и 3, т.е. sum(a,3). Затем выполняется обращение к функции со значениями a и 2, т.е. Sum(a,2). При выполнении этого обращения к функции производится еще одно обращение: sum(a,1). На последнем шаге при обращении к функции с этими параметрами будет выполнен оператор Sum:=a[1]. Далее процесс развивается в обратном направлении, т.е. выполнится оператор Sum:=a[2]+Sum(a,1), что даст результат Sum:=a[2]+a[1], затем выполнится оператор Sum:=a[3]+Sum(a,2), это дает результат Sum:=a[3]+a[2]+a[1]. На последнем шаге выполнится оператор Sum:=a[4]+Sum(a,3), дающий окончательный результат. Рассмотрев описанный процесс, можно придти к выводу, что рекурсивная подпрограмма требует больших затрат машинного времени и памяти. Это объясняется необходимостью выполнения повторных обращений к подпрограмме и необходимостью хранения (в стеке) фактических параметров при обращениях к подпрограмме.

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

procedure Pr1(a:Real;var b:Real);

begin

.....

Pr2(a,b);

.....

end;

procedure Pr2(c:Real;var d:Real);

begin

.....

Pr1(c,d);

.....

end;

Согласно правилам языка Object Pascal каждый идентификатор должен быть предварительно объявлен, поэтому такая конструкция недопустима. Чтобы разрешить использование косвенной рекурсии, в состав языка введено опережающее объявление, реализуемое директивой forward. Сначала необходимо объявлен заголовок одной из процедур, после которого поместить указанную директиву. После этого следует расположить вторую процедуру, а затем разместить первую процедуру, в заголовке которой можно опустить список формальных параметров. Таким образом, во второй процедуре можно обращаться к первой процедуре, так как к этому моменту ее заголовок уже известен второй процедуре.

procedure Pr1(a:Real;var b:Real); forward;

procedure Pr2(c:Real;var d:Real);

begin

.....

Pr1(c,d);

.....

end;

procedure Pr1(a:Real;var b:Real);

begin

.....

Pr2(a,b);

.....

end;

Дата добавления: 2015-07-26