Использование рекурсии в компьютерной графике

Использование фракталов при  изучении темы «рекурсия»

О.Ю. Тяжельникова, Д.М.Гребнева

ГОУ ВПО  «Нижнетагильская социально-педагогическая академия» 
г. Нижний Тагил 

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

      Понятия фрактал, фрактальная геометрия  и фрактальная графика, появились  в конце 70-х. Слово фрактал образовано от латинского fractus и в переводе означает «состоящий из фрагментов». Оно было предложено математиком Бенуа Мандельбротом  в 1975 году для обозначения нерегулярных, но самоподобных структур. Рождение фрактальной  геометрии принято связывать  с выходом в 1977 году книги Мандельброта «The Fractal Geometry of Nature». В его работах использованы научные результаты других ученых, работавших в 1875 – 1925 годах в той же области (Пуанкаре, Фату, Жюлиа, Кантор, Хаусдорф). Но только в наше время удалось объединить их работы в единую систему. Определение фрактала, данное Мандельбротом: фракталом называется структура, состоящая из частей, которые в каком-то смысле подобны целому. Самоподобие – одно из основных свойств фракталов. Объект называют  самоподобным, когда увеличенные части объекта походят на сам объект и друг на друга.

      Различают геометрические и алгебраические фракталы. Геометрические фракталы самые наглядные. В двухмерном случае их получают с  помощью некоторой ломаной (или  поверхности в трехмерном случае), называемой генератором. За один шаг алгоритма каждый из отрезков, составляющих ломаную, заменяется на ломаную-генератор, в соответствующем масштабе. В результате многократного повторения этой процедуры, получается геометрический фрактал. Примерами геометрических фракталов могут служит кривые Гильберта (рисунок 1), кривые Серпинского (рисунок 2),  треугольник Серпинского (рисунок 3).

        
 

Рисунок 2. Кривые Серпинского

      Для построения геометрических фрактальных  кривых используются рекурсивные алгоритмы.  Рекурсия используется при решении  задач, которые могут быть разложены  на несколько подзадач. Таким образом, применение рекурсии целесообразно  при построении фрактальных кривых, так как они обладают таким  свойством как самоподобие. Алгоритмы  построения фрактальных кривых рекурсивны по своей природе, и их гораздо  проще изучать в рекурсивном  представлении. Ниже приведен пример листинга программы рисования треугольника Серпинского в среде Visual Basic. 

Public xa As Integer, ya As Integer, xb As Integer, yb As Integer, xc As Integer, yc As Integer, n As Integer // объявление глобальных переменных

Private Sub triangle(xa As Integer, ya As Integer, xb As Integer, yb As Integer, xc As Integer, yc As Integer, n As Integer) //описываем процедуру

Dim xp As Integer, xq As Integer, xr As Integer, yp As Integer, yq As Integer, yr As Integer

// объявление  локальных переменных

If n > 0 Then

xp = Int((xb + xc) / 2) //Нахождение координат средних линий треугольника

yp = Int((yb + yc) / 2)

xq = Int((xa + xc) / 2)

yq = Int((ya + yc) / 2)

xr = Int((xb + xa) / 2)

yr = Int((yb + ya) / 2)

Line (xp, yp)-(xq, yq), RGB(90, 10, 500)

Line (xq, yq)-(xr, yr), RGB(190, 10, 100)

Line (xp, yp)-(xr, yr), RGB(190, 190, 300)

Call triangle(xc, yc, xq, yq, xp, yp, n - 1)

Call triangle(xa, ya, xr, yr, xq, yq, n - 1)

Call triangle(xb, yb, xp, yp, xr, yr, n - 1)

End If  End Sub

Private Sub Command1_Click()

treug.Scale (-50, -50)-(800, 600) // Задаем масштаб

treug.Cls //предварительно очищаем форму от предыдущего рисунка

n = Val(Text1.Text)

Line (xa, ya)-(xb, yb), RGB(90, 190, 300)

Line (xb, yb)-(xc, yc), RGB(90, 190, 300)

Line (xa, ya)-(xc, yc), RGB(90, 190, 300)

Call triangle(xa, ya, xb, yb, xc, yc, n)

End Sub

Private Sub Form_Load()

n = Val(Text1.Text)

xc = 300

yc = 0

xb = 600

yb = 400

xa = 0 ya = 400

End Sub