Техника рекурсивных описаний

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);

Дата добавления: 2014-01-06