Черепаха: Мне кажется, я чувствую знакомый запах… Не вытаскин ли это?

Ахилл: И правда… откуда этот запах?

Черепаха: По-моему, это здесь… О! Я нашла целую бутыль! Это он и есть!

Ахилл: Вытаскин! Давайте напьемся с горя!

Черепаха: Надеюсь, что это не протолкин — они до того похожи, что их трудно различить.

Ахилл: Что вы сказали про Толкиена?

Черепаха: Я ничего подобного не говорила. У вас уже галлюцинации начинаются…

Ахилл: Б-батюшки мои! Надеюсь, что нет… Ну что же, поехали!

(И друзья начинают отхлебывать вытаскин (или протолкин?) — и вдруг — ХЛОП! Кажется, это-таки оказался вытаскин…)

Черепаха: Забавная история, ничего не скажешь. Вам понравилось?

Ахилл: Так, ничего себе… Интересно, выбрались ли они в конце концов из ямы страшного Мажотавра? Бедняга Ахилл, он так хотел опять стать большим.

Черепаха: Не беспокойтесь — они выбрались, и Ахилл снова вырос до своих обычных размеров. Вытаскин оказался весьма кстати…

Ахилл: Не знаю, не знаю… Единственное, в чем я сейчас АБСОЛЮТНО уверен, это в том, что нам не мешало бы найти нашу бутылочку с настойкой — у меня уже давно горло пересохло. И ничто так не утоляет жажду, как выталкивающая настойка

Черепаха: Она к тому же известна своим тонизирующим  действием. Известны случаи, когда народ просто с ума по ней сходил. Например, когда в начале века продуктовая фабрика Шёнберга перестала производить джин с тоником и начала производство какао, вы не представляете себе, какой из-этого поднялся шум — настоящая какаофония!

Ахилл: Воображаю… Но давайте же искать настойку! Погодите — взгляните-ка на этих ящериц на столе! Не кажется ли вам, что в них есть что-то необычное?

Черепаха: Не вижу ничего особенного. А что такое?

Ахилл: Посмотрите: они вылезают из плоскости картины без помощи выталкивающей настойки! Как они это делают?

Черепаха: Разве я вам не говорила? Вы можете вылезти из картины, двигаясь перпендикулярно ее плоскости. Ящерки научились лезть НАВЕРХ, когда они хотят выбраться из двухмерного мира альбома.

Ахилл: Может быть, мы можем так же выбраться из этой картины Эшера наружу?

Черепаха: Разумеется — нужно только подняться уровнем выше. Хотите попытаться?

Ахилл: Все что угодно, только бы попасть домой! Я уже сыт по горло этими занимательными приключениями.

Черепаха: В таком случае, следуйте за мной наверх.

(И они поднимаются на один уровень.)

Ахилл: Хорошо быть снова у себя дома… Но постойте, здесь что-то не то! Это вовсе не мой дом — это ВАШ дом, г-жа Черепаха!

Черепаха: Вы правы — и я предовольна, так как перспектива тащиться от вас к себе домой мне совершенно не улыбалась. Я прямо-таки валюсь с лап от усталости.

Ахилл: Что ж, я как раз не возражаю против небольшой прогулки; так что, мне кажется, все сложилось довольно удачно.

Черепаха: Я думаю! Вот это удача так удача!

ЧТО ТАКОЕ РЕКУРСИЯ? То, что было проиллюстрировано в диалоге «Маленький гармонический лабиринт»: вложенность схем одна в другую и варианты этой вложенности. Рекурсия — весьма общее понятие. (Рассказы внутри рассказов, фильмы внутри фильмов, картины внутри картин, матрешечки внутри матрешек (даже скобки внутри скобок!) — вот лишь несколько симпатичных примеров.) Однако читатель должен иметь в виду, что в этой главе термин «рекурсия» употребляется в ином значении, чем в главе III, и эти два значения связаны только косвенно. Эта связь должна проясниться к концу главы.

Иногда рекурсия приближается к парадоксу. Например, существуют рекурсивные определения. С первого взгляда может показаться, что в этом случае нечто определяется через себя самоё. Из этого получился бы если не парадокс, то порочный круг и бесконечное возвращение к началу. На самом деле, правильно сформулированное рекурсивное определение никогда не приводит ни к тому, ни к другому. Дело в том, что рекурсивные определения никогда не определяют предметы или идеи через них самих — вместо этого они используют более простые версии определяемого понятия. Чтобы вам стало понятнее, что я имею в виду, приведу несколько примеров рекурсивных определений.

