Одна из основных способностей, необходимых в компьютерном программировании, — это умение заметить, когда два явления схожи в широком смысле, поскольку это ведет к модуляризации — разбиванию задачи на несколько естественных подзадач. Представьте, например, что вам надо исполнить одну за другой серию схожих операций. Вместо того, чтобы записывать каждую из них, мы можем написать петлю (или цикл), которая говорит компьютеру, что, выполнив некое множество операций, он должен вернуться к началу и повторять тот же процесс снова и снова, пока не будет выполнено некое условие. Тело петли — определенные повторяющиеся команды — не должно быть жестко установленным; в нем допустимы предсказуемые вариации. Примером может служить несложная проверка того, является ли число N простым. Вначале вы делите число N на 2, потом на 3, 4, 5, и так далее, до N-1. Если N не делится ни на одно из этих чисел, то N — простое число.
Обратите внимание на то, что каждый шаг цикла здесь похож на другие, но не тождественен им. Заметьте также, что количество шагов варьируется в зависимости от N, поскольку петля постоянной длины не могла бы служить общей проверкой для простых чисел. Существуют два критерия для «прерывания» петли: (1) если N делится без остатка на какое-либо число, то петля прерывается и ответом будет «НЕТ»; (2) если мы достигли N-1 и N «выжило», не разделившись, то петля прерывается и ответом будет «ДА».
Основная идея петель такова: повторять серию родственных шагов до тех пор, пока не выполняется определенное условие. Иногда максимальное количество шагов в петле заранее известно, а иногда мы начинаем и ждем, пока петля прервется. Второй тип петель, который я называю свободными, опасен, поскольку условия для прерывания петли могут никогда не выполниться, в результате чего компьютер застрянет на так называемом «бесконечном цикле». Разница между свободными и ограниченными петлями, или циклами, является одним из важнейших понятий в теории вычислительной техники; этой теме будет посвящена глава «БлууП и ФлууП и ГлууП».
Петли могут быть также вложены одна в другую. Предположим, например, что мы хотим найти все простые числа от 1 до 5000. Для этого можно написать вторую петлю, повторяющую описанную проверку снова и снова, начиная с N=1 и кончая N=5000. Таким образом, у нашей программы будет структура «петли-в-петле». Хорошие программисты обычно составляют программы именно в этом «стиле». Подобные вложенные петли встречаются в инструкциях для сборки простых предметов, а также в таких видах деятельности, как вязание и вышивание, где маленькие петли повторяются несколько раз внутри больших петель, которые, в свою очередь, тоже повторяются несколько раз… Результатом петли на нижнем уровне может быть всего пара стежков, в то время как петля на высшем уровне производит большую часть изделия.
В музыке также часто встречаются вложенные одна в другую петли — например, когда гамма (маленькая петля) проигрывается несколько раз, возможно, сдвинутая при этом выше или ниже. Последние части Пятого концерта Прокофьева и Второй симфонии Рахманинова содержат длинные пассажи, в которых разные инструменты одновременно проигрывают гаммы-петли в быстром, среднем и медленном темпе — эффект получается потрясающий. Гаммы Прокофьева идут вверх, гаммы Рахманинова — вниз. Выбор за вами!
Более широким, чем понятие петли, является понятие подпрограммы или процедуры, которое мы уже затронули. Группа операций при этом рассматривается как одно целое, носящее определенное название — например, процедура УКРАШЕННОЕ СУЩЕСТВИТЕЛЬНОЕ. Как мы видели в СРП, процедуры могут вызывать одна другую по имени — таким образом кратко описывается последовательность необходимых операций. Это — основа модульности в программировании. Разумеется, модульность существует также в качественных системах звуковоспроизведения, в мебели, в живых клетках и в человеческом обществе — везде, где есть иерархическая структура.
Чаще всего, нам нужна процедура, которая может варьироваться в зависимости от контекста. Такая процедура может согласовывать выбор действий с информацией, хранящейся в памяти, или же действовать согласно данному списку параметров. Иногда используются оба эти метода. В терминах СРП выбор последовательности действий называется выбором пути. СРП, улучшенная добавлением параметров и условий, контролирующих выбор путей внутри нее, называется Увеличенная Схема Переходов (УСП). Скорее всего, вы предпочтете УСП вместо СРП, если вам надо получить осмысленные русские предложения на основе набора слов; при этом базой служит грамматика, выраженная в УСП. Параметры и условия позволят вам ввести определенные семантические ограничения, запрещающие случайные соединения типа «неблагодарная закуска». Однако мы еще вернемся к этой теме в главе XVIII.
Классическим примером рекурсивной процедуры с параметрами может служить программа для выбора лучших ходов в шахматной партии. Лучшим ходом можно, по-видимому, считать тот, что оставляет противника в наихудшей ситуации. Таким образом, проверка лучшего хода весьма проста: представьте себе, что вы сделали ход… а теперь мысленно переверните доску и оцените позицию с точки зрения вашего противника. Но каким образом оценивает позицию ваш противник? Он ищет свой лучший ход. Это значит, что он мысленно перебирает все возможные варианты и оценивает их, как ему кажется, с вашей точки зрения, надеясь, что вы найдете их опасными для себя. Обратите внимание, что мы определили «лучший ход» рекурсивно: то, что лучше для одного противника, хуже для другого. Рекурсивная процедура, занятая поисками лучшего хода, пробует один ход за другим и каждый раз вызывает саму себя в качестве противника! В этой роли она пробует следующий ход, и вызывает себя в качестве противника противника — то есть, снова себя самой.
Эта рекурсия может спуститься на несколько уровней — но рано или поздно она должна достичь дна! Как можно оценить позицию на доске, не заглядывая вперед? Для этого существуют несколько полезных критериев, таких как, например, количество фигур с обеих сторон, количество и тип фигур, находящихся под атакой, контроль над центром, и так далее. Оценивая позицию таким образом в начале, «на дне», рекурсивный генератор ходов может вернуться наверх и оценить позицию с точки зрения каждого отдельного хода. Таким образом, один из параметров в этом самовызове должен определить, на сколько ходов вперед просчитывать. Самый внешний вызов процедуры будет использовать некое установленное извне значение для этого параметра. После этого, каждый раз, когда процедура будет вызывать саму себя, параметр, указывающий на какое количество ходов вперед надо просчитывать каждый вариант, будет сокращаться на единицу. Таким образом, когда параметр достигнет нуля, процедура последует по другому пути и обратится к не-рекурсивной оценке.
В программах подобного «игрового» типа, каждый анализируемый ход порождает «дерево анализа вариантов», где сам ход является стволом, возможные ответы — основными ветвями, контр-ответы — ветвями потоньше, и так далее. На рис. 38 я показал простое дерево анализа, иллюстрирующее начало игры в крестики-нолики. Существуют способы, позволяющие избежать анализа каждой ветви до конца. В искусстве выращивания шахматных деревьев лидируют люди, а не компьютеры. Известно, что лучшие игроки просчитывают варианты на относительно небольшое число ходов, в сравнении с компьютером — и играют при этом намного лучше! В начале развития компьютерных шахмат считалось, что не пройдет и десяти лет, как компьютер (или программа) станет чемпионом мира. Однако, эта цель не достигнута и по сей день… Это может служить еще одним подтверждением очень рекурсивного
Закона Хофштадтера:
На любое дело требуется больше времени, чем казалось в начале, даже если вы учитывали при этом закон Хофштадтера.
