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

Содержание:

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

Объектом исследования курсовой работы является рекурсия.

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

Цель курсовой работы – изучение рекурсивного подхода к программированию на примере решения отдельных задач в среде программирования PascalABC.

Задачи курсовой работы:

• изучить понятие рекурсии и рекурсивного алгоритма;
• рассмотреть возможность реализации рекурсивных алгоритмов на языке программирования высокого уровня Pascal в среде программирования PascalABC;
• изучить основные команды и операторы для работы с файлами разного типа;
• разработать программные этюды с использованием рекурсивных процедур и функций;
• составить несколько программ, реализующих рекурсивные алгоритмы для построения фракталов;
• проанализировать результаты выполнения курсовой работы.

1. РЕКУРСИЯ. РЕКУРСИВНЫЕ ПРОЦЕДУРЫ И ФУНКЦИИ

1.1 Понятие рекурсии

На запрос «Рекурсия» Google выдает 5 миллионов результатов при частоте показа 14 тысяч ежемесячно.

Определение, которое находится на сайте Открытой энциклопедии Википедия, гласит:

«Рекурсия — определение, описание, изображение какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя».

Рекурсия (от лат. recurrere — «возвращаться»):

• самоповторение;
• способ выражения понятия через само себя;
• введение некоторого предмета или события в самого себя, как элемента.

Рекурсия – это способ определения объекта, при котором он фрагментарно описывается через такой же объект. Описание, содержащее рекурсию, является рекурсивным описанием. [12]

Термин «рекурсия» применяется в разных специальных сферах знаний - от лингвистики до логики. Самое широкое применение рекурсия имеет в математике и информатике. Рекурсию относят к лингвистическим универсалиям, то есть считается, что рекурсия свойственна любому естественному языку.

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

1.1.1 Рекурсия в лингвистике

Рекурсия больше известна специалистам как способ определения и описания сложных структур в математике и информатике. Но рекурсивные подходы в языкознании возникли гораздо раньше и известны, например, в мифологии. Считается, что использование рекурсии – то есть описания объекта через себя самого – в естественном языке обладает высоким уровнем абстракции и/или психологического воздействия.

Пример рекурсии из русского фольклора:

Вот море,

А на море – суша,

А на суше – пальма,

А на пальме клоп сидит

И видит море,

А на море – суша ...

Так же примером рекурсивного подхода в лингвистике служит стихотворная форма английского поэта Роберта Бернса, известная в России в переводе С.Я. Маршака – «Дом, который построил Джек».

На рекурсивную конструкцию для усиления яркости и сюжетной завершенности опираются многие писатели. Например, такой подход реализован в известном стихотворении А.Блока:

Ночь, улица, фонарь, аптека.

Бессмысленный и тусклый свет.

Живи еще хоть четверть века –

Все будет так. Исхода нет.

Умрешь – начнешь опять сначала,

И повторится все, как встарь:

Ночь, ледяная рябь канала,

Аптека, улица, фонарь.

1.1.2 Рекурсия в искусстве

Многочисленные примеры рекурсивного подхода можно найти в искусстве.

Классическим примером рекурсивного изображения является одна из визуальных форм рекурсии, названная «Эффект Дросте» в соответствии с наименованием марки какао Droste, использовавшей вышеописанный эффект в рекламе [19]. Картинка с «эффектом Дросте» представлена на рисунке 1.

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

Рисунок – Эффект Дросте

Рисунок – Рекурсивный объект – матрешка

1.1.3 Рекурсия в физике

Известны рекурсивные явления и в физике.

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

Рисунок – Пример бесконечной рекурсии с зеркалом

Еще одним известным примером безграничной рекурсии является эффект самовозбуждения (положительной обратной связи) у электронных схем усиления, когда сигнал с выхода попадает на вход, усиливается, снова попадает на вход схемы и снова усиливается. Усилители, для которых такой режим работы является штатным, называются автогенераторы.[7]

1.1.4 Рекурсия в математике

В математике и ее разделе – логике - многие объекты имеют рекурсивные определения.

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

Натуральное число – это либо 1, либо целое число, следующее за натуральным.

n-й степенью целого числа является 1, если n = 0 и число = a* a^n-1 при n отличном от 0.

Факториалом целого неотрицательного числа n является число 1, если n = 0, т.е. 0! = 1 или число n!=n*(n-1)! в противном случае. Иначе говоря,

