Private Sub Factorial(num As Integer, value As Integer)
ReDim num_stack(1 to 200) As Integer
ReDim pc_stack(1 to 200) As Integer
Dim stack_top As Integer ' Вершина стека.
Dim pc As Integer
pc = 1
Do
Select Case pc
Case 1
If num <= 1 Then ' Это условие остановки. value = 1
pc = 0 ' Конец рекурсии.
Else ' Рекурсия.
' Сохранить num и следующее значение pc.
stack_top = stack_top + 1
num_stack(stack_top) = num
pc_stack(stack_top) = 2 ' Возобновить с 2.
' Начать рекурсию.
num = num - 1
' Перенести блок управления в начало.
pc = 1
End If
Case 2
' value содержит результат последней
' рекурсии. Умножить его на num.
value = value * num
' "Возврат" из "рекурсии".
pc = 0
Case 0
' Конец "рекурсии".
' Если стеки пусты, исходный вызов
' подпрограммы завершен.
If stack_top <= 0 Then Exit Do
' Иначе восстановить локальные переменные и pc.
num = num_stack(stack_top)
pc = pc_stack(stack_top)
stack_top = stacK_top - 1
End Select
Loop
End Sub
Так же, как и устранение хвостовой рекурсии, этот метод имитирует поведение рекурсивного алгоритма. Процедура заменяет каждый рекурсивный вызов итерацией цикла While. Поскольку число шагов остается тем же самым, полное время выполнения алгоритма не изменяется.
Так же, как и в случае с устранением хвостовой рекурсии, этот метод устраняет глубокую рекурсию, которая может переполнить стек.
Нерекурсивное построение кривых Гильберта
Пример вычисления факториала из предыдущего раздела превратил простую, но неэффективную рекурсивную функцию вычисления факториала в сложную и неэффективную нерекурсивную процедуру. Намного лучший нерекурсивный алгоритм вычисления факториала, был представлен ранее в этой главе.
=======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(N4).
Программа Hilbert2 демонстрирует нерекурсивный алгоритм построения кривых Гильберта. Задавайте вначале построение несложных кривых (меньше 6 порядка), пока не узнаете, насколько быстро будет выполняться эта программа на вашем компьютере.
Нерекурсивное построение кривых Серпинского
Приведенный ранее алгоритм построения кривых Серпинского включает в себя косвенную и множественную рекурсию. Так как алгоритм состоит из четырех подпрограмм, которые вызывают друг друга, то нельзя просто пронумеровать важные строки, как это можно было сделать в случае алгоритма построения кривых Гильберта. С этой проблемой можно справиться, слегка изменив алгоритм.
Рекурсивная версия этого алгоритма состоит из четырех подпрограмм 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(N4), поэтому порядок времени выполнения новой версии также составляет O(N4). Она выполняется немного медленнее, чем рекурсивная версия, и является намного более сложной.