Строгое определение некоторых понятий может опираться на то же понятие. Существует доступная математическая форма определений, согласно которой определяемое понятие используется как заголовок определения и как его элемент. Эта форма называется рекурсивной или индуктивной.
Рекурсия является особенно мощным средством в математических определениях. Известны примеры рекурсивных определений натуральных чисел, древовидных структур и некоторых функций.
Пример 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;
}
Как показывает опыт разработки и использования рекурсивных подпрограмм, объем используемой стековой памяти зависит как от размера фрейма активации, так и от количества вызовов рекурсивной подпрограммы. Поэтому, чтобы избежать переполнения стека, необходимо прикинуть возможный размер фрейма активации и хотя бы приблизительно подсчитать ожидаемое количество возможных активаций.