Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

3.3. П
РИМЕРЫ РЕКУРСИВНЫХ ПРОГРАММ
 
Методика создания рекурсивных программ в общем случае состоит из 
таких этапов: 
− параметризация задачи, то есть выделение тех элементов, от которых 
зависит решение и в частности размерность задачи; размерность должна 
убывать при каждом рекурсивном вызове; 
− поиск тривиального случая, который может быть разрешен без рекур-
сивного вызова,  и его решение.
Последний этап является ключевым при построении рекурсивного ал-
горитма и ему обычно соответствует размерность задачи, равная нулю или 
единице. 
Далее приведены два примера рекурсивных программ – «Ханойские 
башни» и сортировка массива.
3.3.1. З
АДАЧА О 
Х
АНОЙСКИХ БАШНЯХ
 
Легенда о Ханойских башнях была придумана математиком Эдуардом 
Люка в начале XIX века. Она представляла собой увлекательную формули-
ровку математической задачи, и вызвала такой большой интерес, что множе-
ство людей старались найти ее решение. А задача и связанная с нею легенда 
такова. 
У служителей одного из монастырей, расположенного в труднодоступ-
ных горах, есть три алмазных стержня. На одном из стержней лежат 64 золо-
тых кольца, различных по размеру и расположенных пирамидой: снизу само-
го большого диаметра, потом меньшего и, наконец, наверху пирамиды — 
самый маленький. Эти кольца нужно переложить на другой стержень, полу-
чив точно такую же пирамиду. Третий стержень используется как промежу-
точный. Условия перемещения колец следующие: 
− за один раз можно перемещать только одно кольцо; 
− кольцо можно брать только с вершины одной из пирамид, а 
класть либо на пустой стержень, либо на кольцо большего диа-
метра. 
5 / 23

---

52 
Когда монахи перенесут все 64 кольца, наступит конец света. На ри-
сунке 3.2 изображены три стержня, на одном из которых находится пирамида 
из 4-х колец. 
Рис. 3.2. Ханойские башни (начальное положение) 
Поставим задачу вывода на экран последовательности перемещений 
колец. Данная задача имеет очевидное рекурсивное решение. 
Напомним, что рекурсивное решение любой задачи состоит из этапов 
параметризации и поиска тривиального случая. Здесь естественным парамет-
ром является K – число колец. Кроме того, в число параметров нужно вклю-
чить: номер стержня, с которого надо снять пирамиду колец, номер промежу-
точного стержня и номер стержня, на который пирамиду надо перенести. 
Тривиальным будет случай, соответствующий K = 0, не требующий выпол-
нения каких-либо действий.
K колец могут быть перемещены со стержня 1 на стержень 2 путем: 
− рекурсивного переноса K–1 колец со стержня 1 на стержень 3 с 
учетом правил игры. Стержень 2 используется как промежуточ-
ный; 
− перемещения на стержень 2 со стержня 1 последнего — наиболь-
шего — кольца (рис. 3.3); 
− рекурсивного переноса K–1 колец со стержня 3 на стержень 2. Но 
теперь как промежуточный будет использоваться стержень 1. 
Рис. 3.3. Ханойские башни (промежуточное положение) 
С учетом сказанного структура функции Hanoj() будет выглядеть 
так, как это представлено в листинге 3.4.