12

Иванова Г.С., Ничушкина Т.Н.

Конспект лекций

по курсу "Алгоритмические языки и программирование".

Тема "Рекурсия".

Глава 1. Рекурсия. Основные положения.

1.1. Рекурсивные алгоритмы.

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

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

Пример 1. Определение отношения "Кубик А находится в башне над кубиком В."

1. Если кубик А лежит непосредственно на кубике В, то кубик А находится в

башне над кубиком В.

2. Если кубик А лежит непосредственно на кубике С и этот кубик находится в

башне над кубиком В, то кубик А находится в башне над кубиком В.

Первое утверждение носит название базисного. Базисное утверждение нерекурсивно.

Рис. 1

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

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

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

а) Проверяем первое утверждение "Синий кубик находится в башне над зеленым, если он лежит на зеленым". Оно ложно, следовательно, переходим к проверке второго.

б) Второе утверждение "Синий кубик находится в башне над зеленым, если синий кубик лежит на красном, а красный находится в башне над зеленым" требует доказательства того, что красный кубик находится в башне над зеленым. А это значит, что надо вновь применить правило 1 и проверить, находится ли красный кубик непосредственно на зеленом. Поскольку это положение истинно, значит истинно и то, что синий кубик находится в башне над зеленым.

Пример 2. Рекурсивное определение понятия "нечетное число".

Базисное утверждение: Число 1 является нечетным.

Рекурсивное утверждение: Если i является нечетным числом, то нечетными являются и числа i-2 и i+2.

Определить, являются ли числа 7 и -7 нечетными.

а) 7-2 -> 5 5-2 -> 3 3-2 -> 1 1 - нечетное число, следовательно, число 7 - нечетное.

б) -7+2 -> -5 -5+2 -> -3 -3+2 -> -1 -1+2 -> 1 - нечетное число, следовательно, число -7 - нечетное.

Очень важной областью применения рекурсии является синтаксис языков программирования.

Пример 3. Определение целой константы.

Базисное утверждение: Числа от 0 до 9 являются целыми константами.

Рекурсивное утверждение: Добавление десятичной цифры к записи целой константы образует новую целую константу.

Соответствующая форма Бэкуса-Наура записывается следующим образом:

<цифра>:: = 0|1|2|3|4|5|6|7|8|9 - базис

<целая константа>:: =<цифра>|<целая константа> - рекурсивная часть

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

В программировании рекурсия используется как при определении структур данных, так и при разработке алгоритмов.

1.2. Рекурсивные процедуры и функции. Взаиморекурсия.

Рекурсивной процедурой называется такая процедура, которая в процессе выполнения вызывает сама себя.

Различают следующие виды рекурсии:

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

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

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

1. сначала задаются прототипы подпрограмм с параметрами, за которыми вместо тела подпрограммы следует forword;

2. затем описываются тела этих подпрограмм (причем параметры второй раз можно уже не описывать).

Например, описание взаиморекурсивных процедур A и B можно выполнить следующим образом: procedure B(j:byte);forward;

procedure A(j:byte);

begin ... B(i); ... end;

procedure B;

begin ... A(j); ... end;

Рис.2.

1.3. Фрейм активации.

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

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

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

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

V= <размер области параметров>+2(адрес возврата)+2..8(для сохранения содержимого регистров)+<размер области локальных переменных>+<размер строки результата, если это функция, возвращающая результат - строку>

Пример 4. Вычисление НОД двух чисел (алгоритм Евклида).

Базисное утверждение: Если два числа равны, то их НОД равен этим числам.

Рекурсивное утверждение: НОД двух чисел равен НОД их разности и меньшего из чисел.

Таким образом, редуцирование происходит при замене большего из чисел на их разность.

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

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.

Рис.3.

При выполнении программы Паскаль будет использовать стек, в который будут записываться фреймы активации каждого вызова. Например, для а=20 и b=12 стек будет выглядеть следующим образом (запись в стек идет словами, то есть по 2 байта, как и изображено на рисунке):

Рис.4.

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

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.

Пример 5. Определение корней уравнения y=x²-2 на заданном отрезке методом половинного деления.

Для простоты будем считать, что отрезок задается таким образом, что корень на нем есть (иначе основная программа должна содержать проверку наличия корня).

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

Базисное утверждение: Если абсолютная величина функции в середине отрезка не превышает заданного значения точности, то координата середины отрезка и есть корень.

Рекурсивное утверждение: Корень расположен между серединой отрезка и тем концом, значение функции в котором по знаку не совпадает со значением функции в середине отрезка.

program ex;

var a,b,eps,x:real;

procedure root(a,b,eps:real,var r):real;

var f,x:real;

begin x:=(a+b)/2; f:=x*x-1;

if abs(f)>eps then

begin

if (a*a-1)*f>0 then root(x,b,eps,r)

else root(a,x,eps,r)

end;

end;

begin readln(a,b,eps);

root(a,b,eps,x);

writeln(x);

end.

Рис.5.

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

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

Базисные утверждения: Строка допустима, если она пустая.

Строка не допустима, если обнаружен не допустимый символ.

Рекурсивное утверждение: Если текущий символ строки допустим, то допустимость строки определяется оставшейся частью строки.

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

program ex2;

var s:string;

function f_char(st:string):boolean;forward;

function f_value(st:string):boolean;