Урок 4

Процедуры и функции, производящие вызов самих себя, называют рекурсивными. Рекурсия - является способом организации вычислительного процесса, при котором подпрограмма в ходе выполнения составляющих ее операторов обращается сама к себе.

При рекурсивном выполнении подпрограммы выделяется область памяти, называемая стек. Стек работает по принципу: "последний заходит, первый - выходит". Рекурсия может быть бесконечной. Но, как и любой другой алгоритм, она обязана выдавать результат своей работы за некое определенное количество операций. На каждом шаге выполнения рекурсивной подпрограммы обязательно присутствует условие завершения, когда оно выполняется, выполняется конечный шаг и последующий рекурсивный возврат. Глубиной рекурсии называется количество копий или количество обращений к рекурсии.

Пример 1: Вычисление факториала числа (n!)

Фракталы

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

Sub treug(ByVal x1 As Integer, ByVal y1 As Integer, ByVal x2 As Integer, ByVal y2 As Integer, ByVal x3 As Integer, ByVal y3 As Integer, ByVal n As Integer)

'P.Color = Color.FromArgb(Rnd() * 200 + 50, Rnd() * 50 + 50, Rnd() * 50 + 50)

GR.DrawLine(P, x1, y1, x2, y2) 'прорисовка тереугольника,

GR.DrawLine(P, x3, y3, x2, y2)

GR.DrawLine(P, x1, y1, x3, y3)

End Sub

Sub tr(ByVal x1 As Integer, ByVal y1 As Integer, ByVal x2 As Integer, ByVal y2 As Integer, ByVal x3 As Integer, ByVal y3 As Integer, ByVal n As Integer)

Dim x1p As Integer, y1p As Integer, x2p As Integer, y2p As Integer, x3p As Integer, y3p As Integer

Application.DoEvents()

If n > 0 Then

x1p = (x1 + x2) / 2 ' определение координат середин сторон

y1p = (y1 + y2) / 2

x2p = (x3 + x2) / 2

y2p = (y3 + y2) / 2

x3p = (x3 + x1) / 2

y3p = (y3 + y1) / 2

Call treug(x1p, y1p, x2p, y2p, x3p, y3p, n)

Call tr(x1, y1, x1p, y1p, x3p, y3p, n - 1)

Call tr(x2, y2, x1p, y1p, x2p, y2p, n - 1)

Call tr(x3, y3, x2p, y2p, x3p, y3p, n - 1)

End If

End Sub

Private Sub btn1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btn1.Click

GR = Me.CreateGraphics

P = New Pen(Color.Red, 2)

GR.Clear(Me.BackColor)

xa = 40 'координаты вершин треугольника

ya = Me.Height - 60

xb = Me.Width / 2

yb = 40

xc = Me.Width - 40

yc = Me.Height - 60

na = tb1.Text 'уровень вложенности треугольников

Call treug(xa, ya, xb, yb, xc, yc, na)

Call tr(xa, ya, xb, yb, xc, yc, na)

End Sub

Private Sub Form1_DoubleClick(ByVal sender As Object, ByVal e As System.EventArgs) Handles Me.DoubleClick

End

End Sub

End Class

Рис. 4.5. Результат работы программы «Снежинка Коха»

Программа «Снежинка Коха»

Public Class Form1

'Снежинка Коха

Dim GR As Graphics, P As Pen

Private Sub Koch(ByRef X As Double, ByRef Y As Double, ByRef L As Double, ByRef N As Single, ByRef A As Double)

Dim XK, YK As Double, T1 As PointF, T2 As PointF

If N = 0 Then

XK = X + L * Math.Cos(A * Math.PI / 180)

YK = Y + L * Math.Sin(A * Math.PI / 180)

T1.X = X

T1.Y = Y

T2.X = XK

T2.Y = YK

GR.DrawLine(P, T1, T2)

X = XK

Y = YK

Else

Call Koch(X, Y, L / 3, N - 1, A)

A = A - 60

Call Koch(X, Y, L / 3, N - 1, A)

A = A + 120

Call Koch(X, Y, L / 3, N - 1, A)

A = A - 60

Call Koch(X, Y, L / 3, N - 1, A)

End If

End Sub

Private Sub Btn1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Btn1.Click

Dim X, Y, L, N, A, I As Double

GR = Me.CreateGraphics

GR.Clear(Me.BackColor)

P = New Pen(Color.Blue, 2)

N = Tb1.Text

A = 0

L = 350

X = 200

Y = Me.Height / 4

For I = 1 To 3

Call Koch(X, Y, L, N, A)

A = A + 120

Next I

End Sub

Private Sub Form1_DoubleClick(ByVal sender As Object, ByVal e As System.EventArgs) Handles Me.DoubleClick

End

End Sub

End Class

Пример 4: Построим фигуру: “Ковёр Серпинского” . Фигура строится по правилу: закрашенный прямоугольник делится двумя горизонтальными и двумя вертикальными линиями на 9 частей и выбрасывается центральная часть. Затем то же повторяется для оставшихся 8 частей, и т. д. Последовательность построения фигуры показана на рис. 4.6.

Sub Serp(ByVal x1 As Integer, ByVal y1 As Integer, ByVal x2 As Integer, ByVal y2 As Integer, ByVal n As Integer)

Dim x1p As Integer, y1p As Integer, x2p As Integer, y2p As Integer

Application.DoEvents()

If n > 0 Then

x1p = 2 * x1 / 3 + x2 / 3 ' определение координат разделительных линий

y1p = 2 * y1 / 3 + y2 / 3

x2p = x1 / 3 + 2 * x2 / 3

y2p = y1 / 3 + 2 * y2 / 3

` убрать комментарий для кисти, что бы получить пёстрый ковёр

`B = New SolidBrush(Color.FromArgb(Rnd() * 255, Rnd() * 255, Rnd() * 255))

GR.FillRectangle(B, x1p, y1p, Math.Abs(x1p - x2p), Math.Abs(y1p - y2p))

Call Serp(x1, y1, x1p, y1p, n - 1)

Call Serp(x1p, y1, x2p, y1p, n - 1)

Call Serp(x2p, y1, x2, y1p, n - 1)

Call Serp(x1, y1p, x1p, y2p, n - 1)

Call Serp(x2p, y1p, x2, y2p, n - 1)

Call Serp(x1, y2p, x1p, y2, n - 1)

Call Serp(x1p, y2p, x2p, y2, n - 1)

Call Serp(x2p, y2p, x2, y2, n - 1)

End If

End Sub

Private Sub btn1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btn1.Click

GR = Me.CreateGraphics

P = New Pen(Color.Red, 2)

B = New SolidBrush(Color.Red)

GR.Clear(Me.BackColor)

xa = 170 'координаты вершин прямоугольника

ya = 60

xb = Me.Width - 40

yb = Me.Height - 60

na = tb1.Text 'уровень вложенности прямоугольника

GR.FillRectangle(B, xa, ya, Math.Abs(xb - xa), Math.Abs(yb - ya))

'GR.DrawRectangle(P, xa, ya, Math.Abs(xb - xa), Math.Abs(yb - ya))

B = New SolidBrush(Color.White)

Call Serp(xa, ya, xb, yb, na)

End Sub

Private Sub Form1_DoubleClick(ByVal sender As Object, ByVal e As System.EventArgs) Handles Me.DoubleClick

End

End Sub

End Class