Гёдель, Эшер, Бах. Эта бесконечная гирлянда

Обратите внимание на то, что каждый шаг цикла здесь похож на другие, но не тождественен им. Заметьте также, что количество шагов варьируется в зависимости от N, поскольку петля постоянной длины не могла бы служить общей проверкой для простых чисел. Существуют два критерия для «прерывания» петли: (1) если N делится без остатка на какое-либо число, то петля прерывается и ответом будет «НЕТ»; (2) если мы достигли N-1 и N «выжило», не разделившись, то петля прерывается и ответом будет «ДА».

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

Петли могут быть также вложены одна в другую. Предположим, например, что мы хотим найти все простые числа от 1 до 5000. Для этого можно написать вторую петлю, повторяющую описанную проверку снова и снова, начиная с N=1 и кончая N=5000. Таким образом, у нашей программы будет структура «петли-в-петле». Хорошие программисты обычно составляют программы именно в этом «стиле». Подобные вложенные петли встречаются в инструкциях для сборки простых предметов, а также в таких видах деятельности, как вязание и вышивание, где маленькие петли повторяются несколько раз внутри больших петель, которые, в свою очередь, тоже повторяются несколько раз… Результатом петли на нижнем уровне может быть всего пара стежков, в то время как петля на высшем уровне производит большую часть изделия.

В музыке также часто встречаются вложенные одна в другую петли — например, когда гамма (маленькая петля) проигрывается несколько раз, возможно, сдвинутая при этом выше или ниже. Последние части Пятого концерта Прокофьева и Второй симфонии Рахманинова содержат длинные пассажи, в которых разные инструменты одновременно проигрывают гаммы-петли в быстром, среднем и медленном темпе — эффект получается потрясающий. Гаммы Прокофьева идут вверх, гаммы Рахманинова — вниз. Выбор за вами!

Более широким, чем понятие петли, является понятие подпрограммы или процедуры, которое мы уже затронули. Группа операций при этом рассматривается как одно целое, носящее определенное название — например, процедура УКРАШЕННОЕ СУЩЕСТВИТЕЛЬНОЕ. Как мы видели в СРП, процедуры могут вызывать одна другую по имени — таким образом кратко описывается последовательность необходимых операций. Это — основа модульности в программировании. Разумеется, модульность существует также в качественных системах звуковоспроизведения, в мебели, в живых клетках и в человеческом обществе — везде, где есть иерархическая структура.

Чаще всего, нам нужна процедура, которая может варьироваться в зависимости от контекста. Такая процедура может согласовывать выбор действий с информацией, хранящейся в памяти, или же действовать согласно данному списку параметров. Иногда используются оба эти метода. В терминах СРП выбор последовательности действий называется выбором пути. СРП, улучшенная добавлением параметров и условий, контролирующих выбор путей внутри нее, называется Увеличенная Схема Переходов (УСП). Скорее всего, вы предпочтете УСП вместо СРП, если вам надо получить осмысленные русские предложения на основе набора слов; при этом базой служит грамматика, выраженная в УСП. Параметры и условия позволят вам ввести определенные семантические ограничения, запрещающие случайные соединения типа «неблагодарная закуска». Однако мы еще вернемся к этой теме в главе XVIII.

Рекурсия в шахматных программах

Классическим примером рекурсивной процедуры с параметрами может служить программа для выбора лучших ходов в шахматной партии. Лучшим ходом можно, по-видимому, считать тот, что оставляет противника в наихудшей ситуации. Таким образом, проверка лучшего хода весьма проста: представьте себе, что вы сделали ход… а теперь мысленно переверните доску и оцените позицию с точки зрения вашего противника. Но каким образом оценивает позицию ваш противник? Он ищет свой лучший ход. Это значит, что он мысленно перебирает все возможные варианты и оценивает их, как ему кажется, с вашей точки зрения, надеясь, что вы найдете их опасными для себя. Обратите внимание, что мы определили «лучший ход» рекурсивно: то, что лучше для одного противника, хуже для другого. Рекурсивная процедура, занятая поисками лучшего хода, пробует один ход за другим и каждый раз вызывает саму себя в качестве противника! В этой роли она пробует следующий ход, и вызывает себя в качестве противника противника — то есть, снова себя самой.