Нерекурсивное построение кривых Гильберта

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

 

=======107-108

 

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

В качестве более интересного примера, рассмотрим нерекурсивный алгоритм построения кривых Гильберта.

 

Private Sub Hilbert(depth As Integer, Dx As Single, Dy As Single)

If depth > 1 Then Hilbert depth - 1, Dy, Dx

HilbertPicture.Line -Step(Dx, Dy)

If depth > 1 Then Hilbert depth - 1, Dx, Dy

HilbertPicture.Line -Step(Dy, Dx)

If depth > 1 Then Hilbert depth - 1, Dx, Dy

HilbertPicture.Line -Step(-Dx, -Dy)

If depth > 1 Then Hilbert depth - 1, -Dy, -Dx

End Sub

 

В следующем фрагменте кода первые строки каждого блока кода между рекурсивными шагами пронумерованы. Эти блоки включают первую строку процедуры и любые другие точки, в которых может понадобиться продолжить выполнение после возврата после «рекурсии».

 

Private Sub Hilbert(depth As Integer, Dx As Single, Dy As Single)

1 If depth > 1 Then Hilbert depth - 1, Dy, Dx

2 HilbertPicture.Line -Step(Dx, Dy)

If depth > 1 Then Hilbert depth - 1, Dx, Dy

3 HilbertPicture.Line -Step(Dy, Dx)

If depth > 1 Then Hilbert depth - 1, Dx, Dy

4 HilbertPicture.Line -Step(-Dx, -Dy)

If depth > 1 Then Hilbert depth - 1, -Dy, -Dx

End Sub

 

Каждый раз, когда нерекурсивная процедура начинает «рекурсию», она должна сохранять значения локальных переменных Depth, Dx, и Dy, а также следующее значение переменной pc. После возврата из «рекурсии», она восстанавливает эти значения. Для упрощения работы, можно написать пару вспомогательных процедур для заталкивания и выталкивания этих значений из нескольких стеков.

 

====109

 

Const STACK_SIZE =20

Dim DepthStack(0 To STACK_SIZE)

Dim DxStack(0 To STACK_SIZE)

Dim DyStack(0 To STACK_SIZE)

Dim PCStack(0 To STACK_SIZE)

Dim TopOfStack As Integer

 

Private Sub SaveValues (Depth As Integer, Dx As Single, _

   Dy As Single, pc As Integer)

TopOfStack = TopOfStack + 1

DepthStack(TopOfStack) = Depth

DxStack(TopOfStack) = Dx

DyStack(TopOfStack) = Dy

PCStack(TopOfStack) = pc

End Sub

 

Private Sub RestoreValues (Depth As Integer, Dx As Single, _

   Dy As Single, pc As Integer)

Depth = DepthStack(TopOfStack)

Dx = DxStack(TopOfStack)

Dy = DyStack(TopOfStack)

pc = PCStack(TopOfStack)

TopOfStack = TopOfStack - 1

 

End Sub

 

Следующий код демонстрирует нерекурсивную версию подпрограммы Hilbert.

 

Private Sub Hilbert(Depth As Integer, Dx As Single, Dy As Single)

Dim pc As Integer

Dim tmp As Single

 

pc = 1

Do

   Select Case pc

      Case 1

          If Depth > 1 Then   ' Рекурсия.

              ' Сохранить текущие значения.

              SaveValues Depth, Dx, Dy, 2

              ' Подготовиться к рекурсии.

              Depth = Depth - 1

              tmp = Dx

              Dx = Dy

              Dy = tmp

              pc = 1 ' Перейти в начало рекурсивного вызова.

          Else   ' Условие остановки.

              ' Достаточно глубокий уровень рекурсии.

              ' Продолжить со 2 блоком кода.

              pc = 2

          End If

      Case 2

          HilbertPicture.Line -Step(Dx, Dy)

          If Depth > 1 Then   ' Рекурсия.

              ' Сохранить текущие значения.

              SaveValues Depth, Dx, Dy, 3

              ' Подготовиться к рекурсии.

              Depth = Depth - 1

              ' Dx и Dy остаются без изменений.

              pc = 1 Перейти в начало рекурсивного вызова.

          Else   ' Условие остановки.

              ' Достаточно глубокий уровень рекурсии.

              ' Продолжить с 3 блоком кода.

              pc = 3

          End If

      Case 3

          HilbertPicture.Line -Step(Dy, Dx)

          If Depth > 1 Then   ' Рекурсия.

              ' Сохранить текущие значения.

              SaveValues Depth, Dx, Dy, 4

              ' Подготовиться к рекурсии.

              Depth = Depth - 1

              ' Dx и Dy остаются без изменений.

              pc = 1 Перейти в начало рекурсивного вызова.

          Else   ' Условие остановки.

              ' Достаточно глубокий уровень рекурсии.

              ' Продолжить с 4 блоком кода.

              pc = 4

          End If

      Case 4

          HilbertPicture.Line -Step(-Dx, -Dy)

          If Depth > 1 Then   ' Рекурсия.

              ' Сохранить текущие значения.

              SaveValues Depth, Dx, Dy, 0

              ' Подготовиться к рекурсии.

              Depth = Depth - 1

              tmp = Dx

              Dx = -Dy

              Dy = -tmp

              pc = 1 Перейти в начало рекурсивного вызова.

          Else   ' Условие остановки.

              ' Достаточно глубокий уровень рекурсии.

              ' Конец этого рекурсивного вызова.

              pc = 0

          End If

      Case 0 ' Возврат из рекурсии.

          If TopOfStack > 0 Then

              RestoreValues Depth, Dx, Dy, pc

          Else

              ' Стек пуст. Выход.

              Exit Do

          End If

   End Select

Loop

End Sub

 

 

======111

 

Время выполнения этого алгоритма может быть нелегко оценить непосредственно. Поскольку методы преобразования рекурсивных процедур в нерекурсивные не изменяют время выполнения алгоритма, эта процедура так же, как и предыдущая версия, имеет время выполнения порядка O(N⁴).

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