Техника рекурсивных описаний
End
End;
Тело функции F содержит два рекурсивных вызова, выполняемых последовательно. Поэтому полная картинка рекурсии имеет вид дерева! Построим ее при n = 5.
 |
Каждая рекурсивная копия, если ее параметр k >= 2, вызывает две новых копии. Полная картинки вызовов имеет вид дерева, из каждого ветвления которого выходят две ветви. (с параметрами k-1, k-2).
В каждый момент времени в памяти компьютера хранится только один путь - тот, который соответствует состоянию процесса вычислений.
В памяти компьютера, отведенной под рекурсивные вычисления, хранятся те копии, путь через которые лежит к исполняемой.
Время исполнения этого алгоритма пропорционально общему числу рекурсивных копий,
Максимальная память, требуемая для хранения данных, пропорциональна длине максимального пути - от первой копии до копии нижнего уровня.
Древовидная картинка наглядно показывает схему рекурсивных вычислений. На ней видно, что необходимыми являются только вычисления, стоящие в самом левом пути. Все остальные вычисления - только повторения уже проделанных.
Несколько примеров рекурсивных процедур, рассмотренных в этом пункте, помогут лучшему усвоению техники применения рекурсии. Мы также увидим преимущества и недостатки рекурсивных описаний.
Пример 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);