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

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

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

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

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

   Рисунок 1 – Схема размещения кубиков в башне

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

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

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

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

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

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

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

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

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

б) Второе утверждение "Синий кубик находится в башне над зеленым, если синий кубик лежит на красном, а красный находится в башне над зеленым" требует доказательства того, что красный кубик находится в башне над зеленым. А это значит, что надо вновь применить правило 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. Рекурсивные процедуры и функции. Взаиморекурсия

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

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

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

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

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

1) сначала задаются прототипы подпрограмм с параметрами;

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

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

Рисунок 2 – Пример взаиморекурсии

void A (int j);

Void B (int j)

  {...

A (j);

...

}

Void A(int j)

{ ….

B(j);

…..

}

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

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

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

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

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

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

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

Пример 4. Вычисление наибольшего общего делителя двух чисел (алгоритм Евклида).

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

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

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

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

 

 

Рисунок 3 – Схема алгоритма подпрограммы- процедуры нахождения наибольшего общего делителя двух чисел                                                                          

 

Текст программы:

 

#include "stdafx.h"

#include <stdio.h>

void nod(int a,int b,int &r)

{

if(a==b) r=a;

else

{

if (a>b)nod(a-b,b,r);

else nod(a,b-a,r);

}

}

int main(int argc, char* argv[])

{

int a,b,r;

puts("input two integer value ");

scanf("%d %d",&a,&b);

nod(a,b,r);

     printf("\n nod %7d %7d = %7d\n",a,b,r);

  return 0;

}

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

 

Рисунок 4 – Структура фрейма активации

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

#include "stdafx.h"

#include <stdio.h>

int nod(int a,int b)

{

if(a==b) return a;

else

{

 if (a>b) return nod(a-b,b);

      else  return nod(a,b-a);

}

}

int main(int argc, char* argv[])

{

  int a,b;

puts("input two integer value ");

scanf("%d %d",&a,&b);

printf("\n nod %7d %7d = %7d\n",a,b,nod(a,b));

return 0;

}

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