А(4.2)

А(4,1.

А(1.3)

•Л13. А(4,11)

АР, Д(4.0))

АЮ. А(1.2))

«4

»13

13.1) =13 А(2, А(3,01) =5

А(2,1) =5

А(1. а(2.0)) =3 о

А(1,1) =3

А(0. а(1,0)1=2 i

а(0.щ=2

AtO. А(М)1 "3

А(2,6)-

А(1. A(2.4l)

11

»э

А(1. А!2.3))

АН. А(2,2)) «7

А[1, А(2,1)) "S..

Atl, А(1,1)1 = 3

А О 1 2 3 4 5 6 7 8 Э 10 11 12 13 . . ,

1 2 3 4 5 6 7 8. S ID-Ц 12 13 14 . • .

2 3 4 Б 6 7 8 Э 10 11 12 13 14 15 . .• ,

3 5 7 S 11 13 15 17 19 21 23 25 27 29 . , ,

бЛз о

Рис. 3.5.1. Вычисление функции Аккермана А (4, 2).

3. Q(M, N)=Q{M, М), если M<.N. Ясно, что никакое разбиение М не может содержать слагаемого N, большего М.

4. Q{M, M)=1+Q(M, М-1). С5та,естБует только одно разбиение М со слагаетш, равным М. Все другие разбиения М имеют наибольшее слагаемое NM-1.

5. Q(M, N)=Q(M, N-l)+Q(M-N, N). Это означает, что любое разбиение М с наибольшим слагаемым, меньшим или равным Л, или не содержит в качестве слагаемого - в этом случае данное разбиение также входит в число Q(M, N-1), или содержит N - при этом остальные слагаемые образуют разбиение числа М-Л.

Уравнения 1-5 рекурсивно определяют функцию Q{M, N). Они определяют Р{М), так как P{M)=Q{M, М).

Каждый, кто знаком с Фортраном, знает, что в этом языке нельзя производить рекурсивных обращений к подпрограммам. Казалось бы, это должно препятствовать нам в реализации вычисления рекурсивной функции Q{M, N) на Фортране. Однако ниже представлена программа реализации итеративного алгоритма на Фортране, правильно вычисляющая Q(M, N).

INTEGER FUNCTION O(M.N) INTEGER M. N, VAL(M.N) IF (M .LT. 1 .OR. N .LT. 1) GO TO 70 DO 60 K = 1.M DO sd L = 1,N f- IF (K .EQ. 1 .OR. L .EQ. 1) GO TO 40

IF (K-L) 10.20.30 10 VAL(K,L) = VAL(K.I

GO VO SO zo- VAUK,L) = 1+VAL(K,K-1)

UO TO SO

SO VAL(K,L)=VAL{K.L-1)+VAL(K-L,L)

GO TO so 40 VAL(K.L) = 1

60 CONTINUE

60 CONTINUE

Q = VAUM.N)

RETURN 70 WRITE (6,1000) M,N 100D FORMAT (1H0.21H НЕВЕРНЫЕ АРГУМЕНТЫ. 216)

RETURN

• Заметим, что для вычисления Q(M, Л) сначала вычисляются и запоминаются в виде массива VAL(/, /) все предьщущие значения Q{M, N) для /<УИ и JN. Таким образом, то, что кажется рекурсивными обращениями (например, строка 10), на самом деле есть только обращения к массиву.

Предыдущий пример показывает, что с некоторым усилием можно написать на Фортране программу реализации рекурсивной функции. С другой стороны, сопоставьте это с естественностью реализации той же функции на Алголе:

bealnlf М<1 OR N<1 then PRINT НЕВЕРНЫЕ АРГУМЕНТЫ

elaelfM=10RN=1 lhenQP:=1

в18вНМ<М lhBnQP:=QP(M.M)

elseUMU ШлОР:=1+ОР(М,М-1)

else ClP:eClP(M.U-1}.+QPlM-N.NJ

Идентификаторы языка

Рекурсия естественным образом встречается во всех областях машинной математики. Например, в Фортране идентификатор (переменная, функция или имя подпрограммы) обычно определен как последовательность, содержащая от одной до шести букв или цифр, первая из которых - буква. В Алголе идентификаторы определены почти так же, но без ограничения на длину. Определение идентифи-

катора обычно задается так.

(цифра) : =0njm4J5J6J7J8I9

(буква) : AJB/CI. . ./X/F/Z (идентификатор) : = (буква) (идентификатор) : = (идентификатор) (цифра) (идентификатор) : = (идентификатор) (буква)

Обращаем внимание на то, что в последних двух определениях идентификатор выражен сам через себя.

Формулы, аналогичные приведенным выше, используются компиляторами Алгола, чтобы определять, все ли переменные в исходной программе правильно сформированы. Предположим, что функция VAR определяется таким образом, что для любой цепочки символов X, VAR (X)=«YES» тогда и только тогда, когда X - правильный идентификатор; в противном случае VAR(X)=«NO». Функция VAR определяется рекурсивно следующим образом:

YES, если Х = <буква>;

VДPY-J " = <Цифра>;

I VAR, (У), если Х = У <буква>; , N0 в остальных случаях;

здесь X=F (цифра) означает, что X - цепочка символов, последний из которых цифра.

Поиск в глубину и в ширину

Во многих сетевых теоретических задачах нужно найти произвольное остовное дерево в сети G (например, для определения, связна ли G) или проверить каждое ребро G хотя бы по разу. Тарьян предложил простой рекурсивный алгоритм для этих двух задач. Алгоритм назьшается поиском в глубину. Его основная идея может быть применена во многих ситуациях, когда нужно найти какой-то оптимум в результате поиска по большой структуре типа дерева. Проиллюстрируем этот алгоритм (алгоритм DPS) с сетью на рис. 3.5.2, которая представлена списками смежности.

Алгоритм DFS выражен рекурсивно и требует в качестве начальных данных сеть G, произвольную начальную вершину V и начальные значения /=0 и Т=0.

Algorithm DFS (Поиск в глубину). Найти остовное дерево Т в связной сети G, вершины которой перенумерованы 1, 2, . . ., М. Алгоритм является рекурсивным и обращается к себе самому оператором CALL DFS(1/), вершина V - новая вершина, которую нужно просмотреть; если VISIT (1F)=/, тогда вершина W была 1-й новой просмотренной вершиной: VISIT (IF) не определена, если W не просмотрена.