Нерекурсивное построение кривых Серпинского

Приведенный ранее алгоритм построения кривых Серпинского включает в себя косвенную и множественную рекурсию. Так как алгоритм состоит из четырех подпрограмм, которые вызывают друг друга, то нельзя просто пронумеровать важные строки, как это можно было сделать в случае алгоритма построения кривых Гильберта. С этой проблемой можно справиться, слегка изменив алгоритм.

Рекурсивная версия этого алгоритма состоит из четырех подпрограмм SierpA, SierpB, SierpC и SierpD. Подпрограмма SierpA выглядит так:

 

Private Sub SierpA(Depth As Integer, Dist As Single)

If Depth = 1 Then

   Line -Step(-Dist, Dist)

   Line -Step(-Dist, 0)

   Line -Step(-Dist, -Dist)

Else

   SierpA Depth - 1, Dist

   Line -Step(-Dist, Dist)

   SierpB Depth - 1, Dist

   Line -Step(-Dist, 0)

SierpD Depth - 1, Dist

   Line -Step(-Dist, -Dist)

   SierpA Depth - 1, Dist

End If

End Sub

 

Три другие процедуры аналогичны. Несложно объединить эти четыре процедуры в одну подпрограмму.

 

Private Sub SierpAll(Depth As Integer, Dist As Single, Func As Integer)

Select Case Punc

   Case 1 ' SierpA

      <код SierpA code>

   Case 2 ' SierpB

      <код SierpB>

   Case 3 ' SierpC

      <код SierpC>

   Case 4 ' SierpD

      <код SierpD>

End Select

End Sub

 

 

======112

 

Параметр Func сообщает подпрограмме, какой блок кода выполнять. Вызовы подпрограмм заменяются на вызовы процедуры SierpAll с соответствующим значением Func. Например, вызов подпрограммы SierpA заменяется на вызов процедуры SierpAll с параметром Func, равным 1. Таким же образом заменяются вызовы подпрограмм SierpB, SierpC и SierpD.

Полученная процедура рекурсивно вызывает себя в 16 различных точках. Эта процедура намного сложнее, чем процедура Hilbert, но в других отношениях она имеет такую же структуру и поэтому к ней можно применить те же методы устранения рекурсии.

Можно использовать первую цифру меток pc, для определения номера блока кода, который должен выполняться. Перенумеруем строки в коде SierpA числами 11, 12, 13 и т.д. Перенумеруем строки в коде SierpB числами 21, 22, 23 и т.д.

Теперь можно пронумеровать ключевые строки кода внутри каждого из блоков. Для кода подпрограммы SierpA ключевыми строками будут:

 

   ' Код SierpA.

11 If Depth = 1 Then

      Line -Step(-Dist, Dist)

      Line -Step(-Dist, 0)

      Line -Step(-Dist, -Dist)

   Else

      SierpA Depth - 1, Dist

12    Line -Step(-Dist, Dist)

      SierpB Depth - 1, Dist

13    Line -Step(-Dist, 0)

      SierpD Depth - 1, Dist

14    Line -Step(-Dist, -Dist)

      SierpA Depth - 1, Dist

   End If

 

Типичная «рекурсия» из кода подпрограммы SierpA в код подпрограммы SierpB выглядит так:

 

SaveValues Depth, 13 ' Продолжить с шага 13 после завершения.

Depth = Depth - 1

pc = 21           ' Передать управление на начало кода SierpB.

 

 

======113

 

Метка 0 зарезервирована для обозначения выхода из «рекурсии». Следующий код демонстрирует нерекурсивную версию процедуры SierpAll. Код для подпрограмм SierpB, SierpC, и SierpD аналогичен коду для SierpA, поэтому он опущен.

 

Private Sub SierpAll(Depth As Integer, pc As Integer)

Do

   Select Case pc

       ' **********

       ' * SierpA *

       ' **********

      Case 11

          If Depth <= 1 Then

              SierpPicture.Line -Step(-Dist, Dist)

              SierpPicture.Line -Step(-Dist, 0)

              SierpPicture.Line -Step(-Dist, -Dist)

              pc = 0

          Else

              SaveValues Depth, 12 ' Выполнить SierpA

              Depth = Depth - 1

              pc = 11

          End If

      Case 12

          SierpPicture.Line -Step(-Dist, Dist)

          SaveValues Depth, 13 ' Выполнить SierpB

          Depth = Depth - 1

          pc = 21

      Case 13

          SierpPicture.Line -Step(-Dist, 0)

          SaveValues Depth, 14 ' Выполнить SierpD

          Depth = Depth - 1

          pc = 41

      Case 14

          SierpPicture.Line -Step(-Dist, -Dist)

          SaveValues Depth, 0 ' Выполнить SierpA

          Depth = Depth - 1

          pc = 11

 

       ' Код для SierpB, SierpC и SierpD опущен.

              :

 

       ' *******************

       ' * Конец рекурсии. *

       ' *******************

      Case 0

          If TopOfStack <= 0 Then Exit Do

          RestoreValues Depth, pc

   End Select

Loop

End Sub

 

 

=====114

Так же, как и в случае с алгоритмом построения кривых Гильберта, преобразование алгоритма построения кривых Серпинского в нерекурсивную форму не изменяет время выполнения алгоритма. Новая версия алгоритма имитирует рекурсивный алгоритм, который выполняется за время порядка O(N⁴), поэтому порядок времени выполнения новой версии также составляет O(N⁴). Она выполняется немного медленнее, чем рекурсивная версия, и является намного более сложной.

Нерекурсивная версия также могла бы рисовать кривые более высоких порядков, но построение кривых Серпинского с порядком выше 8 или 9 непрактично. Все эти факты определяют преимущество рекурсивного алгоритма.

