Несколько примеров рекурсивных процедур, рассмотренных в этом пункте, помогут лучшему усвоению техники применения рекурсии. Мы также увидим преимущества и недостатки рекурсивных описаний.
Пример 7. Ханойские башни.
Классический пример применения рекурсии для описания эффективного алгоритма - задача о ханойских башнях.
Анализ и неформальное описание алгоритма.Пусть N - количество колец на стержне, I - номер кольца, с которого осуществляется перестановка и J - номер кольца, на которое кольца требуется переставить.
HanojTower( N, I, J) - процедура, переставляющая N колец с I-того стержня на J-тый.
Step(I, J) - процедура, переставляющая одно кольцо с I-того стержня на J-тый.
(Если I и J - номера 2-стержней, то 6-I-J - номер третьего стержня.)
Предположим, что мы переместили N-1 кольцо с I-того стержня на 6-I-J стержень. Тогда можно переместить кольцо со стержня I на J.
На стержне J лежит кольцо с наибольшим диаметром, т.е. этот стержень можно использовать без нарушения ограничений, связанных с величинами диаметров. Поэтому можно теперь переставить всю пирамиду из N-1 кольца со стержня 6-I-J на J, и задача решена!
При N = 1 задача решается за один шаг - процедурой Step(I, J). Тем самым установлен базис рекурсии. Опишем теперь процедуру HanojTower(N, I, J):
Procedure HanojTower(N, I, J: Integer);