Из приведенных примеров хорошо видно, что в рекурсивном определении всегда выделяются два случая:

• базовый,
• рекурсивный.[13]

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

Для математики характерны также рекурсивные последовательности.[1]

Классическими, но неединственными, примерами рекуррентных последовательностей являются:

• числа Фибоначчи;
• формула золотой пропорции.

Числовой ряд, носящий сегодня итальянского математики Фибоначчи (Леонардо Пизанского), вырос из проблемы с кроликами, которая была изложена ученым в книге «Liber abacci» (1202 год):

Человек посадил пару кроликов в загон, окруженный со всех сторон стеной. Сколько пар кроликов за год может произвести на свет эта пара, если известно, что каждый месяц, начиная со второго, каждая пара кроликов производит на свет одну пару?

Последовательность Фибоначчи определяется следующим рекуррентным соотношением:

Пе5рвые члены последовательности Фибоначчи:

1, 1, 2, 3, 5, 8, 13, 21,34,…

Золотая пропорция выражается с помощью рекуррентной формулы

Интересным математическим объектом, которые строятся на рекурсивной основе по принципу самоподобия, являются фракталы. Они подробнее рассмотрены в главе 3.

1.2 Рекурсия в программировании

В программировании рекурсией является вызов функции (процедуры) из самой процедуры (функции).

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

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

Рекурсия — это свойство объекта подражать самому себе. Объект является рекурсивным, если его части выглядят также как весь объект. Рекурсия очень широко применяется в математике и программировании:

• структуры данных:
  • • граф (в частности деревья и списки) можно рассматривать как совокупность отдельного узла и подграфа (меньшего графа);
    • строка состоит из первого символа и подстроки (меньшей строки);
• некоторые методы сортировки данных (например, QuikSort);
• построение фрактальных объектов;
• построение рекурсивных математических последовательностей;
• шаблоны проектирования, например декоратор, при реализации многопоточного сервера. Объект декоратора может включать в себя другие объекты, также являющиеся декораторами. [16]

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

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

Наиболее точно отражает дилемму выбора быть или не быть рекурсии цитата Ли Колдуэлла, опубликованная в Интернете:

«Циклы могут ускорить работу программы. Рекурсия может ускорить работу программиста. Выбирайте, что важнее в вашей ситуации!».

В следующем разделе курсовой работы рассмотрены основы программирования на языке Pascal ABC и реализация в нем алгоритмов с применением рекурсивного подхода.

2. РЕКУРСИВНЫЕ ПРОЦЕДУРЫ И ФУНКЦИИ

2.1 История развития языка программирования Pascal

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

Язык программирования высокого уровня Pascal был разработан в 1968-1971 годах швейцарским профессором Никлаусом Виртом (рисунок 4) с целью обучения студентов. Свой язык программирования Вирт назвал в честь яркого французского математика, физика, философа, изобретателя первого механического арифмометра Блеза Паскаля. [4]

Рисунок – Никлаус Вирт

Pascal быстро приобрел популярность среди разработчиков программного обеспечения благодаря своим очевидным достоинствам, к которым относят:

• простоту синтаксиса языка, прозрачность и структурированность программного кода;
• невысокие требования к аппаратным и системным ресурсам как со стороны компилятора языка Pascal, так и со стороны программ на этом языке;
• универсальность языка программирования Pascal, которая дает возможность разрабатывать на этом языке программы в рамках любой предметной области;
• благодаря строгой типизации языка программирования существенно минимизируется количество ошибок в кодах программ;
• поддержку различных современных технологий программирования (структурного программирования, программирования «сверху вниз», объектно-ориентированного программирования). [18]

В настоящее время выделяют три стандарта языка программирования высокого уровня Pascal:

1. Unextended Pascal - нерасширенный Pascal – это классический вариант языка, который был принят в 1983 году и фактически целиком совпадает с описанием языка Pascal по Никлаусу Вирту.
2. Extended Pascal - расширенный Pascal – стандарт языка с включенными в него расширениями, касающимися технологии модульного программирования (интерфейсная часть и реализация, отдельная компиляция модулей, импорт-экспорт подпрограмм). В расширенной версии также добавлены некоторые процедуры и функции – такие, как работа со строковыми переменными, прямой доступ файлов и другие.
3. Object Pascal – объектный Pascal – стандарт, утвержденный в 19993 году. Это язык программирования с наличием классов, характеризующихся свойствами и методами; поддерживающий наследование классов, полиморфизм (переопределение методов у потомков), а также иные атрибуты объектно-ориентированной методологии программирования. Язык программирования фирма Borland - разработчик среды Delphi начиная с версии Delphi 7.0 в официальной документации именует язык программирования Object Pascal как язык программирования Delphi.