Один из часто встречающихся типов рекурсии в повседневной жизни — это прекращение какого-либо дела на время, с тем, чтобы сделать более простое дело, зачастую того же типа, что и первое. Вот хороший пример. У директора фирмы на столе стоит сложный телефон, по которому ему могут звонить несколько человек одновременно. Директор разговаривает с А; в этот момент звонит Б. Директор спрашивает А, может ли тот подождать минутку. На самом деле, ему совершенно все равно, может ли А подождать, — он просто нажимает кнопку и переключается на разговор с Б. Тут звонит В. Теперь уже и Б приходится подождать. Так может продолжаться до бесконечности — однако не будем увлекаться. Предположим, разговор с В закончился; наш директор «выталкивается» обратно и продолжает беседу с Б. Между тем, на другом конце провода А в раздражении барабанит пальцами по столу и слушает сладенькие мелодии, передающиеся по телефону чтобы скрасить его ожидание… Самый простой случай был бы, если бы звонок Б закончился и директор наконец вернулся бы к А. Но может случиться, что когда он разговаривает с Б, звонит Д. Б снова оказывается «протолкнутым» в стек ждущих своей очереди. По окончанию разговора с Д директор вернется к Б, а затем к А. Разумеется, здесь он действует совершенно механически — я пытаюсь показать рекурсию в самой чистой форме.

В предыдущем примере я ввел основные термины, касающиеся рекурсии, по крайней мере так, как их понимают специалисты по компьютерам: проталкивание, выталкивание и стек. Все эти термины связаны между собой. Они вошли в обиход в конце 1950-х годов в составе ИПЛ, одного из первых языков для искусственного разума. Вы уже встречались с «проталкиванием» и «выталкиванием» в Диалоге; однако я объясню здесь эти термины еще раз. Протолкнуть означает прервать работу над очередным делом, при этом не забывая, на чем вы остановились, и начать работать над следующим заданием. Обычно говорят, что новое дело находится на «низшем уровне» по сравнению с предыдущим занятием. Вытолкнуть означает обратное: прекратить работу на одном уровне и вновь приняться за работу на высшем уровне, начав с того, на чем вы остановились.

Как же нам удается точно помнить, где мы были на каждом уровне? Для этого мы сохраняем нужную информацию в стеке. Таким образом, стек — это просто табличка, сообщающая нам 1) на чем было прервано каждое незаконченное занятие (на компьютерном жаргоне это называется «обратный адрес») и 2) какие факты нам надо знать о моменте, когда задание было прервано («переменная связка»). Когда вы выталкиваетесь наверх, чтобы возобновить работу над чем-либо, именно стек восстанавливает ваш контекст, чтобы вы не потерялись. В примере с телефонными звонками стек сообщает вам, кто ждет вас на каждой линии и в каком месте беседа была прервана.

К слову сказать, происхождение терминов «проталкивать», «выталкивать» и «стек» восходит к образу сложенных один на другой подносов в кафетерии (stack по-английски — куча, стеллаж). Обычно внизу такой стопки помещается нечто вроде пружины, поддерживающей верхний поднос приблизительно на одном и том же уровне — так что каждый новый поднос «проталкивает» всю стопку вниз, в то время как при снятии одного подноса все стопка «выталкивается» наверх.

Еще один пример из повседневной жизни. Когда вы слушаете новости по радио, часто случается, что слово предоставляется иностранному корреспонденту. «Говорит Адам Зайчиков из Минска, Беларусь.» Адам, в свою очередь, включает запись местного репортера, берущего у кого-то интервью: «С вами Иван Петровский; я нахожусь недалеко от того места, где совершилось ограбление банка. Предоставляю слово главе оперативной группы…» Теперь вы уже тремя уровнями ниже. Может случиться, что и тот, у кого берут интервью, тоже включит какую-то запись. Спускаться таким образом по уровням, слушая новости — дело весьма обычное; мы даже не всегда отдаем себе отчет в том, что сообщение на одном уровне прерывается. Наше подсознание следит за этим автоматически. Может быть, это так легко для нас потому, что уровни здесь сильно отличаются друг от друга. Если бы они были схожими, мы потеряли бы ориентацию в мгновение ока.