Стр. 18 - Основы алгоритмов и структур данных

16 Содержание
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
Каждое поколение HANOY содержит два рекурсивных вызова. При каждом
вызове выполнение текущего поколения прекращается и она впадает в
“зимнюю спячку”. Как только последующее поколение закончит свою работу,
вызвавшее поколение пробуждается и продолжает свою работу с прерванного
места. Для программы HANOY необходимой информацией является n, x, y, z
(имена оснований) и номер осуществлённого вызова. Очевидно, задача
управления рекурсией заключается в том, чтобы сохранить при каждом
рекурсивном вызове всю необходимую информацию для поколения,
инициировавшего этот вызов. Эта информация должна храниться до тех пор,
пока не закончат свою работу все последующие поколения, при этом
необходимо правильно отыскать сохранённую информацию.
1 X Z Y 1
2 X Y Z 1
3 X Z Y 1
4 X Y Z 1
1 Z Y X
2 X Y Z 2
3 X Z Y 1
4 X Y Z 1
1 Y X Z
2 Y Z X 1
3 X Z Y 2
4 X Y Z 1
и т.д.
закончил
закончил
номер вызова
Рис. 9. Стек игры Ханойская башня
Можно сказать, что информация должна восстанавливаться в порядке,
обратном тому, в котором она запоминалась. Такое поведение информации
реализуется в стеке. Проследим, как заносится и реализуется эта информация:
(n=4).
Когда стек окажется пуст, выполнение завершается.
Важные наблюдения:
1. Очевидно, схема выполнения рекурсивной программы – это всегда
дерево с кратностью ветвления, равной числу рекурсивных вызовов из одного
поколения. Иными словами, рекурсивная программа интерпретирует
обрабатываемые данные как организованные древовидно (иерархически). И,
наоборот, если данные уже организованы древовидно, то простейший и лучший
способ их обработать – это рекурсия.
Рекурсия  дерево (как вид алгоритма).