Наиболее популярные формы реализации языка программирования Pascal представлены в таблице 1.

Таблица – Версии языка программирования Pascal

2.2 Основы программирования на языке программирования Pascal

Алфавит языка программирования высокого уровня Pascal составляют:

• строчные и заглавные латинские буквы;
• цифры десятичной системы счисления (0 – 9);
• символы кириллицы;
• зарезервированные символы (рисунок 5)

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

• зарезервированные сочетания символов (рисунок 6)

Рисунок – Зарезервированные сочетания символов языка Pascal

• ключевые (зарезервированные) слова.

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

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

Идентификатором в языке программирования языка Pascal называется совокупность букв, знака подчеркивания, цифр, которая может начинаться только со знака подчеркивания или буквы, Наименование любого программного объекта (переменные, константы, типы, процедуры, функции, программа) должно по правилам языка являться идентификатором.

Информация, которую обрабатывает компьютер, хранится в его памяти. Отдельный информационный объект (число, символ, строка, таблица и другие) называется величиной. Величины в программировании, так же, как и математические величины, делятся на переменные и константы (постоянные). Pascal является строго типизированным языком программирования. Это означает, что любой объект до своего использования должен быть описан, то есть указано имя объекта и его тип. Иерархия типов данных языка программирования высокого уровня Pascal представлена на рисунке 8.

Рисунок – Иерархия типов языка программирования Pascal

2.3 Основные алгоритмические структуры в Pascal

Язык программирования высокого уровня Pascal поддерживает технологию структурного программирования, одним из постулатов которой является утверждение, что для реализации любого алгоритма достаточно трех базовых алгоритмических структур:

• следование;
• ветвление;
• повторение (цикл).

2.3.1 Линейный алгоритм

Линейная алгоритмическая структура (следование) представляет собой структуру, в которой пошагово описываются и выполняются те или иные команды. [14]

Линейный алгоритм представлен на рисунке 9.

Рисунок – Линейный алгоритм

2.3.2 Разветвляющийся алгоритм

Разветвляющиеся алгоритмы – это такая вычислительная структура, которая содержит не одну, а несколько возможных ветвей решения, в структуре алгоритма есть хотя бы одна операция сравнения, т.е. в зависимости от выполнения некоторого логического условия вычислительный процесс осуществляется по одной или другой ветви. [11]

Реализовать такую структуру можно с помощью условного оператора. Он имеет два вида записи (рисунок 10):

Рисунок – Неполная и полная формы оператора условного перехода

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

Рисунок - Разветвляющийся алгоритм

2.3.3 Циклический алгоритм

Простые циклы – это такая вычислительная схема разветвленной структуры, в которой одна ветвь операции сравнения является обратной связью на предыдущую часть алгоритма, т.е. идет назад. Таким образом, некоторая последовательность операций алгоритма будет выполняться многократно (в цикле), образуя тело цикла. Так можно многократно вычислять значения выражений по одним и тем же математическим зависимостям для различных значений входящих в них величин. Использование циклов позволяет сократить объем схемы алгоритма и длину программы. Циклы могут быть с заданным и с неизвестным числом повторений. Переменная, которая управляет циклом, называется параметром цикла. [20]

При построении любого цикла необходимо предусмотреть три момента:

1) организовать данные для первого цикла;

2) после выполнения цикла надо обновлять данные для очередного цикла;

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

В языке программирования Pascal реализованы три оператора цикла:

• цикл с параметрами for …to…do <тело цикла>;
• цикл с предусловием

while <условие> do <тело цикла>;

• цикл с постусловием

repeat <тело цикла> until <условие>.

Блок-схема реализации циклического алгоритма на примере цикла с параметрами представлена на рисунке 10.

Рисунок – Циклический алгоритм

2.4 Процедуры и функции в языке программирования Pascal

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

Подпрограмма - независимая часть программы, реализующая установленный алгоритм и разрешающая обращение к ней из разных частей основного модуля программы. Использование подпрограмм является основой одного из самых современных методов программирования - структурного программирования.[9]

