Механизм работы рекурсивной функции

Различают два вида рекурсии подпрограмм:

§ прямая или явная рекурсия - характеризуется существованием в теле подпрограммы оператора обращения к самой себе;

§ косвенная или неявная рекурсия - образуется при наличии цепочки вызовов других подпрограмм, которые в конечном итоге приведут к вызову исходной.

Каждое обращение к рекурсивной подпрограмме вызывает независимую активацию этой подпрограммы. Совокупность данных, необходимых для одной активации рекурсивной подпрограммы, называется фреймом активации.

Фрейм активации включает:

§ копии всех локальных переменных подпрограммы;

§ копии параметров-значений;

§ четырехбайтовые адреса параметров-переменных и параметров-констант;

§ копию строки результата (для функций типа string);

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

Пример 4. Разработать программу определения наибольшего общего делителя двух чисел, используя алгоритм Евклида.

Рекурсивный вариант решения данной задачи будем строить исходя из двух утверждений.

Базисное утверждение: если два числа равны, то их наибольший общий делитель равен этим числам.

Рекурсивное утверждение: наибольший общий делитель двух чисел равен наибольшему общему делителю их разности и меньшего из чисел.

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

Рис. 1. Схема алгоритма Евклида

а - с использованием рекурсивной процедуры; б - с использованием рекурсивной функции

Program ex;

Var

a, b, r: integer;

Procedure nod(a, b: integer; var r: integer);

Begin

if a=b then r: =a {базис}

else if a> b then nod(a-b, b, r)

else nod(a, b-a, r)

End;

Begin

ReadLn(a, b);

nod(a, b, r);

WriteLn(r);

End.

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

Если реализовать вариант с рекурсивной функцией (см. рис. 5.10, б), то фрейм активации уменьшится, так как сократится список параметров. Соответствующая программа будет выглядеть следующим образом:

Program ex;

Var a, b, r: integer;

Function nod(a, b: integer): integer;

begin

if a=b then nod: =a {базис}

else {рекурсивный вызов}

if a> b then nod: =nod(a-b, b)

else nod: =nod(a, b-a)

end;

Begin

ReadLn(a, b);

r: =nod(a, b);

WriteLn(r);

End.

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

Размер стека устанавливается в настройках среды, по умолчанию он принимает размер 16 Кб, и его размер не может превышать 64 Кб.

Пример 6. Разработать рекурсивную подпрограмму «переворота» строки (первая буква должна, стать последней, вторая - предпоследней и т.д.).

Можно предложить два способа разворота строки.

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

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

Вариант с отсечением и дописыванием:

Function reverse 1 (const st: string): string;

Begin

if length(st)=0 then reverser l: ="

else

reverserl: = reversel (copy (si, 2, length(st)-l)) +st[l];

End;

Определим размер фрейма активации:

V = 4 (адрес параметра) + 256 (результат-строка) + < размер служебной области > ~ 270 (байт).

Вариант с использованием перестановок:

Procedure reverse2(var ss: string; n: integer);

Var temp: char;

Begin

if n< =length(ss) div 2 then

begin

temp: =ss[n];

ss[n]: =ss[length(ss)-n+l];

ss[length(ss)-n+1]: =temp;

reverse2(ss, n+1);

end;

End;

Размер фрейма активации для этого варианта:

V=4(адрес 1-го параметра)+2(копия 2-го параметра) + 1 (локальная переменная)+< размер служебной области> ~17 (байт).

Следовательно второй вариант предпочтительней.

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

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

Лекция15.Тип данных запись(2 часа)