Файл: Рекурсивные и итерационные алгоритмы: Особенности и примеры использования (История развития языка программирования Pascal).pdf

k:= exp(n*ln(x));

Можно избежать таких сложностей, разработав собственную функцию или процедуру вычисления степени числа, и затем использовать созданный модуль при необходимости.

Ниже реализовано возведение целого числа в целую неотрицательную степень при помощи рекурсивной функции.

Вычисление степени с помощью рекурсивной функции.

function stepen(n:integer; st: integer): integer;

begin

if (st>0) then

stepen:=n*stepen(n,st-1)

else stepen:=1;

end;

Код программы stepen.pas представлен в Приложении 1.

Скриншот выполнения программы представлен на рисунке 13.

Рисунок – Возведение числа в степень при помощи рекурсивной функции

Анализ результата показывает, что все заданные числа правильно возведены в указанную степень.

2.5.2 Вычисление факториала числа рекурсивным и итерационным способами

Сравним эффективность по времени итерационной и рекурсивной реализации программы на примере вычисления факториала числа. Программа fact1.pas вычисляет факториал числа с помощью рекурсивной функции, а программа fact2.pas - на основе определения. Полный код программ представлен в Приложении 2.

function fact(n:integer):integer;{рекурсивная функция

var f:integer;

begin

if (n<=1) then f:=1

else

begin

f:=fact(n-1)*n;

writeln ('Шаг ',n,': n! = ',f);

end;

fact:=f;

end;

Скриншот выполнения программы представлен на рисунке 14.

Рисунок – Вычисление факториала при помощи рекурсивной функции

Можно проанализировать, как организуется выполнение данной рекурсивной функции в памяти компьютера.

В таблицах 2, 3 рассмотрены шаги по выполнению алгоритма для n = 3.

Таблица – Выполнение рекурсивного алгоритма (спуск)

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

Таблица – Выполнение рекурсивного алгоритма (подъем)

Для сравнения вычисление факториала итерационным методом:

//начальное значение переменной-счетчика

fact:=1;

// вычисление факториала как произведения чисел от 1 до n

for i:=1 to n do

begin

if (n<=1) then fact:=1

else fact:=fact*i;

writeln ('Итерация ',i,': n = ',fact);

end;

Скриншот выполнения программы представлен на рисунке 15.

Рисунок - Вычисление факториала при помощи итерационной процедуры

Сравнение временных характеристик рекурсивного и итерационного алгоритмов представлены в таблице 4.

Отличие времени выполнения программы от представленного на скриншоте объясняется временем реакции пользователя при вводе данных в ответ на запрос программы.

В обоих случаях максимальное натуральное число, для которого факториал числа возможно вычислить без ошибки переполнения - 12.

Таблица - Сравнение временных характеристик рекурсивного и итерационного алгоритмов

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

2.5.3 Рекурсивная процедура печати звездочек

В предложенной ниже программе реализована рекурсивная процедура вывода на экран строки из звездочек. Количество звездочек у строке определяется пользователем и вводится им с клавиатуры.

Код программы печати звездочек (файл stars.pas).

program Stella;

var n:integer;

// Рекурсивная процедура печати звездочек

procedure Stars(count: integer);

var

i:integer;

begin

for i:=1 to count do

write('*');

end;

begin

write('Сколько звездочек надо вывести? ');

readln(n);

stars(n);

end.

Результат выполнения программы при разных значениях параметра n представлен на рисунке 15.

Рисунок – Результат выполнения программы

3. ФРАКТАЛЬНЫЕ ОБЪЕКТЫ

В математике описываются очень интересные графические объекты – фракталы.

Фрактал (лат. fractus — дроблёный, сломанный, разбитый) - множество, обладающее свойством самоподобия (объект, в точности или приближённо совпадающий с частью себя самого, то есть целое имеет ту же форму, что и одна или более частей).

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

Фракталы – идеальные объекты с очки зрения их построения при помощи рекурсивных процедур.

Термин «фрактал» ввел в обиход французским и американским математиком Бенуа Мандельбротом в 1975 году. С тех пор и по настоящий день фрактальные объекты являются объектом пристального внимания не только математиков, но и исследователей в других научных направлениях. Дело в том, что найдено удивительное сходство между фрактальными объектами и объектами живой и неживой природы.[5]

В настоящее время изучено множество фракталов, многие из них получили особенные названия.

Ниже представлены примеры популярных математических фракталов. Они графически реализованы в среде PascalABC с помощью рекурсивного подхода.

3.1 Дерево Пифагора

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

Рисунок – Фрактальный объект дерево Пифагора

Дерево Пифагора очень напоминает вилок капусты брокколи (рисунок 18).

Рисунок – Вилок капусты брокколи

На рисунке 16 представлено классическое дерево Пифагора. В математике рассматриваются и произвольные фрактальные объекты – например, обдуваемое ветром дерево Пифагора (угол построения объектов отличен от 45⁰) – рисунок 19, а также дерево, которое строится не с помощью квадратов, а с помощью отрезков – рисунок 20.  

Рисунок – Обдуваемое ветром дерево Пифагора

Рисунок – Дерево Пифагора, построенное из отрезков

Ниже представлен код рекурсивной программы построения классического дерева Пифагора на языке программирования PascalABC.

Код программы PifagorTree.pas

program PifagorTree;

uses GraphABC;

Procedure Ris(x1, y1, l: Integer; a1: Real);

Begin

MoveTo(x1, y1);

LineTo(x1 + Round(l * cos(a1)), y1 - Round(l * sin(a1)),clGreen);

LineTo(x1 + Round(l * sqrt(2) * cos(a1 + pi/4)),

y1 - Round(l * sqrt(2) * sin(a1 + pi/4)),clGreen);

LineTo(x1 + Round(l * cos(a1 + pi/2)), y1 - Round(l * sin(a1 + pi/2)),clGreen);

LineTo(x1, y1,clGreen)

End;

// Рекурсивная процедура рисования дерева

Procedure Tree(x, y, l, a: Real);

Begin

If l > 4 Then

Begin

Ris(Round(x), Round(y), Round(l), a);

Tree(x - l*sin(a), y - l * cos(a), l / sqrt(2), a + pi / 4);

Tree(x - l * sin(a) + l / sqrt(2) * cos(a + pi/4),

y - l * cos(a) - l / sqrt(2) * sin(a + pi/4),

l / sqrt(2), a - pi/4)

End

End;

Begin

SetWindowCaption('Классическое Дерево Пифагора');

SetWindowSize(730,500);

ClearWindow;

//Вызов рекурсивной процедуры

Tree(280, 460, 100, 0);

End.

Изначально рекурсивная процедура Tree() вызывается со следующими параметрами:

x = 280, y = 460 – координаты точки, с которой начинается построение дерева Пифагора,

l = 100 – длина стороны квадрата,

a = 0 – угол поворота построения при очередной итерации.

Результат построения представлен на рисунке 21.

Рисунок – Результат работы программы

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

Кривая Коха - это фрактальный объект, описанный в 1904 году математиком из Швеции Хельге фон Кохом.[17]

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

Три копии кривой Коха, построенные (остриями наружу) на сторонах правильного треугольника, образуют замкнутую кривую бесконечной длины, называемую снежинкой Коха.

На рисунке 22 представлены процесс и результат построения снежинки Коха.

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

Рисунок – Процесс получения снежинки Коха

Программа, реализующая построение снежинки Коха (файл Sneg.pas), полностью приведена в Приложении 3.

Фрагмент рекурсивной процедуры построения очередного треугольника:

program Sneg;

uses GraphABC;

//Рекурсивная процедура ris1

procedure ris(x, y, l, u : Real; t : Integer);

procedure ris1(Var x, y: Real; l, u : Real; t : Integer);

begin

ris(x, y, l, u, t);

x := x + l*cos(u);

y := y - l*sin(u);

end;

begin

if t > 0 then

begin

l := l/3;

ris1(x, y, l, u, t-1);

ris1(x, y, l, u+pi/3, t-1);

ris1(x, y, l, u-pi/3, t-1);

ris1(x, y, l, u, t-1);

end

else

Line(Round(x), Round(y), Round(x+cos(u)*l), Round(y-sin(u)*l))

end;

Результат работы программы представлен на рисунке 23.

Рисунок – Результат выполнения программы Sneg.pas

3.3 Множество Мандельброта

В математике множество Мандельброта – это фрактал, описываемый совокупностью точек С на комплексной плоскости, для которых описывается не уходящая в бесконечность итеративная последовательность:

Иллюстрация множества Мандельброта представлена на рисунке 24.

Рисунок – Множество Мандельброта

Между графическим изображением множества Мандельброта и хаотическими изменениями цены на финансовых рынках была установлена связь – оба явления обладают некоторыми схожими свойствами.[2]

На рисунке 25 представлена реализация в программе PascalABC множества Мандельброта (файл Mandelbrot.pas).

Рисунок – Программная реализация множества Мандельброта

Код программы построения множества Мандельброта (файл Mandelbrot.pas) представлен в Приложении 4.

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