В языке Паскаль существует два вида подпрограмм: процедура (ключевое слово - PROCEDURE) и функция (ключевое слово - FUNCTION).

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

Функция как объект языкаPascal является другой версией реализации технологии построения программ с использованием алгоритмической структуры группирования. Можно утверждать, что функция есть частный случай определенного типа процедур, а именно процедур с одним параметром – переменной (с одним результатом).

Функция отличается от процедуры тем, что всегда возвращает в точку вызова одно значение. При этом функция, как и процедура, может содержать параметры – значения или быть без них.[10]

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

Синтаксис применения процедур и функций в Pascal имеет следующий формат.

Процедура

PROCEDURE <имя процедуры> (аргументы; VAR параметр-результат: тип);

begin

< тело процедуры>

end;

Функция

FUNCTION <имя функции> (аргументы): тип;

begin

< тело функции>

end;

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

2.5 Реализация рекурсии в языке программирования Pascal

Ниже рассмотрены как классические примеры использования рекурсии – реализация операции возведения в степень и вычисление факториала числа, так и менее распространенные программные этюды с использованием рекурсии на языке программирования PascalABC.

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

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

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.

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

Шаг рекурсии, значение n	Значение функции factorial (n)	Примечание
1. n = 3	factorial (3) =3* factorial (2)	Не базовый случай
2. n = 2	factorial (2) =2* factorial (1)	Не базовый случай
3. n = 1	factorial (1) =1* factorial (0)	Не базовый случай
3. n = 0	factorial (0) =1	Базовый случай

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

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

Шаг рекурсии, значение n	Значение функции factorial (n)	Примечание
1. n = 0	factorial (0) =1	Базовый случай
2. n = 1	factorial (1) =1* 1 = 1
3. n = 2	factorial (2) =2* 1 = 2
3. n = 3	factorial (3) =3*2 = 6

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

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

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.

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

N	Рекурсивный метод		Итерационный метод
	Время работы программы, секунды	Результат	Время работы программы, секунды	Результат
5	1.766	120	2.109	120
6	2.531	720	3.391	720
7	1.906	5040	1.984	5040
8	2.094	40320	1.796	40320
9	1.672	362880	3.046	362880
10	2.406	3628800	1.781	3628800
11	2.375	39916800	4.359	39916800
12	6.484	479001600	2.234	479001600
13	2.125	1932053504 ошибка переполнения	1.5	1932053504 ошибка переполнения

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

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.

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

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

Специалисты отмечают и недостатки рекурсивных подходов:

• использование рекурсии часто не является очевидным приемом и требует от разработчика наличия некоторого опыта программирования;
• рекурсивные алгоритмы требовательны к ресурсам компьютера и не являются быстрыми.[15]

ЗАКЛЮЧЕНИЕ

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

Исследованы такие объекты как фрактальное определение, фрактальная формула, фрактальная зависимость, фрактальный алгоритм.

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

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

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

Многие алгоритмы можно реализовать как при помощи рекурсии, так и итерационными методами. На классических задачах, как показано в главе 2, эффективность этих подходов сопоставима, поэтому разработчик-программист может выбирать метод по своему усмотрению.

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

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

СПИСОК ЛИТЕРАТУРЫ

