ГЕДЕЛЬ, ЭШЕР, БАХ: эта бесконечная гирлянда - Хофштадтер Даглас Р. - Страница 49

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 используется для расширения самого ряда. Получающаяся последовательность, мягко выражаясь, беспорядочна, и чем дальше мы продвигаемся, тем бессмысленнее она кажется. Это один из тех странных случаев, когда естественное определение приводит к весьма странному результату — хаос, полученный упорядоченным способом. При этом возникает вопрос: нет ли в кажущемся хаосе какого-то скрытого порядка? Разумеется, из определения следует, что некий порядок существует. Но интересно, есть ли иной способ определить данный ряд — если повезет, нерекурсивно?

Чудес рекурсии в математике множество, и я не собираюсь здесь говорить о них подробно. Я остановлюсь лишь на двух особо интересных случаях с которыми мне пришлось столкнуться. Речь пойдет о двух графиках. Один из них — часть моих исследований по теории чисел. Другой возник в процессе моей работы над докторской диссертацией по физике твердых тел. Особенно поразительно то, что эти графики находятся в родстве между собой.

Первый (рис. 32) — график функции, которую я называю INT (x). Здесь она дана для x между 0 и 1. Чтобы найти x между любой другой парой чисел n и n+1, вы должны вычислить INT (x-n) и затем снова прибавить n. Как видите, структура этого графика прерывиста. Она состоит из бесконечного числа изогнутых кусочков, уменьшающихся ближе к краям. Если вы посмотрите на любой такой кусочек попристальнее, вы увидите, что перед вами — копия целого графика, только слегка изогнутая! Последствия этого удивительны; одним из них является то, что график INT состоит исключительно из копий себя самого, вложенных одна в другую до бесконечности. Если вы возьмете любую, сколь угодно малую часть графика, у вас окажется полная копия всего графика — на самом деле, бесконечное количество таких копий!

Рис. 32. График функции INT(x). В точках рациональных значений x функция прерывается.

Вы можете подумать, что INT слишком эфемерна, чтобы существовать в действительности, поскольку она состоит лишь из копий самой себя. Ее определение выглядит слишком круговым.

Как начинается эта функция? Где ее «исток»? Это очень интересный вопрос. Важно отметить, что, описывая INT человеку, никогда не видевшему графика этой функции, недостаточно просто сказать, что она состоит из копий себя самой. Вторая, нерекурсивная часть описания должна содержать сведения о том, где эти копии лежат внутри графика и каким образом они деформированы по отношению к нему. Только взятые вместе, эти два аспекта INT определяют ее структуру. Точно так же, чтобы определить числа Фибоначчи, нам понадобились две строчки — одна, определяющая рекурсию, и другая, определяющая дно — первоначальные значения функции. Приведу конкретный пример: если вы замените одно из двух первоначальных значений на 3 вместо 1, то получите совершенно иную последовательность, известную под названием ряда Лукаса:

В определении INT «дну» соответствует рисунок (рис. 33а), состоящий из множества квадратов, указывающих, где находятся копии и каким образом они деформированы. Я называю это «скелетом» INT. Чтобы построить INT на основе скелета, вы должны действовать следующим образом. Сначала для каждого квадрата надо проделать две операции: (1) вложите туда уменьшенную и изогнутую копию скелета, следуя направлению изогнутой линии внутри; (2) сотрите квадрат-рамку и линию внутри него. Закончив этот процесс для каждого квадрата первоначального скелета, вы получите вместо одного большого скелета множество скелетов-«деток». Теперь тот же процесс повторяется уровнем ниже, для каждого скелета-детки. Затем то же самое повторяется еще раз, и еще, и еще… В пределе вы приближаетесь к точному графику INT, хотя никогда его не достигаете. Снова и снова вкладывая скелет графика внутрь себя самого, вы постепенно строите график «из ничего». Но, по сути, «ничто» не было таковым — оно было рисунком.