Рекурсивное построение кривых Серпинского
Как и кривые Гильберта, кривые Серпинского (Sierpinski curves) — это самоподобные кривые, которые обычно определяются рекурсивно. На рис. 5.5 показаны кривые Серпинского 1, 2 и 3 порядка.
Алгоритм построения кривых Гильберта использует всего одну подпрограмму для рисования кривых. Кривые Серпинского проще рисовать, используя четыре отдельных процедуры, которые работают совместно. Эти процедуры называются SierpA, SierpB, SierpC и SierpD. Это процедуры с косвенной рекурсией — каждая процедура вызывает другие, которые затем вызывают первоначальную процедуру. Они рисуют верхнюю, левую, нижнюю и правую части кривой Серпинского, соответственно.
На рис. 5.6 показано, как эти процедуры работают совместно, образуя кривую Серпинского 1 порядка. Подкривые изображены стрелками, чтобы показать направление, в котором они рисуются. Отрезки, соединяющие четыре подкривые, нарисованы пунктирными линиями.
@Рис. 5.4. Программа Hilbert
=====92
@Рис. 5.5. Кривые Серпинского
Каждая из четырех основных кривых состоит из диагонального отрезка, затем вертикального или горизонтального отрезка, и еще одного диагонального отрезка. Если глубина рекурсии больше единицы, каждая из этих кривых разбивается на меньшие части. Это осуществляется разбиением каждого из двух диагональных отрезков на две подкривые.
Например, для разбиения кривой типа A, первый диагональный отрезок разбивается на кривую типа A, за которой следует кривая типа B. Затем рисуется без изменений горизонтальный отрезок из исходной кривой типа A. Наконец, второй диагональный отрезок разбивается на кривую типа D, за которой следует кривая типа A. На рис. 5.7 показано, как кривая типа A второго порядка образуется из нескольких кривых 1 порядка. Подкривые изображены жирными линиями.
На рис. 5.8 показано, как полная кривая Серпинского 2 порядка образуется из 4 подкривых 1 порядка. Каждая из подкривых обведена контурной линией.
Можно использовать стрелки - и - для обозначения типа линий, соединяющих подкривые (тонкие линии на рис. 5.8), тогда можно будет изобразить рекурсивные отношения между четырьмя типами кривых так, как это показано на рис. 5.9.
@Рис. 5.6. Части кривой Серпинского
=====93
@Рис. 5.7. Разбиение кривой типа A
Все процедуры для построения подкривых Серпинского очень похожи, поэтому мы приводим здесь только одну из них. Соотношения на рис. 5.9 показывают, какие операции нужно выполнить для рисования кривых различных типов. Соотношения для кривой типа A реализованы в следующем коде. Вы можете использовать остальные соотношения, чтобы определить, какие изменения нужно внести в код для рисования кривых других типов.
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
@Рис. 5.8. Кривые Серпинского, образованные из меньших кривых Серпинского
=====94
@Рис. 5.9. Рекурсивные соотношения между кривыми Серпинского
Кроме процедур, которые рисуют каждую из основных кривых, потребуется еще процедура, которая по очереди вызывает их все для создания законченной кривой Серпинского.
Sub Sierpinski (Depth As Integer, Dist As Single)
SierpB Depth, Dist
Line -Step(Dist, Dist)
SierpC Depth, Dist
Line -Step(Dist, -Dist)
SierpD Depth, Dist
Line -Step(-Dist, -Dist)
SierpA Depth, Dist
Line -Step(-Dist, Dist)
End Sub
Чтобы проанализировать время выполнения этого алгоритма, необходимо определить число вызовов для каждой из четырех процедур рисования кривых. Пусть T(N) — число вызовов любой из четырех основных подпрограмм основной процедуры Sierpinski при построении кривой порядка N.
Если порядок кривой равен 1, кривая каждого типа рисуется только один раз. Прибавив сюда основную процедуру, получим T(1) = 5.
При каждом рекурсивном вызове, процедура вызывает саму себя или другие процедуры четыре раза. Так как эти процедуры практически одинаковые, то T(N) будет одинаковым, независимо от того, какая процедура вызывается первой. Это обусловлено тем, что кривые Серпинского симметричны и содержат одно и то же число кривых разных типов. Рекурсивные уравнения для T(N) выглядят так:
T(1) = 5
T(N) = 1 + 4 * T(N-1) для N > 1.
Эти уравнения почти совпадают с уравнениями, которые использовались для оценки времени выполнения алгоритма, рисующего кривые Гильберта. Единственное отличие состоит в том, что для кривых Гильберта T(1) = 1. Сравнение значений этих уравнений показывает, что TSierpinski(N) = THilbert(N+1). В конце предыдущего раздела было показано, что THilbert(N) = (4N - 1) / 3, поэтому TSierpinski(N) = (4N+1 - 1) / 3, что также составляет O(4N).
=====95
Так же, как и алгоритм построения кривых Гильберта, этот алгоритм выполняется за время порядка O(4N), но это не так уж и плохо. Кривая Серпинского состоит из O(4N) линий, поэтому ни один алгоритм не может нарисовать кривую Серпинского быстрее, чем за время порядка O(4N).
Кривые Серпинского также полностью заполняют экран большинства компьютеров при порядке кривой, большем или равном 9. При каком‑то порядке, большем 9, вы столкнетесь с ограничениями языка Visual Basic и возможностей вашего компьютера, но, скорее всего, вы еще раньше будете ограничены предельным разрешением экрана.
Программа Sierp, показанная на рис. 5.10, использует этот рекурсивный алгоритм для рисования кривых Серпинского. При выполнении программы, задавайте вначале небольшую глубину рекурсии (меньше 6), до тех пор, пока вы не определите, насколько быстро выполняется эта программа на вашем компьютере.
Рекурсия может служить мощным методом разбиения больших задач на части, но она таит в себе несколько опасностей. В этом разделе мы пытаемся охватить некоторые из этих опасностей и объяснить, когда стоит и не стоит использовать рекурсию. В последующих разделах приводятся методы устранения от рекурсии, когда это необходимо.
Наиболее очевидная опасность рекурсии заключается в бесконечной рекурсии. Если неправильно построить алгоритм, то функция может пропустить условие остановки рекурсии и выполняться бесконечно. Проще всего совершить эту ошибку, если просто забыть о проверке условия остановки, как это сделано в следующей ошибочной версии функции факториала. Поскольку функция не проверяет, достигнуто ли условие остановки рекурсии, она будет бесконечно вызывать сама себя.
@Рис. 5.10 Программа Sierp
=====96
Private Function BadFactorial(num As Integer) As Integer
BadFactorial = num * BadFactorial (num - 1)
End Function
Функция также может вызывать себя бесконечно, если условие остановки не прекращает все возможные пути рекурсии. В следующей ошибочной версии функции факториала, функция будет бесконечно вызывать себя, если входное значение — не целое число, или если оно меньше 0. Эти значения не являются допустимыми входными значениями для функции факториала, поэтому в программе, которая использует эту функцию, может потребоваться проверка входных значений. Тем не менее, будет лучше, если функция выполнит эту проверку сама.
Private Function BadFactorial2(num As Double) As Double
If num = 0 Then
BadFactorial2 = 1
Else
BadFactorial2 = num * BadFactorial2(num-1)
End If
End Function
Следующая версия функции Fibonacci является более сложным примером. В ней условие остановки рекурсии прекращает выполнение только нескольких путей рекурсии, и возникают те же проблемы, что и при выполнении функции BadFactorial2, если входные значения отрицательные или не целые.
Private Function BadFib(num As Double) As Double
If num = 0 Then
BadFib = 0
Else
BadFib = BadPib(num - 1) + BadFib (num - 2)
End If
End Function
И последняя проблема, связанная с бесконечной рекурсией, заключается в том, что «бесконечная» на самом деле означает «до тех пор, пока не будет исчерпано стековое пространство». Даже корректно написанные рекурсивные процедуры будут иногда приводить к переполнению стека и аварийному завершению работы. Следующая функция, которая вычисляет сумму N + (N - 1) + … + 2 +1, приводит к исчерпанию стекового пространства при больших значениях N. Наибольшее возможное значение N, при котором программа еще будет работать, зависит от конфигурации вашего компьютера.
Private Function BigAdd(N As Double) As Double
If N <= 1 Then
BigAdd = 1
Else
BigAdd = N + BigAdd(N - 1)
End If
End Function
=====97
Программа BigAdd демонстрирует этот алгоритм. Проверьте, насколько большое входное значение вы можете ввести в этой программе до того, как наступит переполнение стека на вашем компьютере.
Другая опасность рекурсии заключается в потерях памяти. При каждом вызове подпрограммы, система выделяет память для локальных переменных новой процедуры. Во время сложной последовательности рекурсивных вызовов, значительная часть времени и памяти компьютера будет уходить на выделение и освобождение памяти для этих переменных во время рекурсии. Даже если это не приведет к исчерпанию стекового пространства, время, потраченное на работу с переменными, может быть значительным.
Существует несколько способов уменьшения этих накладных расходов. Во‑первых, не следует использовать большого количества ненужных переменных. Даже если подпрограмма не использует их, Visual Basic все равно будет отводить память под эти переменные. Следующая версия функции BigAdd еще быстрее приводит к переполнению стека, чем предыдущая.
Private Function BigAdd(N As Double) As Double
Dim I1 As Integer
Dim I2 As Integer
Dim I3 As Integer
Dim I4 As Integer
Dim I5 As Integer
If N <= 1 Then
BigAdd = 1
Else
BigAdd = N + BigAdd (N - 1)
End If
End Function
Если вы не уверены, нужна ли переменная, используйте оператор Option Explicit и закомментируйте определение переменной. При попытке выполнить программу, Visual Basic сообщит об ошибке, если переменная используется в программе.