Лабораторная_работа_№__2-3(2_семестр)0

Лабораторная работа № 2-3

Рекурсия. Рекурсивные алгоритмы и функции.

Цель работы: Знакомство с рекурсивными алгоритмами и функциями.

Теоретические сведения:

\

1. Основные определения

1 .1. Рекурсия

Рекурсивным называется объект, частично состоящий или определяющийся с помощью самого себя. Рекурсивными бывают также алгоритмы и программы.

Простейшим примером рекурсии является картинка в картинке (см. рис. 1). С помощью рекурсии можно определить дерево (см. рис. 2). Пусть О – это пустое дерево, а t1 и t2 тоже деревья (в т.ч. и пустые), тогда построение содержащее вершину с двумя нижерасположенными деревьями является деревом.

Другие примеры:

1.Факториал

если n = 0, то 0! = 1, тогда n!= n * (n −1)!

2.Возведение в степень

если n = 0, то x0 = 1, тогдаxn = x * xn−1

3.Числа Фибоначчи

Fib(0)=0

Fib(1)=1

тогда для n >1 Fib(n) = Fib(n-1) + Fib(n-2)

4.Функция Эйлера (Задача о нахождении наибольшего общего делителя)

если В делится на А нацело, то в этом случае наибольший общий делитель равен А

1

Мощность рекурсивного определения заключается в том, что оно позволяет с помощью конечного высказывания определить бесконечное множество объектов.

1.2. Рекурсивные процедуры и функции

Подпрограмма называется рекурсивной, если она обращается к себе прямо (см. рис. 3) или косвенно (см. рис. 4) через другие подпрограммы. Предусмотрен выход из А.

A

A

B

1.3. Рекурсия изнутри

Самовызов программы ничем не отличается от вызова любой другой программы. Это означает, что

1.В памяти компьютера размещаются параметры, передаваемые подпрограмме.

2.В другом месте памяти сохраняются внутренние (локальные) переменные вызывающей подпрограммы.

3.Запоминается адрес возврата в вызывающую подпрограмму.

4.Управление передается вызываемой подпрограмме.

Количество обращений программы к самой себе называется глубиной рекурсии.

Пример1. НОД – алгоритм Евклида

Public Class Form1

Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load

Dim res As Integer res = nod(12, 8) label1.text = res

End Sub

Function nod(ByVal x As Integer, ByVal y As Integer) As Integer If (x Mod y) = 0 Then

Return y

2

Пример2 факториал

Public Class Form1

Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load

Dim res As Integer

res = Fact(5) label1.text = res

End Sub

Function Fact(ByVal N As Long) As Long

If N <= 0 Then

Return 1

Else

Return Fact(N - 1) * N

End If

End Function

End Class

Или вызов

Fact = Fact(N - 1) * N

Пример3 числа Фибоначчи

Public Class Form1

Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load

Dim res As Integer

res = Fib(3) label1.text = res

End Sub

Function Fib(ByVal n As Integer) As Integer

If n <= 1 Then

Return n

Else

3

Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load

Dim res As Integer

res = A(3, 3) label1.text = res

End Sub

Function A(ByVal M As Long, ByVal N As Long) As Long

If M = 0 Then

Return N + 1

ElseIf N = 0 Then

Return A(M - 1, 0)

Else

Return A(M - 1, A(M, N - 1))

End If

End Function

End Class

Пример 3.

Задача Написать программу построения фрактального изображения из квадрата как из исходного элемента.

Решение Термин фрактал происходит от латинского слова fractus, что в переводе означает поделенный на части, разбитый. Фрактальное изображение – это геометрическая фигура, состоящая из частей, каждая из которых представляет уменьшенную копию целого. Термин фрактал ввел математик фирмы IBM Б.Мандельброт, считающийся основоположником фрактальной геометрии. Различают следующие основные типы фракталов: геометрические, алгебраические, стохастические. Рассмотрим пример построения геометрического фрактала.

Примем следующий алгоритм построения фрактального изображения. На первом шаге уменьшим в два раза стороны исходного квадрата и нарисуем по одному такому уменьшенному квадрату в вершинах исходного квадрата. При этом центры уменьшенных квадратов должны находиться в вершинах исходного квадрата

