1.1. Рекурсивное программирование. Среди упомянутых вы-

ше методов формализации понятия вычислимой функции метод

Тьюринга — Поста основан на уточнении понятия процесса вы-

числений, для чего используются абстрактные «машины», опи-

санные в точных математических терминах. Другой подход (ме-

тод Черча — Клини) основан на понятии рекурсивной функции.

Рекурсивная функция задается с помощью рекурсивных опреде-

лений. Рекурсивное определение позволяет связать искомое зна-

чение функции для заданных аргументов с известными значения-

ми той же функции при некоторых других аргументах. Эта связь

устанавливается с помощью универсального механизма рекурсии,

задающего механическую процедуру поиска значений функции.

Двум подходам к определению вычислимых функции соответст-

вуют два метода программирования этих функций — операторное

и рекурсивное программирование. При операторном методе про-

грамма представляет собой явно выписанную последовательность

описаний действий гипотетической вычислительной машины (по-

следовательность операторов, команд и т. п.).

Язык Фортран — типичный  представитель операторных

языков. С другой стороны, рекурсивная программа — это сово-

купность рекурсивных определений, задающих рекурсивную

функцию, для которой аргументами служат начальные данные

программы, а значением — результат выполнения программы.

Известный язык рекурсивного программирования — язык Лисп —

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

языках комбинируют оба метода программирования. Так, Пас-

каль — операторный язык с возможностью рекурсивного про-

граммирования, предоставляемой механизмом рекурсивных про-

цедур и функций.

Известным примером рекурсивно определяемой функции яв-

ляется факториальная функция FACT: N N, где N — мно-

жество целых неотрицательных чисел:

FACT (х) =

Эту же функцию можно запрограммировать в некотором рекурси-вном языке, базирующемся на механизме рекурсивных функций языка

Паскаль:

FACT (a),

FACT (х) = если х = 0 то 1 иначе х  FACT (х — 1),

где а — некоторое целое неотрицательное число.

Выполнение этой программы для некоторого значения а (пусть

а = 4) может быть осуществлено следующим образом. В обе час-

ти рекурсивного определения вместо х подставляется 4, после чего

вычисляется правая часть определения. Вычисление правой час-

ти начинается с вычисления логического выражения. Если его

значение 1 (истина), то вычисляется левое функциональное выра-

жение (стоящее после то), а если его значение 0 (ложь) — вы-

числяется правое выражение (стоящее после иначе). Вычисление

функционального выражения сводится к его упрощению, т. е.

выполнению всех возможных вычислений. Если в упрощенном

выражении остается вхождение символа определяемой функции

FACT, то осуществляется переход к новому шагу выполнения

программы. На этом шаге вхождение FACT(m), где m, — значение

внутри скобок после упрощения, заменяется левым (m = 0) или

правым (m > 0) функциональным выражением, в котором все

вхождения х заменены на m. Упрощения продолжаются до тех

пор, пока не будет получено выражение, не содержащее FACT

(в пашем случае это выражение — число).

FACT (4) = если 4 = 0 то 1 иначе 4FACT(4 — 1) =

         = 4FACT (3) = 4  (если 3=0 то 1 иначе

           3FACT (3 - 1)) = 4  3  FACT (2) =

         = 12(если 2 = 0 то 1 иначе 2FACT(2 — 1)) =

         = 122FACT(1) = 24(если 1 = 0 то 1

         иначе 1FACT(1 - 1)) =

         = 241FACT(0) = 24(если 0 =

         = 0 то 1 иначе 0FACT(0 — 1)) = 24

Вычисление рекурсивной программы может завершиться за ко-

нечное число шагов с результатом, равным значению запрограм-

мированной функции для заданных аргументов (начальных зна-

чений переменных), но может и продолжаться бесконечно. В по-

следней случае значение функции не определено.

Еще один популярный пример — рекурсивная программа, вы-

числяющая значения функции Аккермана А: :

А (а, b),

А (х, у) = если х =0 то у + 1 иначе В (х, у),

В (х, у) = если у =0 то А (х - 1, 1) иначе С (х, у),

C(x,y) = A(x-1,A(x,y-1)).

Эта программа состоит из главного вызова А (а, b) и трех оп-

редeлений функций. Первое определение описывает функцию Ак-

кeрмана А череа вспомогательную функцию В, которая задана,

в свою очередь, с помощью функций A и С. Последняя также оп-

ределена через функцию А. Здесь каждое определение, взятое

отдельно, само на себя не ссылается, но имеет место взаимная ре-

курсия, когда каждая из функций A, В, С косвенно определена

через саму себя.

Выполнение этой программы для а = b = 1 выглядит сле-

дующим образом (некоторые мелкие упрощения не выписаны):

А (1, 1) = если 1 = 0 то 2 иначе В (1, 1) = В (1, 1) = если

1=0 то A (0, 1) иначе С (1, 1) = С (1,   1) =

=A (0, А (1, 0)) = А (0, (если 1 = 0 то 1 иначе

В (1, 0))) = А (0, В (1, 0)) = А (0, (если 0 = 0 то

А (0, 1)  иначе С (1, 0)) = А ( 0, Л (0,1) ) =

=Л (0, (если 0=0 то 2 иначе В(О, 1))) = А (0, 2) =

= если 0 = 0 то 2+4 = 1 иначе В(0, 2) = 3.

Отметим, что в этом примере функциональное выражение со-

держит несколько вхождений символов определяемых функций

(например, А (0, А (1, 0)) ). Использованное нами правило под-

становки в этом случае требует, чтобы замещалось левое из самых

внутренних вхождений (в случае упомянутого терма — вхожде-

ние А (1,0)).

Операторный и рекурсивный методы программирования имеют

свои достоинства и недостатки, обсуждать которые — не наша

задача (см. например, ставшую классической работу Дж. Бэку-

са, обратившего внимание на преимущества функционального

стиля программирования). Но чтобы подготовить почву для та-

кого обсуждения, полезно формализовать оба метода. Стандарт-

ные схемы являются моделями операторных программ. Сейчас

мы введем рекурсивные схемы, которые служат абстракциями

рекурсивных программ, а в последующих параграфах проведем

сравнение этих моделей.

1.2. Определение рекурсивной схемы. Так же, как и стан-

дартные схемы, рекурсивные схемы определяются в некотором

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

схем, включает четыре счетных множества