Иногда рекурсия приближается к парадоксу. Например, существуют рекурсивные определения. С первого взгляда может показаться, что в этом случае нечто определяется через себя самоё. Из этого получился бы если не парадокс, то порочный круг и бесконечное возвращение к началу. На самом деле, правильно сформулированное рекурсивное определение никогда не приводит ни к тому, ни к другому. Дело в том, что рекурсивные определения никогда не определяют предметы или идеи через них самих — вместо этого они используют более простые версии определяемого понятия. Чтобы вам стало понятнее, что я имею в виду, приведу несколько примеров рекурсивных определений.
Один из часто встречающихся типов рекурсии в повседневной жизни — это прекращение какого-либо дела на время, с тем, чтобы сделать более простое дело, зачастую того же типа, что и первое. Вот хороший пример. У директора фирмы на столе стоит сложный телефон, по которому ему могут звонить несколько человек одновременно. Директор разговаривает с А; в этот момент звонит Б. Директор спрашивает А, может ли тот подождать минутку. На самом деле, ему совершенно все равно, может ли А подождать, — он просто нажимает кнопку и переключается на разговор с Б. Тут звонит В. Теперь уже и Б приходится подождать. Так может продолжаться до бесконечности — однако не будем увлекаться. Предположим, разговор с В закончился; наш директор «выталкивается» обратно и продолжает беседу с Б. Между тем, на другом конце провода А в раздражении барабанит пальцами по столу и слушает сладенькие мелодии, передающиеся по телефону чтобы скрасить его ожидание… Самый простой случай был бы, если бы звонок Б закончился и директор наконец вернулся бы к А. Но может случиться, что когда он разговаривает с Б, звонит Д. Б снова оказывается «протолкнутым» в стек ждущих своей очереди. По окончанию разговора с Д директор вернется к Б, а затем к А. Разумеется, здесь он действует совершенно механически — я пытаюсь показать рекурсию в самой чистой форме.
Проталкивание, выталкивание и стек
В предыдущем примере я ввел основные термины, касающиеся рекурсии, по крайней мере так, как их понимают специалисты по компьютерам: проталкивание, выталкивание и стек. Все эти термины связаны между собой. Они вошли в обиход в конце 1950-х годов в составе ИПЛ, одного из первых языков для искусственного разума. Вы уже встречались с «проталкиванием» и «выталкиванием» в Диалоге; однако я объясню здесь эти термины еще раз. Протолкнуть означает прервать работу над очередным делом, при этом не забывая, на чем вы остановились, и начать работать над следующим заданием. Обычно говорят, что новое дело находится на «низшем уровне» по сравнению с предыдущим занятием. Вытолкнуть означает обратное: прекратить работу на одном уровне и вновь приняться за работу на высшем уровне, начав с того, на чем вы остановились.
Как же нам удается точно помнить, где мы были на каждом уровне? Для этого мы сохраняем нужную информацию в стеке. Таким образом, стек — это просто табличка, сообщающая нам 1) на чем было прервано каждое незаконченное занятие (на компьютерном жаргоне это называется «обратный адрес») и 2) какие факты нам надо знать о моменте, когда задание было прервано («переменная связка»). Когда вы выталкиваетесь наверх, чтобы возобновить работу над чем-либо, именно стек восстанавливает ваш контекст, чтобы вы не потерялись. В примере с телефонными звонками стек сообщает вам, кто ждет вас на каждой линии и в каком месте беседа была прервана.
К слову сказать, происхождение терминов «проталкивать», «выталкивать» и «стек» восходит к образу сложенных один на другой подносов в кафетерии (stack по-английски — куча, стеллаж). Обычно внизу такой стопки помещается нечто вроде пружины, поддерживающей верхний поднос приблизительно на одном и том же уровне — так что каждый новый поднос «проталкивает» всю стопку вниз, в то время как при снятии одного подноса все стопка «выталкивается» наверх.
Еще один пример из повседневной жизни. Когда вы слушаете новости по радио, часто случается, что слово предоставляется иностранному корреспонденту. «Говорит Адам Зайчиков из Минска, Беларусь.» Адам, в свою очередь, включает запись местного репортера, берущего у кого-то интервью: «С вами Иван Петровский; я нахожусь недалеко от того места, где совершилось ограбление банка. Предоставляю слово главе оперативной группы…» Теперь вы уже тремя уровнями ниже. Может случиться, что и тот, у кого берут интервью, тоже включит какую-то запись. Спускаться таким образом по уровням, слушая новости — дело весьма обычное; мы даже не всегда отдаем себе отчет в том, что сообщение на одном уровне прерывается. Наше подсознание следит за этим автоматически. Может быть, это так легко для нас потому, что уровни здесь сильно отличаются друг от друга. Если бы они были схожими, мы потеряли бы ориентацию в мгновение ока.
Пример более сложной рекурсии — наш Диалог. Ахилл и Черепаха присутствовали там на каждом из нескольких различных уровней. Иногда они читали историю, в которой сами были действующими лицами. Тут было легко запутаться, и приходилось напрягать все внимание, чтобы не потерять нить. «Так, посмотрим… настоящие Ахилл и Черепаха все еще наверху, в вертолете господина Удачи — вторичные сейчас находятся в картине Эшера — а теперь они нашли ту книгу и начали читать; значит, Ахилл и Черепаха, блуждающие по звуковым дорожкам „Маленького гармонического лабиринта“, — третичны. Стоп — я, кажется, пропустил один уровень…» Чтобы уследить за рекурсией в Диалоге, нам необходим сознательный мысленный стек, подобный такому, какой изображен ниже.
Рис. 26. Диаграмма структуры Диалога «Маленький гармонический лабиринт». Вертикальные спуски — проталкивание, подъемы — выталкивание. Обратите внимание, что диаграмма напоминает структуру абзацев в Диалоге. Из нее ясно следует, что угроза Удачи так никогда и не была выполнена — Ахилл и Черепаха остались висеть между небом и землей. Некоторые читатели, возможно, придут в отчаяние от этого недовытолкутого проталкивания, в то время как другие даже глазом не моргнут. В рассказе Баховский музыкальный лабиринт тоже был оборван слишком, скоро — но Ахилл не заметил в этом ничего особенного. Нарастающее напряжение почувствовала только Черепаха.
Стеки в музыке
Говоря о «Маленьком гармоническом лабиринте», мы должны обсудить следующую идею, которая косвенно упоминалась в диалоге: мы слушаем музыку рекурсивно — в частности, мы создаем мысленный стек ключей, и каждая новая модуляция проталкивает туда новый ключ. Если развить эту идею дальше, получится, что мы хотим услышать последовательность ключей в обратном порядке — выталкивая из стека ключи один за другим, пока не дойдем до основной тональности. Это, разумеется, преувеличение, но в нем есть доля правды. Слушая музыку, любой сколько-нибудь музыкальный человек автоматически создает минимальный стек с двумя ключами. В этом «коротком стеке» содержатся основная тональность, а также ближайший «псевдоключ», тональность, в которой композитор «находится» в данный момент. (Иными словами, самый общий и самый «местный» ключи. Таким образом слушатель знает, когда достигается тоника, и испытывает от этого сильное чувство «удовлетворения». В отличие от Ахилла, он также чувствует разницу между местным разрешением напряжения — например, разрешением в псевдотонику — и глобальным разрешением. Псевдоразрешение нагнетает напряжение, вместо того, чтобы его ослабить. Оно подобно иронической шутке — совсем как спасение Ахилла от ящериц, в то время как мы знаем, что на самом деле и он, и Черепаха все еще ожидают погибели от ножа месье Удачи.
Поскольку напряжение и разрешение — душа и сердце музыки, существует множество примеров на эту тему. Давайте взглянем на пару примеров из Баховской музыки. Бах написал много композиций в форме «ААББ»: обе части пьесы повторяются дважды. Возьмем джигу из «Французской сюиты #5», типичную для данной формы. Ее энергично введенная танцевальной мелодией тоника — «соль». Вскоре, однако, модуляция в части А вводит тесно связанную с первоначальной тональность «ре» (доминанта). Когда часть А кончается, мы находимся в тональности «ре». Может даже показаться, что пьеса заканчивается в ключе «ре»! (По крайней мере, так может подумать Ахилл.) Но тут случается странная вещь — мы внезапно прыгаем обратно к началу, снова в тональность «соль», и снова слышим тот же переход в «ре». Но тут случается странная вещь — мы внезапно прыгаем обратно к началу, снова в тональность «соль», и снова слышим тот же переход в «ре».
Затем следует часть Б. В результате тематического сдвига, мелодия здесь начинается с «ре», словно «ре» являлось тоникой с самого начала — но в конце концов, мелодия модулирует обратно в «соль»; это означает, что мы выталкиваемся обратно в тонику, и что часть Б оканчивается именно так, как надо. Тут случается это забавное повторение, отбрасывая нас, безо всякого предупреждения, назад к «ре», и затем возвращаясь к «соль» еще раз. Тут случается это забавное повторение, отбрасывая нас, безо всякого предупреждения, назад к «ре», и затем возвращаясь к «соль» еще раз.
