После того, как читатель смог почувствовать вкус волшебства рекурсивных функций, настало время рассмотреть другую знаменитую рекурсивную задачу, которая по популярности уступает разве что задаче вычисления факториала - задачу о Ханойских Башнях. Но, в отличие от строго математической подоплёки факториала, эта задача подаётся в изящной "мифологической" упаковке.
Итак, сначала легенда.
Где-то на Дальнем Востоке (очевидно, в Ханое, хотя некоторые версии это отрицают) находится старинный храм, во дворе которого установлены три столба. Столбы могут быть алмазными, а могут быть и просто деревянными в зависимости от источника, однако для нас это значения не имеет. В Начале Времён на левом столбе находились 64 золотых диска, все разного диаметра - самый большой диск внизу, самый маленький - сверху. Задача монахов - обитателей храма и хранителей секрета - состоит в том, чтобы перенести все диски с левого столба на правый, пользуясь средним столбом, как вспомогательным, так, чтобы никогда диск большего диаметра не находился над диском меньшего диаметра. В конце концов диски на правом столбе должны занимать точно такое же положение, какое они занимали на левом.
Легенда гласит, что в тот момент, когда задача будет выполнена, наступит Конец Времён.
Ну что ж, в попытке приблизить Конец Времён, начнём решать задачу. Необходимо оговориться, что "магическое" число 64 не будет играть никакой роли в нашем решении - напротив, мы постараемся решить задачу для общего случая - любого числа дисков.
Обозначим столбы A,B и C так, что A - будет исходным (левым) столбом, С - конечным (правым), а В - вспомогательным (средним). Сразу же раскроем карты: "фокус" решения будет состоять в том, что столбы на разных этапах будут меняться ролями. В какой-то момент средний столб В из вспомогательного превратится в исходный, в начальный или в конечный, и точно такие же метаморфозы будут происходить со столбами А и С. Зачем ? Для того, чтобы обеспечить "рекурсивность" решения.
Начнём с самого простого случая - на столбе А лежит только один диск. Здесь даже Лисп не понадобится - просто перенесём диск на столб С и пойдём смотреть, как в небе одна за другой начнут гаснуть звёзды. Однако, как вы уже догадались, этот случай и будет основным - базисным - случаем рекурсии. В общем виде (и это исключительно важно!) случай с одним диском может быть описан так:
Перенести один диск с исходного столба на конечный.
Заметьте, что мы намеренно отказались от обозначений А и С, потому что, как и было сказано, наши столбы будут постоянно меняться ролями: в некий промежуточный момент времени исходным столбом может быть не только А (левый), а конечным - не только С (правый).
Более интересный случай: на столбе А находятся два диска. Вспомним основной принцип рекурсивного решения. Мы уже умеем решать более простую задачу (то есть задачу с одним диском), а значит, решив её, сможем перенести и оставшийся диск. Однако, не всё здесь так просто, как в случае с факториалом. Взгляните на рисунок:
Из рисунка становится ясно, что маленький диск нужно было сначала положить на средний столб В, затем перенести большой диск на столб С и, наконец, перенести маленький диск на столб С, так, чтобы он оказался над большим, тем самым не нарушив правил. Получается, что базисный случай рекурсии в этом случае не так прост, как могло показаться сначала. Действительно, для того, чтобы решить задачу с двумя дисками, нужно прежде всего решить задачу с одним диском, но так, чтобы этот шаг не помешал следующему.
Вот здесь-то и вступает в силу "смена ролей" дисков. Для первого шага решения (то есть задачи с одним маленьким диском) роль конечного столба будет играть вспомогательный столб В. Вспомните, как решался базисный случай рекурсии: перенести диск с исходного столба на конечный. В нашем случае это будет означать: перенести маленький диск со столба А на столб В.
Далее мы снова решаем задачу с одним диском (теперь уже с большим). И опять нам известно, как решить эту простую задачу, но на этот раз роль конечного столба будет играть столб С (потому что он свободен - столб В уже занят маленьким диском): перенесём большой диск с исходного столба А на конечный столб С.
Оставшаяся задача снова проста: перенести маленький диск с начального столба (теперь его роль досталась столбу В) на конечный - С:
Задача с двумя дисками решена!
Повторимся: для того, чтобы решить эту "сложную" задачу с двумя дисками, мы три раза решили "простую" - базисную - задачу с одним диском, каждый раз меняя роли, которые играли столбы. Общее решение начинает проясняться, но для того, чтобы сформулировать его окончательно, нам понадобится разобрать задачу с тремя дисками.
Из рисунка ясно, что для решения задачи с тремя дисками, нам нужно сначала решить более простую задачу с двумя дисками. Но ведь мы её только что решили! Применяя рекурсию (о, эта всемогущая рекурсия!), предоставим задаче с двумя дисками "решаться самой по себе". Разница с предыдущим решением будет заключаться в том, что в качестве столба назначения для задачи с двумя дисками мы будем использовать средний столб В, а в качестве вспомогательного столба - С. Это сделано для того, чтобы на последнем этапе (переносе самого большого диска) "последний" (или, если хотите, настоящий) столб назначения С был свободен.
Обратите внимание: если при решении задачи с двумя дисками мы пользовались термином "шаг" (что означало перенос одного диска), то здесь мы будем пользоваться термином "этап". Это будет означать не просто перенос какого-либо одного диска, а решение целой задачи - более "лёгкой" задачи с двумя дисками.
Итак, первый этап решения задачи с тремя дисками - это решение задачи с двумя дисками со столбом В в роли конечного.
Следующим шагом станет перенос самого большого диска на столб назначения - С. Это очень простая задача:
И, наконец, нам снова нужно решить задачу переноса двух дисков, на сей раз со столба В (исходного) на столб С (конечный), используя столб А в качестве вспомогательного:
Задача с тремя дисками решена. В ходе её решения мы два раза воспользовались уже решенной задачей с двумя дисками и один раз простой задачей с одним диском. Как обычно, столбы всё время менялись ролями.
Пришло время сформулировать алгоритм решения задачи:
Дано N дисков на исходном столбе А.
1. Перенесём N-1 дисков на столб В (то есть решим более простую задачу, а, вернее, предоставим рекурсии решать её "самостоятельно"), используя столб С в качестве вспомогательного.
2. Перенесём самый большой диск со столба А на конечный столб С.
3. Перенесём N-1 дисков со столба В на конечный столб С, используя столб А в качестве вспомогательного.
Попробуем немного приблизиться к описанию этого алгоритма на Лиспе. Для этого, вместо названий столбов - А,В,С - будем пользоваться их ролями в алгоритме. Так, изначально столб А играет роль исходного (назовём его FROM), столб В играет роль вспомогательного (назовём его SPARE), а столб С играет роль конечного (назовём его TO).
Из описания видно, что на этапе 1 в качестве столба назначения используется столб, роль которого называется SPARE, а в качестве вспомогательного используется столб TO.
На втором этапе самый большой диск со столба FROM переносится на столб TO.
На третьем этапе столб SPARE становится исходным, а столб TO - конечным.
Всё это достаточно запутано, но попробуем переписать алгоритм, используя роли столбов вместо названий, а затем углубимся на один шаг "в рекурсию":
Дано N дисков на исходном столбе FROM.
1. Перенесём N-1 дисков на столб SPARE, используя столб TO в качестве вспомогательного.
2. Перенесём самый большой диск со столба FROM на конечный столб TO.
3. Перенесём N-1 дисков со столба SPARE на конечный столб TO, используя столб FROM в качестве вспомогательного.
Ключевой момент! Чтобы решить первый этап алгоритма, а именно:
"Перенесём N-1 дисков на столб SPARE, используя столб TO в качестве вспомогательного",
мы должны применить тот же самый алгоритм к задаче с N-1 диском, учитывая, что в качестве столба назначения теперь выступает столб SPARE, а роль вспомогательного играет столб TO. Вот, что получается:
Дано N-1 дисков на исходном столбе FROM.
1. Перенесём N-2 дисков на столб TO, используя столб SPARE в качестве вспомогательного.
2. Перенесём самый большой диск со столба FROM на конечный столб SPARE.
3. Перенесём N-2 дисков со столба TO на конечный столб SPARE, используя столб FROM в качестве вспомогательного.
Второй этап прост - углубляться некуда. А на третьем этапе мы снова можем расшифровать алгоритм переноса N-1 диска, учитывая, что теперь роль исходного столба играет SPARE, конечного - TO, а вспомогательного - FROM:
Дано N-1 дисков на исходном столбе SPARE.
1. Перенесём N-2 дисков на столб FROM, используя столб TO в качестве вспомогательного.
2. Перенесём самый большой диск со столба SPARE на конечный столб TO.
3. Перенесём N-2 дисков со столба FROM на конечный столб TO, используя столб SPARE в качестве вспомогательного.
Теперь, когда принцип работы рекурсии в задаче о Ханойских башнях понятен, можно рассмотреть и реализацию алгоритма на Лиспе. Функция tower-of-hanoi и есть рекурсивный алгоритм, записанный в терминах Лиспа:
(defun tower-of-hanoi (n from to spare)
(cond ((= n 1) (move-disk from to))
(t (tower-of-hanoi (- n 1) from spare to)
(move-disk from to)
(tower-of-hanoi (- n 1) spare to from))
)
)
Как видите, функция tower-of-hanoi использует вспомогательную функцию
move-disk, задача которой напечатать движение очередного диска[1]:
(defun move-disk (from to)
(format t "~%Move a disk from ~a to ~a." from to)
)
Следующий рисунок служит одной единственной цели - обратить внимание читателя на изменение порядка параметров функции в рекурсивных вызовах. Этот порядок строго соответствует смене ролей столбов, описанной в приведённом алгоритме. Мы не зря расшифровали следующий шаг "углубления в рекурсию": это было сделано именно для того, чтобы смена ролей стала более наглядной. Теперь то же самое можно увидеть и на рисунке:
Чтобы запустить программу, нужно вызвать функцию tower-of-hanoi, помня о том, что в самом начале столб from называется А, столб to называется С, а столб spare называется В:
(tower-of-hanoi 2 ‘A ‘C ‘B)
Мы поставили перед Лиспом задачу с двумя дисками, и вот, что он напечатает:
Move a disk from A to B.
Move a disk from A to C.
Move a disk from B to C.
Это было очевидно. А вот, что получится, если поставить задачу с тремя дисками:
(tower-of-hanoi 3 ‘A ‘C ‘B)
Move a disk from A to C.
Move a disk from A to B.
Move a disk from C to B.
Move a disk from A to C.
Move a disk from B to A.
Move a disk from B to C.
Move a disk from A to C.
Небольшая таблица поможет нам лучше понять то, что здесь происходит:
В общем случае для того, чтобы решить задачу с числом дисков, равным N, нужно совершить 2^N-1 передвижений. Поспешу успокоить тех читателей, которые волнуются, что монахи закончат свою работу в обозримом будущем: для того, чтобы переместить все 64 диска, монахам понадобится совершить 18446744073709551615 передвижений. Даже если предположить, что на перемещение одного диска они тратят только одну секунду (возможно, это очень трудолюбивые монахи), то свою работу они закончат не раньше, чем через 585 миллиардов лет.
[1] Встроенная функция Лиспа format помогает напечатать текст в заданном формате, подставляя значения переменных на соответствующие места.