Рекурсия
Материал из OpenWiki.
Объект, частично состоящий или определяемый с помощью самого себя.
Рекурсивные определения представляют собой мощный аппарат в математике. Например:
1. Натуральные числа:
) 1 есть натуральное число,
б) число, следующее за натуральным, есть натуральное число.
2. Деревья:
а) 0 есть дерево ("пустое дерево"),
б) если А1 и А2 - деревья, то построение, содержащее вершину с двумя ниже расположенными деревьями, опять дерево.
3. Функция n! "факториал" (для неотрицательных целых чисел):
а) 0!=1,
б) n>0: n!=n·(n-1)!
Мощность рекурсивного определения заключается в том, что оно позволяет с помощью конечного высказывания определить бесконечное множество объектов. Аналогично, с помощью конечной рекурсивной программы можно описать бесконечное вычисление, причем программа не будет содержать явных повторений. В общем виде рекурсивную программу Р можно выразить как некоторую композицию Р из множества операторов С (не содержащих Р) и самой Р: Р=Р[С,Р].
Для выражения рекурсивных программ удобнее пользоваться процедурами или функциями. Если некоторая процедура Р содержит явную ссылку на саму себя, то ее называют прямо рекурсивной, если же Р ссылается на другую процедуру В, содержащую ссылку на Р, то Р называют косвенно рекурсивной.
Как правило с процедурой связывают множество локальных переменных, которые определены только в этой процедуре. При каждой рекурсивной активации процедуры порождается новое множество локальных, связанных переменных. Хотя они имеют те же самые имена, что и соответствующие элементы локального множества предыдущего "поколения" этой процедуры, их значения отличны от последних, а любые конфликты по именам разрешаются с помощью правил, определяющих область действия идентификаторов: идентификатор всегда относится к самому последнему порожденному множеству переменных.
Рекурсивные процедуры могут приводить к не заканчивающимся вычислениям. Очевидно основное требование, чтобы рекурсивное обращение к Р управлялось некоторым условием Х, которое в какой-то момент становится ложным.
