Рекурсивные объекты

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

Рекурсивные определения представляют собой мощный аппарат в математике. Например:

1. Натуральные числа:

а) 1 есть натуральное число,

б) число, следующее за натуральным, есть натуральное число.

2. Деревья:

а) 0 есть дерево ("пустое дерево"),

б) если А 1 и А 2 - деревья, то построение, содержащее вершину с двумя ниже расположенными деревьями, опять дерево.

3. Функция n! "факториал" (для неотрицательных целых чисел):

а) 0!=1,

б) n >0: n!= n ·(n -1)!

Мощность рекурсивного определения заключается в том, что оно позволяет с помощью конечного высказывания определить бесконечное множество объектов. Аналогично, с помощью конечной рекурсивной программы можно описать бесконечное вычисление, причем программа не будет содержать явных повторений. В общем виде рекурсивную программу Р можно выразить как некоторую композицию Р из множества операторов С (не содержащих Р) и самой Р: Р=Р[С,Р].

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

· При каждом вызове такой функции в нее должны передаваться модифицированные данные;

· На каком-то этапе должен быть прекращен вызов данной функции. Рекурсивный процесс должен шаг за шагом так упрощать задачу, чтобы в конце для нее появилось нерекурсивное решение.

· После завершения каждого вызова рекурсивной функции в точку возврата должен передаваться некоторый результат для дальнейшего использования.

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

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

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

Р: if X then P[C,P]

Основной способ доказательства конечности некоторого повторяющегося процесса:

1. Определяется функция f(x), такая, что из f(x) 0 следует истинность условия окончания цикла.

2. Доказывается, что при каждом прохождении цикла f(x) уменьшается.

Аналогично доказывается и окончание рекурсии - показывается, что Р уменьшает f(x), такую, что из f(x) 0 следует истинность В.

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

Дата добавления: 2014-01-07