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

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

Рекурсивная версия этого алгоритма состоит из четырех подпрограмм 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