На втором шаге повторяем действия первого шага применительно к каждому из нарисованных 4-х уменьшенных квадратов. Повторяя данные шаги можно получить фрактальное изображение высокой степени детализации.

Программа, реализующая данный алгоритм, будет состоять из основной процедуры, например, Form1_Click(), из которой будет вызываться процедура S (), служащая непосредственно для построения фрактального изображения. Таким образом,

4

построение фрактала будет начинаться по щелчку левой кнопкой мыши по форме. В процедуре Form1_Click() запишем строку вызова процедуры S () с указанием списка фактических параметров исходного квадрата

S(160, 160, 250)

где:

160,160 - фактические координаты левого верхнего угла исходного квадрата; 250 – фактическая длина стороны исходного квадрата.

Создадим процедуру S(), указав в заголовке перечень параметров

Private Sub S(ByVal x As Integer, ByVal y As Integer, ByVal z As Integer)

где:

x, y – формальные координаты левого верхнего угла квадрата; z – формальная длина стороны квадрата.

Начальные значения формальным параметром передаются из процедуры Form1_Click() посредством строки вызова процедуры S(160, 160, 250).

Управляющим параметром сделаем z. Это означает, что координаты левого

Значение координаты x для левого верхнего уменьшенного квадрата должно быть уменьшено на величину z/4, так как сторона уменьшенного квадрата равна z/2, а его центр должен находиться в вершине исходного квадрата (рис.2.37). Значение координаты y уменьшится на такую же величину по тем же соображениям. Сторона квадрата будет равна z/2. Следовательно, для верхнего левого квадрата имеем

S(x - z / 4, y - z / 4, z / 2)

Для правого верхнего квадрата (рис.2.70) значение x увеличивается на длину стороны исходного квадрата z и уменьшается на половину длины стороны уменьшенного квадрата z/4. Значение y уменьшается на z/4. Следовательно, для верхнего правого квадрата имеем выражение

S(x + z - z / 4, y - z / 4, z / 2)

Для правого нижнего квадрата (рис.2.370 по аналогичным соображениям имеем

S(x - z / 4, y + z - z / 4, z / 2)

И, наконец, для левого нижнего квадрата

S(x + z - z / 4, y + z - z / 4, z / 2)

В процедуре S() также надо задать поверхность для рисования

Dim r As Graphics = CreateGraphics()

метод рисования (перо красного цвета) r.DrawRectangle(Pens.Red, x, y, z, z)

и, самое главное, условие выхода из процедуры S(). Для этого надо определиться, до какого значения делить сторону исходного квадрата z. Чтобы получить

5

пополам стороны исходного квадрата один раз, так как условие перехода к третьему шагу – деление 125 пополам, то есть 62,5 )

If z < 80 Then Exit Sub

По тем же соображениям задать 50

If z < 50 Then Exit Sub

Ниже приведен полный текст программы. После ввода программы и нажатия клавиши F5 перед тем как щелкнуть по форме, чтобы запустить процедуру Form1_Click(), распахните форму на весь экран.

Private Sub S(ByVal x As Integer, ByVal y As Integer, ByVal z As Integer)

Dim r As Graphics = CreateGraphics() If z < 80 Then Exit Sub r.DrawRectangle(Pens.Red, x, y, z, z) S(x - z / 4, y - z / 4, z / 2)

S(x + z - z / 4, y - z / 4, z / 2)

S(x - z / 4, y + z - z / 4, z / 2) S(x + z - z / 4, y + z - z / 4, z / 2)

End Sub

Private Sub Form1_Click(ByVal sender As Object, ByVal e As System.EventArgs) Handles MyBase.Click

S(160, 160, 250) End Sub

Измените условие выхода из подпрограммы на следующее

If z < 6 Then Exit Sub

и вы получите впечатляющий результат – мелкий фрактальный рисунок похожий на микросхему

Пример 4 Задача Написать программу строящую фрактальное изображение по

следующему алгоритму. Первый шаг: на прямой линии как на гипотенузе строится равнобедренный прямоугольный треугольник. Второй шаг: на катетах этого треугольника как на гипотенузах строятся два равнобедренных прямоугольных треугольника. При этом один треугольник развернут вовне, а второй вовнутрь исходного треугольника. Третий шаг: на катетах построенных на предыдущем шаге треугольников как на гипотенузах строятся по два равнобедренных треугольника, развернутых по тому же принципу, как на предыдущем шаге. И так далее.

