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

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

=======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 порядка), пока не узнаете, насколько быстро будет выполняться эта программа на вашем компьютере.