Рекурсивным называется объект, частично состоящий или определяемый с помощью самого себя.
Рекурсивные определения в математике представляют собой мощный аппарат. Примером могут служить: натуральные числа, деревья и определенные функции.
1. Натуральные числа:
а) 0 есть натуральное число,
б) число, следующее за натуральным, есть натуральное число.
2. Деревья:
а) 0 есть дерево (его называют "пустым деревом"),
б) если t1и t2 — деревья, то построение, содержащее вершину с двумя ниже расположенными деревьями, опять же дерево.
3. Функция “факториал” п!(для неотрицательных целых чисел):
а) 0!,
б) n>0: n! = n*(n-1)!
Мощность рекурсивного определения заключается в том, что оно позволяет с помощью конечного высказывания определить бесконечное множество объектов. Аналогично с помощью конечной рекурсивной программы можно описать бесконечное вычисление, причем программа не будет содержать явных повторений. Однако рекурсивные алгоритмы лучше всего использовать, если в решаемой задаче, вычисляемой функции или структуре обрабатываемых данных рекурсия уже присутствует явно. В общем виде рекурсивную программу Р можно выразить как некоторую композицию Р из множества операторов S (не содержащих Р) исамой Р:
P º P[S, P] (1)
Для выражения рекурсивных программ необходимо и достаточно иметьпонятие процедуры или функции, поскольку они позволяют дать любому оператору имя, с помощью которого к нему можно обращаться. Если некоторая процедура Р содержит явную ссылку на саму себя, то ее называют прямо рекурсивной, если же Р ссылается на другую процедуру Q, содержащую (прямую или косвенную) ссылку на Р, то Р называют косвенно рекурсивной. Поэтому по тексту программы рекурсивность не всегда явно определима.
Как правило, с процедурой связывают множество локальных объектов, т.е. множество переменных, констант, типов и процедур, которые определены только в этой процедуре и вне ее не существуют или не имеют смысла. При каждой рекурсивной активации такой процедуры порождается новое множество локальных связанных переменных. Хотя они имеют те же самые имена, что и соответствующие элементы локального множества предыдущего "поколения" этой процедуры, их значения отличны от последних, а любые конфликты по именам разрешаются с помощью правил, определяющих область действия идентификаторов: идентификатор всегда относится к самому последнему порожденному множеству переменных. Это же правило справедливо и для параметров процедуры, по определению связанных с самой процедурой.
Подобно операторам цикла, рекурсивные процедуры могут приводить к незаканчивающимся вычислениям, и поэтому этой проблеме следует уделить особое внимание. Очевидно, для того чтобы работа когда-либо завершилась, необходимо, чтобы рекурсивное обращение к Р управлялось некоторым условием В, которое в какой-то момент перестает выполняться. Поэтому более точно схему рекурсивных алгоритмов можно представить в любой из следующих форм:
P º IF B THEN P [S, P], (2)
P º P [S, IF B THEN P]. (3)
Основной способ доказательства конечности некоторого повторяющегося процесса таков:
1. Определяется функция f(х)(х — множество переменных), такая, что из условия f(х)£ 0 следует истинность условия окончания цикла (с предусловием или постусловием).
2. Доказывается, что при каждом прохождении цикла f(х)уменьшается.
Аналогично доказывается и окончание рекурсии — показывается, что Р уменьшает f(x), такую, что из f(х)£ 0 следует ùВ.В частности, наиболее надежный способ обеспечить окончаниепроцедуры — ввести в нее некоторый параметр (значение), назовем его n, и при рекурсивном обращении к Р в качестве параметра задавать n - 1. Если в этом случае в качестве В используется n > 0, то окончание гарантировано. Это опять же выражается двумя схемами:
Р(n) º IF n > 0 THEN Р [S, Р (n - 1)], (4)
Р(р) º Р [S, IF n > 0 THEN Р (n - 1)]. (5)
В практических приложениях важно убедиться, что максимальная глубина рекурсий не только конечна, но и достаточно мала. Причиной является то, что каждая рекурсивная активация процедуры Р требует памяти для размещения ее переменных. Кроме этих локальных переменных нужно еще сохранять текущее "состояние вычислений", чтобы можно было вернуться в него по окончании новой активации Р.