Решение Для графической иллюстрации алгоритма будем пошагово строить фрактальное изображение. Поэтому сразу приведем текст программы.

Sub D(ByRef x1 As Integer, ByRef y1 As Integer, ByRef x2 As Integer, ByRef y2 As Integer, ByRef k As Integer)

6

Dim xn As Integer Dim yn As Integer

Dim r As Graphics = CreateGraphics() If k > 0 Then

xn = (x1 + x2) / 2 - (y2 - y1) / 2 yn = (y1 + y2) / 2 + (x2 - x1) / 2

r.DrawLine(Pens.Red, x1, y1, x2, y2) D(x1, y1, xn, yn, k - 1)

D(x2, y2, xn, yn, k - 1) End If

End Sub

Private Sub Form1_Click(ByVal sender As Object, ByVal e As System.EventArgs) Handles MyBase.Click

D(300, 300, 500, 400, 0) End Sub

Программа состоит из процедуры D(), рассчитывающей и строящей изображение,

первоначальном отрезке как на гипотенузе

Появилась точка (xn,yn), координаты которой рассчитываются по известным из аналитической геометрии зависимостям

xn = (x1 + x2) / 2 - (y2 - y1) / 2 yn = (y1 + y2) / 2 + (x2 - x1) / 2

Меняя знаки между полу суммами можно управлять расположением построенного треугольника: он будет находиться либо с одной стороны по отношению

При к=2 кроме рассмотренных двух построений будет выполнено ещё одно. На двух катетах полученного на предыдущем шаге прямоугольного треугольника как на гипотенузах построятся два прямоугольных треугольника. Треугольники являются уменьшенными в два раза подобиями исходного треугольника. Таким образом, принцип построения фрактального и изображения соблюдается. Кроме того один треугольник будет расположен снаружи, а другой внутри исходного треугольника

Для к =3 получим ещё 4 прямоугольных треугольника Они построены на катетах двух треугольников, полученных на предыдущем шаге, как на гипотенузах. По размерам эти треугольники вдвое меньше полученных на предыдущем шаге. Расположение треугольников так же соответствует оговоренному принципу: один

7

внутри, второй снаружи по отношению к треугольнику, на катетах которого они построены.

Текст программы приведены ниже.

Sub D(ByRef x1 As Integer, ByRef y1 As Integer, ByRef x2 As Integer, ByRef y2 As Integer, ByRef k As Integer)

Dim xn As Integer Dim yn As Integer

Dim r As Graphics = CreateGraphics() If k >= 0 Then

xn = (x1 + x2) / 2 - (y2 - y1) / 2 yn = (y1 + y2) / 2 + (x2 - x1) / 2 Call D(x1, y1, xn, yn, k - 1)

D(x2, y2, xn, yn, k - 1) Else

r.DrawLine(Pens.Red, x1, y1, x2, y2) End If

r.Dispose() End Sub

Private Sub Form1_Click(ByVal sender As Object, ByVal e As System.EventArgs) Handles MyBase.Click

D(300, 300, 500, 400, 16) End Sub

Выполните программу для к=3, к=4, к=16

Пример 5.

Задача Написать программу для построения фрактального изображения по следующему алгоритму. На первом шаге стороны равностороннего треугольника делим пополам и соединяем прямыми. В результате образуется подобный вписанный треугольник, опирающийся своими вершинами на середины сторон исходного треугольника. На втором шаге к образовавшимся по углам трем треугольным областям применяем действия, описанные на первом шаге. В результате имеем ещё 9 треугольных областей. На третьем шаге к образовавшимся 9 треугольным областям применяем тот же алгоритм и получаем ещё 27 треугольных областей. И так далее. Данное изображение называется решетом Серпинского (В.Серпинский – польский математик начала 20-го века).

Решение Создадим две подпрограммы. Одну T() для рисования исходного и всех последующих вписанных треугольников , вторую TD() - для расчета координат вершин образующихся вписанных треугольников и передачи значений этих координат в подпрограмму Т().

Sub T(ByVal x1 As Single, ByVal y1 As Single, ByVal x2 As Single, ByVal y2 As Single, ByVal x3 As Single, ByVal y3 As Single)