Программа Sierp2 использует этот нерекурсивный алгоритм для построения кривых Серпинского. Задавайте вначале построение несложных кривых (меньше 6 порядка), пока не определите, насколько быстро будет выполняться эта программа на вашем компьютере.

Резюме

При применении рекурсивных алгоритмов следует избегать трех основных опасностей:

· Бесконечной рекурсии. Убедитесь, что условия остановки вашего алгоритма прекращают все рекурсивные пути.

· Глубокой рекурсии. Если алгоритм достигает слишком большой глубины рекурсии, он может привести к переполнению стека. Минимизируйте использование стека за счет уменьшения числа определяемых в процедуре переменных, использования глобальных переменных, или определения переменных как статических. Если процедура все равно приводит к переполнению стека, перепишите алгоритм в нерекурсивном виде, используя устранение хвостовой рекурсии.

· Ненужной рекурсии. Обычно это происходит, если алгоритм типа рекурсивного вычисления чисел Фибоначчи, многократно вычисляет одни и те же промежуточные значения. Если вы столкнетесь с этой проблемой в своей программе, попробуйте переписать алгоритм, используя подход снизу вверх. Если алгоритм не позволяет прибегнуть к подходу снизу вверх, создайте таблицу промежуточных значений.

Применение рекурсии не всегда неправильно. Многие задачи являются рекурсивными по своей природе. В этих случаях рекурсивный алгоритм будет проще понять, отлаживать и поддерживать, чем его нерекурсивную версию. В качестве примера можно привести алгоритмы построения кривых Гильберта и Серпинского. Оба по своей природе рекурсивны и намного понятнее, чем их нерекурсивные модификации. При этом рекурсивные версии даже выполняются немного быстрее.

Если у вас есть алгоритм, который рекурсивен по своей природе, но вы не уверены, будет ли рекурсивная версия лишена проблем, запишите алгоритм в рекурсивном виде и выясните это. Может быть, проблемы не возникнут. Если же они возникнут, то, возможно, окажется проще преобразовать эту рекурсивную версию в нерекурсивную, чем написать нерекурсивную версию с нуля.

 

======115

 

Глава 6. Деревья

Во 2 главе приводились способы создания динамических связных структур, таких, как изображенные на рис 6.1. Такие структуры данных называются графами (graphs). В 12 главе алгоритмы работы с графами и сетями обсуждаются более подробно. В этой главе рассматриваются графы особого типа, которые называются деревьями (trees).

В начале этой главы приводится определение дерева и разъясняются некоторые термины. Затем в ней описываются некоторые методы реализации деревьев различных типов на языке Visual Basic. В последующих разделах рассматривается несколько алгоритмов обхода для деревьев, записанных в этих разных форматах. Глава заканчивается обсуждением некоторых специальных типов деревьев, включая упорядоченные деревья (sorted trees), деревья со ссылками[RV7] (threaded trees), боры[RV8] (tries) и квадродеревья[RV9] (quadtrees).

В 7 и 8 главе обсуждаются более сложные темы — сбалансированные деревья и деревья решений.

 

@Рис. 6.1. Графы

 

=====117

 

Определения

Можно рекурсивно определить дерево как:

* Пустую структуру или

* Узел, называемый корнем (node) дерева, связанный с нулем или более поддеревьев (subtrees).

На рис. 6.2 показано дерево. Корневой узел A связан с тремя поддеревьями, начинающимися в узлах B, C и D. Эти узлы связаны с поддеревьями с корнями E, F и G, и эти узлы, в свою очередь связаны с поддеревьями с корнями H, I и J.

Терминология деревьев представляет собой смесь терминов, позаимствованных из ботаники и генеалогии. Из ботаники пришли термины, такие как узел (node), определяемый как точка, в которой может начинаться ветвление, ветвь (branch), определяемая как связь между двумя узлами, и лист (leaf) — узел, из которого не выходят другие ветви.

Из генеалогии пришли термины, которые описывают родство. Если один узел находится непосредственно над другим, верхний узел называется родителем (parent), а нижний дочерним узлом (child). Узлы на пути вверх от узла до корня называются предками (ancestors) узла. Например, на рис. 6.2 узлы E, B и A — это все предки узла I.

Узлы, которые находятся ниже какого‑либо узла дерева, называются потомками (descendants) этого узла. Узлы E, H, I и J на рис. 6.2 — это все потомки узла B.

Иногда узлы, имеющие одного родителя, называются узлами‑братьями или узлами‑сестрами (sibling nodes).

Существует еще несколько терминов, которые не пришли из ботаники или генеалогии. Внутренним узлом (internal node) называется узел, который не является листом. Порядком узла (node degree) называется число его дочерних узлов. Порядок дерева — это наибольший порядок его узлов. Дерево на рис. 6.2 — третьего порядка, потому что узлы с наибольшим порядком, узлы A и E, имеют по 3 дочерних узла.

Глубина (depth) дерева равна числу его предков плюс 1. На рис. 6.2 глубина узла E равна 3. Глубиной (depth) или высотой (height) дерева называется наибольшая глубина его узлов. Глубина дерева на рис. 6.2 равна 4.

Дерево 2 порядка называется двоичным деревом (binary tree). Деревья третьего порядка иногда называются троичными[RV10] (ternary) деревьями. Более того, деревья порядка N иногда называются N‑ичными (N‑ary) деревьями.

 

@Рис. 6.2. Дерево

 

======118

 

Дерево порядка 12, например, называется 12‑ричным (12‑ary) деревом, а не додекадеричным (dodecadary) деревом. Некоторые избегают употребления лишних терминов и просто говорят «деревья 12 порядка».

Рис. 6.3 иллюстрирует некоторые из этих терминов.