Как видите, бесконечной регрессии не произошло, так как по крайней мере на одной из дорожек внутри СРП СВЕРХУКРАШЕННОЕ СУЩЕСТВИТЕЛЬНОЕ мы не встретились с вызовом самого СВЕРХУКРАШЕННОГО СУЩЕСТВИТЕЛЬНОГО. Конечно, мы могли бы упорствовать в выборе нижней дорожки внутри СВЕРХУКРАШЕННОГО СУЩЕСТВИТЕЛЬНОГО — тогда бы нам никогда не удалось закончить работу, подобно тому, как нам не удалось полностью раскрыть сокращение БОГ. Однако если мы выбираем дорожки наугад, подобной бесконечной регрессии не случается.
«Спуск на дно» и гетерархии
Мы только что описали основные различия между круговыми и рекурсивными определениями — в последних всегда есть определенная часть без автореферентности. Таким образом, рано или поздно мы коснемся дна: наша цель — построение объекта, отвечающего определению — будет достигнута. Существуют и другие, менее прямые, чем самовызовы, пути для получения рекурсивности в СРП. Примером может служить картина Эшера «Рисующие руки» (рис. 135), где каждая процедура вызывает не саму себя, а другую. Например, можно представить СРП под названием ПРИДАТОЧНОЕ ПРЕДЛОЖЕНИЕ, вызывающую СВЕРХУКРАШЕННОЕ СУЩЕСТВИТЕЛЬНОЕ, когда ей понадобится дополнение для переходного глагола — с другой стороны, высшая дорожка СВЕРХУКРАШЕННОГО СУЩЕСТВИТЕЛЬНОГО может вызывать ОТНОСИТЕЛЬНОЕ МЕСТОИМЕНИЕ и затем ПРЕДЛОЖЕНИЕ каждый раз, когда нам потребуется придаточное предложение. Это пример косвенной рекурсии; он напоминает двухступенчатую версию парадокса Эпименида.
Нет нужды говорить, что может существовать также трио процедур, вызывающих одну другую по кругу — и так далее. Может существовать даже целая семья СРП, спутанных между собой и что есть силы вызывающих друг друга и самих себя. Программа со структурой, в которой нет «высшего уровня» или «монитора», называется гетерархией (в отличие от иерархии). Этот термин изобретен Уорреном Мак Каллохом, одним из первых кибернетиков, посвятивших себя изучению мозга и интеллекта.
Расширение узлов
Есть также и другая возможность представить СРП графически. Каждый раз, когда, двигаясь по одной из дорожек, вы попадаете в узел, вызывающий другую СРП, вы «расширяете» этот узел, заменяя его на уменьшенную копию требуемой СРП (см. рис. 28). После этого вы приступаете к исполнению этой уменьшенной СРП.
Рис. 28. СРП СВЕРХУКРАШЕННОЕ СУЩЕСТВИТЕЛЬНОЕ с одним рекурсивно расширенным узлом.
Выталкиваясь из расширенного узла, вы автоматически оказываетесь в нужном месте большой схемы. С другой стороны, находясь в маленькой схеме, вы можете конструировать внутри нее еще более миниатюрные СРП. Расширяя узлы по мере того, как вы в них попадаете, вы избегаете построения бесконечной схемы даже в том случае, когда СРП вызывает саму себя. Расширение узлов немного напоминает замену буквы в аббревиатуре на то слово, которое она представляет. Сокращение БОГ рекурсивно, но его дефект — или преимущество — заключается в том, что мы должны все время расширять букву «Б» и, таким образом, она никогда не достигнет «дна». Однако когда СРП является частью настоящей компьютерной программы, в ней всегда есть по крайней мере одна дорожка, избегающая как прямой, так и косвенной рекурсивности. Поэтому бесконечного регресса там не бывает. Даже самая гетерархическая программа рано или поздно заканчивается — иначе она вообще не работала бы! Она продолжала бы расширять узлы один за другим до скончания веков.
Диаграмма G и рекурсивные ряды
Бесконечные геометрические структуры могут быть определены именно так-как расширение узлов один за другим. Давайте попробуем определить бесконечную диаграмму — назовем ее «диаграммой G». Воспользуемся следующим условным обозначением, в двух узлах напишем просто букву «G», которая, однако, будет представлять всю диаграмму G. На рис. 28 показана диаграмма G, использующая такую условную нотацию. Если мы захотим представить эту диаграмму более явно, мы должны расширить каждый узел, обозначенный буквой G, то есть заменить его на уменьшенную копию той же диаграммы G (см. рис. 29 б). Эта версия диаграммы G «второго порядка» дает нам некоторое представление о том, как бы выглядела конечная, невыполнимая диаграмма G. На рис. 30 показана большая часть диаграммы G; все узлы пронумерованы снизу вверх и слева направо. Внизу добавлены два дополнительных узла под номерами 1 и 2. У этого бесконечного «дерева» есть некоторые весьма интересные математические свойства. Двигаясь по нему справа налево, мы получаем знаменитый ряд чисел Фибоначчи:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233…
Этот рад был открыт в 1202 году Леонардом из Пизы, сыном Боначчи — отсюда Филиус Боначчи или, сокращенно, Фибоначчи.
Рис. 29. а) Диаграмма G, нерасширенная; б) Диаграмма G, расширенная один раз; в) Диаграмма H, нерасширенная; г) Диаграмма H, расширенная один раз один раз
Рис. 30. Диаграмма G, расширенная далее. Узлы пронумерованы.
Это числа описываются рекурсивно при помощи следующей пары формул:
FIBO (n) = FIBO (n — 1) + FIBO (n — 2) for n > 2
FIBO (n) = FIBO (2) = 1
Рис. 31. СРП для чисел Фибоначчи
Таким образом, вы можете вычислить ФИБО(15) с помощью ряда рекурсивных вызовов описанной в этой схеме процедуры. Это рекурсивное определение касается дна, когда вы доходите до явно выраженных ФИБО(1) и ФИБО(2). Для этого надо пройти по схеме назад, к меньшим и меньшим значениям n. Пятиться раком довольно неудобно, вместо этого можно начать с ФИБО(1) и ФИБО(2) и идти вперед, складывая два предыдущих числа, пока вы не получите ФИБО(15). Так вам не придется следить за стеком.
Но это еще не самое интересное свойство диаграммы G! Ее структура может быть целиком закодирована в следующем рекурсивном определении.
G(n) = n-G(G(n-1)) для n>0
G(0) = 0
Каким образом эта формула G(n) отражает структуру дерева? Очень просто: если вы начнете строить дерево, помещая G(n) под n для всех значений n, у вас получится диаграмма G. На самом деле, именно так я и открыл эту диаграмму. Я занимался исследованием функции G; однажды, пытаясь ускорить вычисления, я решил представить уже имеющиеся у меня значения в форме дерева. К моему удивлению оказалось, что это дерево обладает очень аккуратной геометрической рекурсивностью.
Еще более занимательным получается аналогичное дерево для функции H(n), имеющей на одно рекурсивное вложение больше, чем G:
H(n) = n - H(H(H(n-1))) для n>0
H(0) = 0
Таким образом, соответствующая диаграмма H косвенно определяется так, как показано на рис. 29 в). Правая ветвь отличается от G только тем, что в ней на один узел больше. И так далее, для любого количества вложений. Рекурсивные геометрические структуры проявляют замечательную регулярность, в точности соответствующую рекурсивным алгебраическим определениям.
Вопрос для любознательных читателей: представьте себе, что вы перевернули диаграмму G так, что у вас получилось ее зеркальное отображение. Номера узлов нового дерева возрастают теперь слева направо. Можете ли вы найти рекурсивное алгебраическое определение для такого «дерева-перевертыша»? Как насчет определения для перевертыша дерева H? И так далее?
Другая забавная задача включает пару рекурсивно сплетенных функций F(n) и M(n) — так сказать, супружеская парочка функций — определенных следующим образом:
F(n) = n-M(F(n-1))
для n>0
M(n) = n-F(M(n-1))
F(0) = 1, M(0) = 0
СРП для этих двух функций вызывают как друг друга, так и самих себя. Задача состоит в том, чтобы найти рекурсивные структуры диаграмм M и F. Они весьма просты и элегантны.
Хаотическая последовательность
Последний пример рекурсии в теории чисел приводит к небольшой загадке. Рассмотрим следующее рекурсивное определение функции.
Q(n) = Q(n-Q(n-1)) + Q(n-Q(n-2) для n>2
Q(1) = Q(2) = 1
Это напоминает определение Фибоначчи тем, что каждое новое значение является суммой двух предыдущих значений — но не ближайших! Вместо этого, два ближайших предыдущих значения указывают нам, насколько далеко мы должны отступить, чтобы найти числа, которые надо сложить для получения нового значения. Вот первые семнадцать чисел Q.
Чтобы получить следующее число, надо продвинуться налево (считая от многоточия), соответственно, на 9 и 10 шагов; вы получите 5 и 6 (отмеченные стрелками). Их сумма — 11 — и дает новое значение: Q(18). Странный процесс: список уже известных чисел Q используется для расширения самого ряда. Получающаяся последовательность, мягко выражаясь, беспорядочна, и чем дальше мы продвигаемся, тем бессмысленнее она кажется. Это один из тех странных случаев, когда естественное определение приводит к весьма странному результату — хаос, полученный упорядоченным способом. При этом возникает вопрос: нет ли в кажущемся хаосе какого-то скрытого порядка? Разумеется, из определения следует, что некий порядок существует. Но интересно, есть ли иной способ определить данный ряд — если повезет, нерекурсивно?