8

Dim r As Graphics = CreateGraphics() r.DrawLine(Pens.Black, x1, y1, x2, y2) r.DrawLine(Pens.Black, x2, y2, x3, y3) r.DrawLine(Pens.Black, x3, y3, x1, y1)

End Sub

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

Dim x1j, y1j, x2j, y2j, x3j, y3j As Single If n > 0 Then

x1j = (x1 + x2) / 2 y1j = (y1 + y2) / 2 x2j = (x2 + x3) / 2 y2j = (y2 + y3) / 2 x3j = (x3 + x1) / 2 y3j = (y3 + y1) / 2

T(x1j, y1j, x2j, y2j, x3j, y3j) TD(x1, y1, x1j, y1j, x3j, y3j, n - 1) TD(x2, y2, x1j, y1j, x2j, y2j, n - 1) TD(x3, y3, x2j, y2j, x3j, y3j, n - 1)

End If End Sub

Передача значений координат производится через параметры вызова подпрограммы T()

T(x1j, y1j, x2j, y2j, x3j, y3j)

В результате подпрограмма Т() с помощью трех операторов, рисующих линии,

r.DrawLine(Pens.Black, x1, y1, x2, y2) r.DrawLine(Pens.Black, x2, y2, x3, y3) r.DrawLine(Pens.Black, x3, y3, x1, y1)

вычерчивает новый треугольник. Обратите внимание, что аргументами методов DrawLine() будут уже не x1, y1, x2, y2, x3, y3 как для исходного треугольника, а, переданные через вызов, значения x1j, y1j, x2j, y2j, x3j, y3j.

Далее в подпрограмме TD() записаны три оператора

TD(x1, y1, x1j, y1j, x3j, y3j, n - 1)

TD(x2, y2, x1j, y1j, x2j, y2j, n - 1)

TD(x3, y3, x2j, y2j, x3j, y3j, n - 1)

которые являются вызовами подпрограммы TD() (то есть вызывают ту же подпрограмму, в которой сами находятся). Обратите внимание на параметры, которые они передают в подпрограмму TD(). Это координаты вершин трех образовавшихся по углам треугольников (рис.2.82). Кроме того, передается значение параметра n, уменьшенное на 1 (n - число циклов делений сторон) . Для завершения работы программы в подпрограмме TD() предусмотрен условный оператор If , проверяющий равенство n нулю. При n = 0 работа программы завершается.

9

Для запуска программы предусмотрена процедура Form1_Click(), в которой объявляется графический объект r и записаны вызовы подпрограмм T() и TD() с начальными значениями параметров. Ниже приведен полный текст программы.

Private Sub Form1_Click(ByVal sender As Object, ByVal e As System.EventArgs) Handles MyBase.Click

Dim r As Graphics = CreateGraphics() T(330, 20, 630, 500, 30, 500)

TD(330, 20, 630, 500, 30, 500, 6) End Sub

Sub T(ByVal x1 As Single, ByVal y1 As Single, ByVal x2 As Single, ByVal y2 As Single, ByVal x3 As Single, ByVal y3 As Single)

Dim r As Graphics = CreateGraphics() r.DrawLine(Pens.Black, x1, y1, x2, y2) r.DrawLine(Pens.Black, x2, y2, x3, y3) r.DrawLine(Pens.Black, x3, y3, x1, y1)

End Sub

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

Dim x1j, y1j, x2j, y2j, x3j, y3j As Single If n > 0 Then

x1j = (x1 + x2) / 2 y1j = (y1 + y2) / 2 x2j = (x2 + x3) / 2 y2j = (y2 + y3) / 2 x3j = (x3 + x1) / 2 y3j = (y3 + y1) / 2

T(x1j, y1j, x2j, y2j, x3j, y3j) TD(x1, y1, x1j, y1j, x3j, y3j, n - 1) TD(x2, y2, x1j, y1j, x2j, y2j, n - 1) TD(x3, y3, x2j, y2j, x3j, y3j, n - 1)

End If End Sub

1.4. Опасности рекурсии

1. Опасность бесконечных рекурсий Пример 1

Private Function BADfact(n As Double) As Double If n = 0 Then

BADfact=1

Else

BADfact=BADfact(n-1)*n ‘ может оказаться n < 0

End If End Function

10