XVIII Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
Исследование рекурсивных алгоритмов и их применение в программировании
Автор работы награжден дипломом победителя III степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Введение.
В окружающем нас мире встречаются объекты, у которых каждая часть в чем-то сходна с самим объектом. Например, ветка дерева повторяет форму и характер ветвления схожие с самим деревом. Про такие объекты говорят – обладают самоподобием. Приведенные ниже графические объекты также обладают самоподобием.[1] Их называют рекурсивными. (рис.1.)
Рис.1.
В связи с развитием информационных технологий, понятие рекурсивного алгоритма является одним из главных понятий современной науки. Более того, в XXI-ом веке, так называемый век информации, алгоритм - фактор цивилизации.
Теория алгоритмов, как самостоятельная наука, появилась в 30-40х годах ХХ-века и имеет значение во всех направлениях математических наук.
Теория алгоритмов вместе с математической логикой служит основой для построения теории вычислений, проектированияи применения вычислительных устройств к плохо формализуемым объектам. Именно, благодаря теории алгоритмов происходит внедрение математических методов в экономику, лингвистику, психологию, педагогику и другие гуманитарные науки
Объектом исследования является алгоритмы рекурсивной функции.
Цель исследования: возможныеобласти применения в повседневной жизни.
Гипотеза: В технике процедурного программирования рекурсивность в построении подпрограмм проявляется в разработке управляющих структур, которые при выполнении обращаются сами к себе непосредственно или через цепочку других аналогичных структур.
Задачи проекта:
изучить целесообразность применения рекурсии в программировании обусловленные спецификой задач;
определить область памяти, предназначенной для хранения промежуточных значений локальных переменных при каждом следующем рекурсивном обращении.
Методы исследования:
анализ информационных источников
изучение возможностей программных средств для решения специфических задач.
Основная часть.
Рекурсия-процесс повторения элементов самоподобным образом. Например, если два зеркала установить друг напротив друга, то возникающие в них вложенные отражения суть одна из форм бесконечной рекурсии. В программировании рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция A вызывает функцию B, а функция B — функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии. Преимущество рекурсивного определения объекта заключается в том, что такое конечное определение теоретически способно описывать бесконечно большое число объектов.[4] С помощью рекурсивной программы же возможно описать бесконечное вычисление, причём без явных повторений частей программы.
Реализация рекурсивных вызовов функций в практически применяемых языках и средах программирования, как правило, опирается на механизм стека вызовов — адрес возврата и локальные переменные функции записываются в стек, благодаря чему каждый следующий рекурсивный вызов этой функции пользуется своим набором локальных переменных и за счёт этого работает корректно. Оборотной стороной этого довольно простого по структуре механизма является то, что на каждый рекурсивный вызов требуется некоторое количество оперативной памяти компьютера, и при чрезмерно большой глубине рекурсии может наступить переполнение стека вызовов. Вследствие этого, обычно рекомендуется избегать рекурсивных программ, которые приводят (или в некоторых условиях могут приводить) к слишком большой глубине рекурсии.
Рекурсивный алгоритм – это алгоритм, в описании которого прямо или косвенно содержится обращение к самому себе. В технике процедурного программирования данное понятие распространяется на функцию, которая реализует решение отдельного блока задачи посредством вызова из своего тела других функций, в том числе и себя самой.
Процедура или функция может содержать вызов других процедур или функций. В том числе процедура может вызвать саму себя. Никакого парадокса здесь нет – компьютер лишь последовательно выполняет встретившиеся ему в программе команды и, если встречается вызов процедуры, просто начинает выполнять эту процедуру. Без разницы, какая процедура дала команду это делать.[2]
Пример рекурсивной процедуры:
procedure Rec(a: integer);
begin
if a>0 then
Rec(a-1);
writeln(a);
end;
Рассмотрим, что произойдет, если в основной программе поставить вызов, например, вида Rec(3). Ниже представлена блок-схема, показывающая последовательность выполнения операторов.
Пример рекурсивной процедуры (Рис.2.):
Рис. 2.
Процедура Rec вызывается с параметром a = 3. В ней содержится вызов процедуры Rec с параметром a = 2. Предыдущий вызов еще не завершился, поэтому можете представить себе, что создается еще одна процедура и до окончания ее работы первая свою работу не заканчивает. Процесс вызова заканчивается, когда параметр a = 0. В этот момент одновременно выполняются 4 экземпляра процедуры. Количество одновременно выполняемых процедур называют глубиной рекурсии.
Четвертая вызванная процедура (Rec(0)) напечатает число 0 и закончит свою работу. После этого управление возвращается к процедуре, которая ее вызвала (Rec(1)) и печатается число 1. И так далее пока не завершатся все процедуры. Результатом исходного вызова будет печать четырех чисел: 0, 1, 2, 3.
Возможна чуть более сложная схема: функция A вызывает функцию B, а та в свою очередь вызывает A. Это называется сложной рекурсией. При этом оказывается, что описываемая первой процедура должна вызывать еще не описанную. Чтобы это было возможно, требуется использовать опережающее описание.
Пример:
procedure A(n: integer); {Опережающее описание (заголовок) первой процедуры}
procedure B(n: integer); {Опережающее описание второй процедуры}
procedure A(n: integer); {Полное описание процедуры A}
begin
writeln(n);
B(n-1);
end;
procedure B(n: integer); {Полное описание процедуры B}
begin
writeln(n);
if n<10 then
A(n+2);
end;
Опережающее описание процедуры B позволяет вызывать ее из процедуры A. Опережающее описание процедуры A в данном примере не требуется и добавлено из эстетических соображений.
Заключение.
Свойством рекурсивности характеризуются объекты окружающего мира, обладающие самоподобием.
Рекурсия в широком смысле характеризуется определением объекта посредством ссылки на себя.
Рекурсивные функции содержат в своем теле обращение к самим себе с измененным набором параметров. При этом обращение к себе может быть организовано через цепочку взаимных обращений функций.
Решение задач рекурсивными способами проводится посредством разработки рекурсивной триады.
Целесообразность применения рекурсии в программировании обусловлена спецификой задач, в постановке которых явно или опосредовано указывается на возможность сведения задачи к подзадачам, аналогичным самой задаче.
Область памяти, предназначенная для хранения всех промежуточных значений локальных переменных при каждом следующем рекурсивном обращении, образует рекурсивный стек.
Рекурсивные методы решения задач нашли широкое применение в процедурном программировании.
Список используемой литературы
Сайт Компьютеры и программирование. Рекурсивные функции С++. http://function-x.ru/cpp_rekursivnye_funkcii.html
Сайт StudFiles.https://studfile.net/preview/9536361/page:3/
Рекурсивные функции – создание собственной математики Гришин Н. https://habrahabr.ru/post/139755/
Носов В.А. Основы теории алгоритмов и анализа их сложности. – М., 1992.
Фиошин М. -исчисление. – М., 1990.