Эффективность рекурсивных вычислений

 

Так как для хранения фреймов активации рекурсивной процедуры используется автоматическая память, при обработке данных нерекурсивной природы следует использовать итеративные алгоритмы, не требующие дополнительного расхода памяти, если только рекурсивные алгоритмы не оказываются более ясными и понятными. Примером алгоритма, обрабатывающего данные нерекурсивной природы, но имеющего гораздо более эффективную рекурсивную реализацию по сравнению с итеративной, яаляется алгоритм решения задачи о “ханойских башнях”. При вычислении же значения факториала натурального числа N несомненно следует предпочесть итеративную процедуру.

Если процедура содержит единственный рекурсивный вызов и он является последним действием процедуры, то говорят, что имеет место задняя рекурсия (tail recursion) (см. процедуру Print_Front). Этот рекурсивный вызов требует затрат на создание фреймов активации и запоминание их в стеке. Когда рекурсивный вычислительный процесс доходит до условия завершения, выполняется серия возвратов, выталкивающих фреймы активации из стека. Если при наличии задней рекурсии фреймы активации не используются для окончательных вычислений, следует предпочесть итеративную реализацию (см. процедуру Print из программного модуля!!!). Рекурсивная процедура Print_Back, не содержащая задней рекурсии, имеет более эффективную реализацию, чем итеративная процедура, выполняющая те же действия.

 

 

7. Иерархические Нелинейные структуры данных. деревья

Деревья общего вида

 

Нелинейные структуры данных выражают более сложные отношения порядка между объектами, чем отношения предшествования и следования. Наиболее важным видом нелинейных структур являются деревья. Древовидные структуры позволяют определить такие отношения, как предок, потомок, брат и т.п.

Дерево – конечное множество объектов Т, состоящее из одного или более узлов, для которых выполняются следующие условия:

¨ имеется один специально выделенный узел, называемый корнем данного дерева;

¨ остальные узлы (исключая корень) содержатся в m попарно непересекающихся множествах T1, …,Tm, каждое из которых в свою очередь является деревом. Деревья T1,...,Тm называются поддеревьями данного корня. Структура дерева общего вида представлена на рис. 63.

 

Рис. 63. Дерево общего вида

 

Число поддеревьев данного корня (узла) называется степенью этого узла. Максимальная степень всех узлов дерева называется степенью дерева, обозначим d. Узел с нулевой степенью называется терминальным узлом или листом. Уровень узла – выраженная в числе ребер длина пути, ведущего из узла в корень дерева плюс единица. Считается, что корень дерева находится на уровне 1. Если некоторый узел А располагается на уровне i, то находящийся непосредственно ниже его на уровне i+1 узел В называется непосредственным потомком узла А, а узел А называется непосредственным предком узла В. Максимальный уровень всех узлов дерева называется высотой или глубиной дерева, обозначим h. Высота пустого дерева равна нулю, высота дерева, состоящего из одного корня, равна 1. Дерево, содержащее максимальное число узлов, называется полным. Количество узлов в полном дереве степени d высотой h вычисляется по формуле (i – номер уровня)

 

Основные свойства деревьев общего вида:

¨ корень не имеет предков;

¨ каждый узел, за исключением корня, имеет только одного предка;

¨ каждый узел связан с корнем единственным путем, т.е. в деревьях отсутствуют замкнутые контуры (циклы).

Если в определении дерева имеет значение относительный порядок поддеревьев Т1,…,Тm, дерево является упорядоченным. Поэтому два упорядоченных дерева на рис. 64 – это разные, отличные друг от друга объекты.

 

Рис. 64. Два различных дерева

Бинарные деревья

Особенно важное практическое значение имеют упорядоченные деревья второй степени. Их называют двоичными или бинарными деревьями.

Бинарное дерево – это конечное множество узлов, которое или пусто, или состоит из корня и двух непересекающихся бинарных деревьев, называемых левым и правым поддеревьями данного корня. Примеры бинарных деревьев приведены на рис. 65.

 

Рис. 65. Примеры бинарных деревьев

 

Максимальное число узлов в бинарном дереве высотой h (d=2):

.

Максимальное число узлов на уровне i в бинарном дереве:

 .

Высота полного бинарного дерева, содержащего N узлов:

.

 ë û означает взятие целой части числа.

 

Существуют различные алгоритмы преобразования дерева произвольной степени, т.е. дерева общего вида, к виду бинарного. Левосторонний алгоритм формулируется следующим образом: у каждого узла дерева произвольной степени необходимо сохранить самую левую связь, а узлы – потомки одного и того же узла следует соединить правой связью. На рис. 66 представлено исходное дерево общего вида, а на рис. – эквивалентное бинарное.

 

 

Рис. 66. Преобразование произвольного дерева к виду бинарного