5. Использование рекурсии.

В программировании иногда используют рекурсивные операторы, например, процедуры, которые содержат обращение к самим себе. Это обращение может быть прямое - вызовом процедуры внутри самой процедуры, или косвенное - вызовом других процедур, внутри которых есть вызов исходной процедуры.

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

Uses Graph;

var Gd, Gm, x1, y1, { x1, y1 - координаты конца отрезка }

l, delta, { l, delta - длина отрезка и ее приращение }

alfa, ugol: integer; { alfa - угол поворота, ugol - текущий угол в градусах }

Procedure OTREZOK(x, y: integer);

begin x1:= x + round(l*cos(ugol*pi/180));

y1:= y - round(l*sin(ugol*pi/180));

line(x, y, x1, y1);

ugol:= ugol + alfa; { изменение угла }

l:= l + delta; { изменение длины отрезка }

{ условие продолжения рекурсии: }

if (x1 > 0) and (x1 < GetMaxX) and (y1 > 0) and (y1 < GetMaxY)

then OTREZOK(x1, y1); { рекурсивный вызов процедуры }

end;

{ (x, y), (x1, y1) - координаты начала и конца отрезка }

begin ugol:= 0; alfa:= 13; l:= 10; delta:= 3;

Gd:= Detect; InitGraph(Gd, Gm, 'с:\tp7\bgi');

OTREZOK(GetMaxX div 2, GetMaxY div 2); { вызов процедуры }

readln; CloseGraph;

end.

Узор получается перемещением отрезка с вращением вокруг точки (x, y). Поскольку внутри процедуры OTREZOK происходит вызов этой же процедуры с фактическими параметрами (x1, y1), то новое построение отрезка начинается с конца предыдущего. Варьируя alfa и delta можно строить различные спиралевидные узоры.

Практическое задание n. 1. 60

1. С использованием процедуры OTREZOK построить (при alfa= 90^o) прямоугольный и ромбический спиралевидные лабиринты из отрезков разного цвета.

2. Построить прямоугольник со сторонами разного цвета и основанием, движущимся согласно процедуре OTREZOK.

98

Следующий пример показывает использование рекурсии при построении узоров, напоминающих кружева. Задается размер "стежка" - короткой линии длиной dl, функция варьирования угла перемещения ugol в зависимости от номера шага n.

uses Graph;

var gD, gM, n, x, y, x1, y1, k: integer; dl, ugol, ugol_0, s, i: real;

{-----------------------------------------------------------------}

PROCEDURE ANGLE(x, y: integer);

begin n:= n+1;

ugol:=2*pi*n/s; ugol_0:=ugol;{ равномерное увеличение угла по параметру n }

ugol:= ugol_0 + i*sin(k*ugol); { периодическое отклонение угла:

параметр i определяет амплитуду, k - частоту отклонений }

x1:= x + round(dl*cos(ugol)); { (x1, y1) - координаты следующей точки }

y1:= y + round(dl*sin(ugol));

Line(x, y, x1, y1); { рисуем "стежок" }

if n<s then ANGLE(x1, y1) { рекурсивный вызов }

end;

begin gD:= Detect; InitGraph(gD, gM, 'z:\tp7\bgi');

ugol_0:= 0; { начальное значение угла }

n:= -1; { начальное значение счетчика изменения угла }

x:= 300; y:= 70; { координаты начала рисования }

dl:= 4; { размер линии ("стежка") }

k:= 8; { количество циклических изменений угла }

s:= 500; { количество "стежков" узора }

i:= 2. ; { амплитуда циклических изменений угла }

ANGLE(x, y); readln; CloseGraph end.

Вид функции "ugol_0" определяет базовую форму узора. В приведенном варианте "ugol_0" равномерно изменяется от 0 до 2*PI и базовой линией является окружность (многоугольник). Слагаемое i*sin(k*ugol) определяет отклонение от базовой формы узора - циклические пульсации угла и заставляет узор "завиваться" вокруг базовой линии. Коэффициент "k" определяет количество "лепестков" узора, от параметров "i" и "dl" зависит их форма и размер. Параметр "s" определяет количество "стежков" в узоре и следовательно общий размер узора.

Меняя форму базовой линии, функцию пульсации угла, а также размер стежка "dl" в зависимости от номера шага "n", можно получать самые разнообразные узоры. Например, если убрать оператор ugol_0:= ugol;, то базовой линией узора будет прямая, наклоненная к оси "Х" под углом ugil_0. Варьированием i, k, s можно менять периодичность, форму и размер деталей узора.