1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 2015. – 412 с..
2. Беллман Р. Динамическое программирование. — М.: Иностранная литература, 2014. – 244 с.
3. Бобровский С. Программирование на языке QBasic для школьников и студентов. – М.:Инфорком-Пресс, ДЕСС, 2017. – 427 с.
4. Боровский, А. C++ и Pascal в Kylix 3. Разработка интернет-приложений и СУБД / А. Боровский. - М.: БХВ-Петербург, 2015. - 544 c.
5. Вирт Н. Алгоритмы + структура данных = программы. - М.: Мир, 1985.- 209 с.
6. Вирт Н. Алгоритмы и структуры данных. - М.: Мир, 1989.- 121 с.
7. Грызлов В.И., Грызлова Т.П. Турбо Паскаль 7.0. - М.: ДМК, 2015. – 400 с.
8. Давыдов, В. Visual C++. Разработка Windows-приложений с помощью MFC и API-функций / В. Давыдов. - М.: БХВ-Петербург, 2018. - 576 c.
9. Дайтибегов Д. - М., Черноусов Е.А. Основы алгоритмизации и алгоритмические языки. - М.: ФиС, 2016.- 563 с.
10. Джонс Ж., Харроу К. Решение задач в системе Turbo Pascal. - М.: ФиС, 2018.- 391 с.
11.  Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — М.: МЦНМО, 2015. – 421 с.
12. Крупский В.Н., Плиско В.Е. Теория алгоритмов – М.: ИЦ «Академия», 2016 – 208 с.
13. Лаврова И.А., Максимова Л.Л. Задачи по теории множеств, математической логике - М.: ФИЗМАТЛИТ, 2014. — 257 с.
14. Лукин С. Н. Turbo Pascal 7.0. Самоучитель для начинающих. – 2-е изд., стер. – М.: Диалог-МИФИ, 2015. – 342 с.
15. Мальцев А.И. Алгоритмы и рекурсивные функции М.: Наука, 2017 – 269 с.
16. Меженный О. А. Turbo Pascal. Самоучитель.- М.: Диалектика, 2018. – 336 с.
17. Тихомирова А.Н. Теория алгоритмов – М.: ИЦ МИФИ, 2016 – 315 с.
18. Усков О.Ф. Программирования на языке Паскаль. Задачник. – С.-Пб.: Питер, 2014. – 336 с.
19. Федоренко Ю.А. Алгоритмы и программы на Pascal. – С.-Пб.: Питер, 2017. – 240 с.
20. Шпак А.Ю., Turbo Pascal 7.0 на примерах— М.: Юниор, 2016. -496 с.

ПРИЛОЖЕНИЕ 1

program power;

// Рекурсивная функция вычисления степени числа

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

begin

if (st>0) then

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

else stepen:=1;

end;

begin

var x,y,i:integer;

writeln (' Программа вычисляет неотрицательную степень целого числа ');

writeln (' при помощи рекурсивной функции ');

writeln('*************************************************************');

writeln;

for i:=1 to 5 do begin

write( 'Введите основание степени x = ');

readln (x);

write( 'Введите показатель степени y = ');

readln (y);

writeln;

writeln( 'Значение ',x,' в степени ',y,' равно ', stepen(x,y));

writeln;

end;

end.

ПРИЛОЖЕНИЕ 2

program factorial_1;

var i, n,fn:integer;

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;

begin

var d := Milliseconds;

writeln (' Программа рекурсивного вычисления факториала числа ');

writeln ('===========================================================');

writeln;write (' Введите натуральное число n = ');

readln(n);

writeln(' Промежуточные вычисления ');

writeln('---------------------------------');

fn:=fact(n);

writeln;writeln (' Факториал числа ');

writeln('-----------------------------');

writeln (' ', n,'! = ', fn);

writeln;

writeln(' Программа выполняется за ',(Milliseconds-d)/1000, ' секунд.');

end.

program factoria1_2;

var i, n,fact:integer;

begin

var d := Milliseconds;

writeln (' Программа вычисления факториала числа по определению ');

writeln ('===========================================================');

writeln;write (' Введите натуральное число n = ');

readln(n);

writeln(' Промежуточные вычисления ');

writeln('---------------------------------');

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

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;

writeln;writeln(' Факториал числа ');

writeln('-----------------------------');

writeln (' ', n,'! = ', fact);

writeln(' Программа выполняется за ',(Milliseconds-d)/1000, ' секунд.');

end.

ПРИЛОЖЕНИЕ 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;

begin

SetWindowSize(425,500);

SetWindowCaption('Снежинка Коха');

SetPenColor(clBlue);

ris(10, 354, 400, pi/3, 4);

ris(410, 354, 400, pi, 4);

ris(210, 8, 400, -pi/3, 4);

end.

ПРИЛОЖЕНИЕ 4

program Mandelbrot;

uses GraphABC;

const

n=255;

max=10;

var

x,y,x1,y1,cx,cy: real;

i,ix,iy: integer;

begin

randomize;

SetWindowSize(400,300);

SetWindowCaption('Множество Мандельброта');

for ix:=0 to WindowWidth-1 do

for iy:=0 to WindowHeight-1 do

begin

x:=0;

y:=0;

cx:=0.002*(ix-720);

cy:=0.002*(iy-150);

for i:=1 to n do

begin

x1:=x*x-y*y+cx;

y1:=2*x*y+cy;

if (x1>max) or (y1>max) then break;

x:=x1;

y:=y1;

end;

if i>=n then SetPixel(ix,iy,RGB(random(255),Random(255),Random(255)))

else SetPixel(ix,iy,RGB(255,255-i,255-i));

end;

end.