Рекурсивные методы

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

Рассмотрим классическую задачу, известную в литературе под названием «Ханойская башня» (рис. 50).

На площадке (назовем ее А) находится пирамида, составленная из дисков уменьшающегося от основания к вершине размера.

Эту пирамиду в том же виде требуется переместить на площадку В. При выполнении этой работы необходимо соблюдать следующие ограничения:

• перекладывать можно только по одному диску, взятому сверху пирамиды;

• класть диск можно либо только на основание площадки, либо на диск большего размера;

• в качестве вспомогательной можно использовать площадку С.

Название «Ханойская башня» связано с легендой, согласно которой в давние времена монахи одного ханойского храма взялись переместить по этим правилам башню, состоящую из 64 дисков. С завершением их работы наступит конец света. Монахи все еще работают и, надеемся, еще долго будут работать!

Нетрудно решить эту задачу для двух дисков. Обозначая перемещения диска, например, с площадки А на В так: А → В, напишем алгоритм для этого случая

А→С; А→В; С→В.

Всего 3 хода! Для трех дисков алгоритм длиннее:

А→В; А→С; В→С; А→В; С→А; С→В; А→В.

В этом случае уже требуются 7 ходов.

Подсчитать количество ходов (N) для k дисков можно по следующей рекуррентной формуле:

N(1) = 1; N(k) = 2х N(k - 1) + 1.

Например, N(10) = 1023, N(20) = 104857. А вот сколько перемещений нужно сделать ханойским монахам:

N(64) = 18446744073709551615.

Попробуйте прочитать это число.

Теперь составим программу, по которой машина рассчитает алгоритм работы монахов и выведет его для любого значения п (количества дисков). Пусть на площадке А находятся п дисков. Алгоритм решения задачи будет следующим:

1. Если п = 0, то ничего не делать.

2. Если п > 0, то переместить п — 1 диск на С через В;

переместить диск с А на В (А → В)

переместить п — 1 диск с С на В через А.

При выполнении пункта 2 последовательно будем иметь три состояния (рис. 51).

Описание алгоритма имеет явно рекурсивный характер

Перемещение n дисков описывается через перемещение п — 1 диска. А где же выход из этой последовательности рекурсивных ссылок алгоритма самого на себя? Он в пункте 1, каким бы ни показалось странным его тривиальное содержание.

А теперь построим программу на Паскале. В ней имеется рекурсивная процедура Напоу, выполнение которой заканчивается только при п = 0. При обращении к процедуре используются фактические имена площадок, заданные их номерами: 1, 2, 3. Поэтому на выходе цепочка перемещений будет описываться в таком виде:

1→2 1→3 2→3 и т.д.

Это одна из самых удивительных программ! Попробуйте воcпроизвести ее на машине. Проследите, как изменяется число ходов с ростом п. Для этой цели можете сами добавить в программу счетчик ходов и в конце вывести его значение или печатать ходы с порядковыми номерами.