Обновлено: 02.07.2024

В наше время все больше и большей задач решаются с помощью компьютерных программ. Наверное уже ни одна сфера жизнедеятельности уже не обходится без программного обеспечения, будь то медицина, физика, экономика, бухгалтерия и т.д.
Большинство задач решаемых с помощью программ связанны с обработкой массив данных различных объектов, для обработки которых применяются итерационные и рекурсивные алгоритмы.
Объектом исследования является рекурсивные и итерационные алгоритмы и их сравнение.
Целю работы является сравнение рекурсивные и итерационные алгоритмы и рассмотрение примеров их реализации на одном из языков программирования.
Задачи:
рассмотреть понятие рекурсии и привести примеры ее реализации;
рассмотреть понятие итерации и привести примеры ее реализации;
сравнить их и выявить преимущества и недостатки данных типов алгоритмов.

1 Рекурсия1.1 Понятие рекурсииРекурсия - это такой способ организации вычислительного процесса, при котором подпрограмма в ходе выполнения составляющих ее операторов обращается сама к себе.
Программы, в которых используются рекурсивные процедуры, отличаются простотой, наглядностью и компактностью текста. Такие качества рекурсивных алгоритмов вытекают из того, что рекурсивная процедура указывает что нужно делать, а нерекурсивная больше акцентирует внимание на том, как нужно делать.
Однако за эту простоту приходится расплачиваться неэкономным использованием оперативной памяти, так как выполнение рекурсивных процедур требует значительно большего размера оперативной памяти во время выполнения, чем нерекурсивных. При каждом рекурсивном вызове для локальных переменных, а также для параметров процедуры, которые передаются по значению, выделяются новые ячейки памяти.
Таким образом, какой-либо локальной переменной А на разных уровнях рекурсии будут соответствовать различные ячейки памяти, которые могут иметь разные значения.
Глубиной рекурсии называется максимальное число рекурсивных вызовов процедуры без возвратов, которое происходит во время выполнения программы.
В общем случае любая рекурсивная процедура Rec вкл.

Нет нужной работы в каталоге?

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

Цены ниже, чем в агентствах и у конкурентов

Вы работаете с экспертами напрямую. Поэтому стоимость работ приятно вас удивит

Бесплатные доработки и консультации

Исполнитель внесет нужные правки в работу по вашему требованию без доплат. Корректировки в максимально короткие сроки

Если работа вас не устроит – мы вернем 100% суммы заказа

Техподдержка 7 дней в неделю

Наши менеджеры всегда на связи и оперативно решат любую проблему

Строгий отбор экспертов

Требуются доработки?
Они включены в стоимость работы

Работы выполняют эксперты в своём деле. Они ценят свою репутацию, поэтому результат выполненной работы гарантирован

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

Полезность, важность и необходимость рекурсии, как одного из концептуальных методов решения практических задач подчеркивалась многими мэтрами информатики. Одни из них, это два лауреата премии Тьюринга: американский специалист по системному программированию Д.Кнут и английский теоретик информатики Ч.Хоар.

1. Теория рекурсивных алгоритмов

1.1. Понятие рекурсии и её виды

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

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

Рекурсивный алгоритм (процедура, функция):

-алгоритм называется рекурсивным, если в его определении содержится прямой или косвенный вызов этого же алгоритма;

-рекурсивная функция – одно из математических уточнений интуитивного понятия вычислимой функции.

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

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

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

Подпрограмма – все, что находится внутри рекурсивной функции.

Основное правило рекурсии: до рекурсивного вызова должна стоять проверка на возврат из рекурсии. Существуют следующие виды рекурсии:

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

В данном случае функция r1( ) вызывает саму себя.

using namespace std;

using namespace std;

using namespace std;

void function(int a);

void function (int a)

-ветвящаяся рекурсия – если каждый экземпляр подпрограммы может вызвать себя несколько раз, то рекурсия называется нелинейной или "ветвящейся".

Рис. 1.4. Ветвящаяся рекурсия

using namespace std;

int function(int a);

int function (int a)

a = function (a – 1) * function(a – 2);

Function(n++); return n;

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

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

1.2. Общие принципы программной реализации рекурсии .

В программировании рекурсия – вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная рекурсия), например, функция A вызывает функцию B, а функция B – функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.

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

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

Нужно учитывать одну особенность, характерную для рекурсивных программ, подобных той, которую используют для генерации чисел Фибоначчи. Каждый уровень рекурсии в функции fibonacci удваивает количество вызовов, так что количество рекурсивных вызовов, которое должно быть выполнено для вычисления n – го числа Фибоначчи, оказывается порядка 2N.

Объем вычислений резко нарастает с увеличением n. Вычисление только 20 – го числа Фибоначчи потребовало бы порядка 2N или около миллиона вызовов, вычисление 30 – го числа Фибоначчи потребовало бы порядка 3N или около миллиарда вызовов и так далее. В методах вычислений это называется экспоненциальной сложностью.

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

Любые задачи, которые можно решить рекурсивно, могут быть решены также и

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

Рис. 1.6. Механизм вызова функции в аппаратном стеке

1. В вершину стека помещается фрагмент нужного размера. В него входят следующие данные:

а) указатели фактических параметров вызова процедуры В;

б) пустые ячейки для локальных переменных, определенных в процедуре В;

в) адрес возврата, т.е. адрес команды в процедуре A, которую следует выполнить после того, как процедура B закончит свою работу.

Если B – функция, то во фрагмент стека для B помещается указатель ячейки во фрагменте стека для A, в которую надлежит поместить значение этой функции (адрес значения).

а) адрес возврата извлекается из вершины стека;

б) если B – функция, то ее значение запоминается в ячейке, предписанной указателем на адрес значения;

в) фрагмент стека процедуры B извлекается из стека, в вершину ставится фрагмент процедуры A;

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

Рис. 1.7. Дерево рекурсии при вычислении факториала числа 5

Рис. 1.8. вычисление 5 – ого числа Фибоначчи (Fb(5)).

-часто это наиболее легкий метод написания алгоритма для задач, которые можно решить с помощью рекурсии (число фибоначчи, факториал);

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

-целый ряд структур данных и многие объекты современных язы­ков программирования рекурсивны по самой своей сути (фрактальные объекты, иерар­хия классов в объектно – ориентированном программировании, древовидные регулярные структуры данных) и программы для работы с такими структурами выглядят намного более естественно в рекурсивной реализации;

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

Недостатки рекурсии заключаются в следующем:

-велика возможность войти в бесконечный цикл;

-при использовании некоторых формул слишком большие затраты памяти компьютера (к примеру, при вычислении числа Фибоначчи или факториалов, необходимо запоминать все значения чисел и вычислять одни и те же значения по многу раз);

-в случае, если вызываемых функций будет очень много, может произойти переполнение стека;

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

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

2. Программная реализация рекурсии

2.1. Примеры решения задач с помощью рекурсии

Задача 1. Числа Фибоначчи

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

Рассмотрим – вычисление N – ого по счёту числа Фибоначчи. Числа Фибоначчи составляют последовательность, очередной элемент которой вычисляется по двум предыдущим значениям:

Прикрепленные файлы: 1 файл

Рекурсивные алгориты.doc

Дерево

Еще один пример рекурсивной структуры, широко использующейся в программировании - структура дерева. Деревом называется совокупность связанных элементов - вершин дерева, включающая в себя один особый элемент - корень, при этом все остальные элементы образуют поддеревья. Наиболее широко используется структура бинарного дерева, все множество вершин которого делится (по отношению к корню) на два подмножества - два поддерева (левое и правое). Любая вершина бинарного дерева реализуется на связанной памяти элементом с двумя связями: с левым поддеревом и с правым.

Связь с левым потомком

Связь с правым потомком

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

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

TYPE Вершина = POINTER TO Элемент ;

PROCEDURE Смеш_Обход (K : Вершина);

Смеш_Обход (K^.LLink); (* Обход левого поддерева *)

WriteCard (K^.Info); (* Обработка корня *)

Смеш_Обход (K^.RLink); (* Обход правого поддерева *)

В традиционном программировании рекурсия часто рассматривается как некоторый заменитель итерации. Причем в качестве примеров рассматривается вычисление рекуррентных последовательностей, которые могут быть легко сформированы и обычными итераторами (циклами WHILE, REPEAT и т.п.). Природа рекурсии значительно глубже, чем механизм итерации, поэтому ее использование практически не имеет альтернатив в виде итераторов только тогда, когда решение задач проводится на рекурсивных структурах. Попробуйте написать процедуру Смеш-Обход без использования рекурсии, только на основе циклов и, если Вам это удастся, сравните ее с приведенным выше вариантом рекурсивной процедуры по наглядности, лаконичности, выразительности.

Преимущества и недостатки рекурсивного алгоритма

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

Преимущества рекурсии заключается в следующих аспектах:

Недостатки рекурсии заключаются в следующем:

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

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

Примеры решения задач с помощью рекурсии

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

Решение: На площадке (назовем ее А) находится пирамида, составленная из дисков уменьшающегося от основания к вершине размера.

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

• Перекладывать можно только по одному диску, взятому сверху пирамиды;
• Класть диск можно либо только на основание площадки, либо на диск большего размера;
• В качестве вспомогательной можно использовать площадку С.

Нетрудно решить эту задачу для двух дисков. Обозначая перемещения диска, например, с площадки А на В так: А→В. Напишем алгоритм для этого случая: А→С; А→В; С→В. Всего 3 хода.

Для трех дисков алгоритм длиннее: А→В; А→С; В→С; А→В; С→А; С→В; А→В. В этом случае уже требуется 7 ходов.

Подсчитать количество ходов (N) для k дисков можно по следующей рекуррентной формуле: N(k)=2xN(k-1)+1.

Например, N(10)=1023, N(20)=104857. А вот сколько перемещений нужно сделать ханойским монахам: N(64)=18446744073709551615.

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

Алгоритм решения задачи будет следующим:

1)Если N=0, то ничего не делать.

2)Если N>0, то переместить (N-1) диск на С через В;

● Переместить диск с А на В (А→В);

● Переместить (N-1) диск с С на В через А.

При выполнении пункта 2 последовательно будем иметь три состояния.

Описание алгоритма имеет явно рекурсивный характер.

А теперь построим программу на Паскале. В ней имеется рекурсивная процедура Hanoy, выполнение которой заканчивается только при N=0. При обращении к процедуре используются фактические имена площадок, заданные их номерами: 1, 2, 3. Поэтому на выходе цепочка перемещений будет описываться в таком виде: 1→2; 1→3; 2→3 и т.д.

Рекуррентные соотношения (формулы), сложности структурно-логического характера в действиях, составляющих конструктивную основу простейших рекурсивных алгоритмов. Рекурсивные определения, выполнение действий на рекурсивном спуске и рекурсивном возврате.

Рубрика	Программирование, компьютеры и кибернетика
Вид	реферат
Язык	русский
Дата добавления	12.12.2009
Размер файла	52,0 K

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

Лицей №1

“Рекурсивное программирование”

Подготовила Щербук О.Ф.,

Основой для разработки рекурсивных алгоритмов служат, так называемые, рекуррентные соотношения (формулы), устанавливающие зависимость между результатами какого-либо действия на n-м шаге от результата аналогичных действий, полученных на предыдущем n-1-м шаге. Следует сказать, что знакомство учащихся даже с простейшими рекурсивными алгоритмами вызывает ряд трудностей в усвоении. Они обусловлены прежде всего сложностями структурно-логического характера в действиях, составляющих конструктивную основу таких алгоритмов. Естественно, подобные сложности и малый ресурс времени не позволяет в процессе обучения специально уделять внимание вопросам разработки рекурсивных алгоритмов решения задач.

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

Данный материал рекомендуется учителям математики для факультативных занятий и спецкурсов по выбору в 9-11 классах, а также учащимся старших классов.

РЕКУРСИЯ

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

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

Способность функции обращаться к себе самой называется рекурсией.

Основой для разработки рекурсивных алгоритмов служат, так называемые, рекурентные соотношения (формулы), устанавливающие зависимость между результатами какого-либо действия на n-м шаге от результата аналогичных действий, полученных на предыдущем n-1-м шаге. Следует сказать, что знакомство учащихся даже с простейшими рекурсивными алгоритмами вызывает ряд трудностей в усвоении. Они обусловлены прежде всего сложностями структурно-логического характера в действиях, составляющих конструктивную основу таких алгоритмов. Естественно, подобные сложности и малый ресурс времени не позволяет в процессе обучения специально уделять внимание вопросам разработки рекурсивных алгоритмов решения задач.

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

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

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

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

program pr1;

procedure PopeAndDog1;

writeln(`У попа была собака, он ее любил');

writeln(`Она съела кусок мяса, он ее убил');

writeln(`похоронил и надпись написал:');

PopeAndDog1

PopeAndDog1

Однако если оператор вызова процедуры поставить перед выводом текста, как показано ниже,

Program PR2;

Procedure PopeAndDog2;

PopeAndDog2;

writeln(`У попа была собака, он ее любил');

writeln(`Она съела кусок мяса, он ее убил');

writeln(`похоронил и надпись написал:');

PopeAndDog2

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

!В действительности при исполнении на компьютере такой бесконечный вызов приводит к переполнению стека и возникновению ошибки времени исполнения.

! Рекурсивная процедура указывает, что нужно делать, а нерекурсивная больше акцентирует внимание на том, как нужно делать.

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

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

! Поэтому, воспользоваться значением переменной А i-го уровня рекурсии можно находясь только на i-гом уровне.

Дадим некоторые определения, имеющие отношения к рекурсии.

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

= Число рекурсивных вызовов в каждый конкретный момент времени, называется текущим уровнем рекурсии.

! Главное требование к рекурсивным процедурам заключается в том, что вызов рекурсивной процедуры должен выполнятся по условию, которое на каком-то уровне рекурсии станет ложным (т.к. бесконечной памяти не существует).

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

Структура рекурсивной процедуры может принимать 3 разные формы.

1. Форма с выполнением действий до рекурсивного вызова (с выполнением

действий на рекурсивном спуске).

Procedure Rec;

if условие then Rec;

2. Форма с выполнением действий после рекурсивного вызова (с выполнением действий на рекурсивном возврате).

Procedure Rec;

if условие then Rec;

3. Форма с выполнением действий как до, так и после рекурсивного вызова (с выполнением действий как на рекурсивном спуске, так и на рекурсивном возврате).

Procedure Rec;

if условие then Rec;

Procedure Rec;

if условие then begin

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

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

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

Алгоритм вычисления факториала. Введем дополнительно 2 параметра:

P-для выполнения операции умножения накапливаемого факториала на

очередной множитель (до рекурсивного вызова)

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

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

• структуры данных:
  • граф (в частности деревья и списки) можно рассматривать как совокупность отдельного узла и подграфа (меньшего графа);
  • строка состоит из первого символа и подстроки (меньшей строки);

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

  Содержание:

  Примеры рекурсивных алгоритмов

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

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

  Поиск элемента массива

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

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

  Двоичный поиск в массиве

  Вычисление чисел Фибоначчи

  Числа Фибоначчи определяются рекуррентным выражением, т.е. таким, что вычисление элемента которого выражается из предыдущих элементов: \(F_0 = 0, F_1 = 1, F_n = F_ + F_, n > 2\).

  Быстрая сортировка (quick sort)

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

  
  

  Блок-схема алгоритма быстрой сортировки

  Сортировка слиянием (merge sort)

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

  
  

  Блок схема сортировки слиянием

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

  Анализ рекурсивных алгоритмов

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

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

  Метод подстановки (итераций)

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

  Можно предположить, что \(T^_n = T^_ + k\times\mathcal(1)\), но тогда \(T^_n = T^_ + n\times\mathcal(1) = \mathcal(n)\).

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

  Метод математической индукции

  Позволяет доказать истинность некоторого утверждения (\(P_n\)), состоит из двух шагов:

  1. доказательство утверждения для одного или нескольких частных случаев \(P_0, P_1, …\);
  2. из истинности \(P_n\) (индуктивная гипотеза) и частных случаев выводится доказательство \(P_\).

  Докажем корректность предположения, сделанного при оценки трудоемкости функции поиска (\(T^_n = (n+1)\times\mathcal(1)\)):

  1. \(T^_ = 2\times\mathcal(1)\) верно из условия (можно подставить в исходную рекуррентную формулу);
  2. допустим истинность \(T^_n = (n+1)\times\mathcal(1)\);
  3. требуется доказать, что \(T^_ = ((n+1)+1)\times\mathcal(1) = (n+2)\times\mathcal(1)\);
     1. подставим \(n+1\) в рекуррентное соотношение: \(T^_ = \mathcal(1) + T^_n\);
     2. в правой части выражения возможно произвести замену на основании индуктивной гипотезы: \(T^_ = \mathcal(1) + (n+1)\times\mathcal(1) = (n+2)\times\mathcal(1)\);
     3. утверждение доказано.

     Часто, такое доказательство — достаточно трудоемкий процесс, но еще сложнее выявить закономерность используя метод подстановки. В связи с этим применяется, так называемый, общий метод [5].

     Общий (основной) метод решения рекуррентных соотношений

     \(T_n = a\cdot T(\frac)+f_n; a, b = const, a \geq 1, b > 1, f_n > 0, \forall n\).

     Уравнения такого вида получаются если исходная задача разделяется на a подзадач, каждая из которых обрабатывает \(\frac\) элементов. \(f_n\) — трудоемкость операций разбиения задачи на части и комбинирование решений. Помимо вида соотношения, общий метод накладывает ограничения на функцию \(f_n\), выделяя три случая:

     1. \(\exists \varepsilon > 0 : f_n = \mathcal(n^<\log_b a — \varepsilon>) \Rightarrow T_n = \Theta(n^<\log_b a>)\);
     2. \(f_n = \Theta(n^<\log_b a>) \Rightarrow T_n = \Theta(n^ <\log_b a>\cdot \log n)\);
     3. \(\exists \varepsilon > 0, c 1\).

     Для проведения анализа может использоваться метод подстановки или следующие рассуждения: каждый рекурсивный вызов уменьшает размерность входных данных на единицу, значит всего их будет n штук, каждый из которых имеет сложность \( \mathcal(1)\). Тогда \(T^_n = n \cdot \mathcal(1) = \mathcal(n)\).

     Анализ алгоритма сортировки слиянием

     Исходные данные разделяются на две части, обе из которых обрабатываются: \(a = 2, b = 2, n^ <\log_b a>= n\).

     При обработке списка, разделение может потребовать выполнения \(\Theta(n)\) операций, а для массива — выполняется за постоянное время (\(\Theta(1)\)). Однако, на соединение результатов в любом случае будет затрачено \(\Theta(n)\), поэтому \(f_n = n\).

     Используется второй случай теоремы: \(T^_n = \Theta(n^ <\log_b a>\cdot \log n) = \Theta(n \cdot \log n)\).

     Анализ трудоемкости быстрой сортировки

     В лучшем случае исходный массив разделяется на две части, каждая из которых содержит половину исходных данных. Разделение потребует выполнения n операций. Трудоемкость компоновки результата зависит от используемых структур данных — для массива \(\mathcal(n)\), для связного списка \(\mathcal(1)\). \(a = 2, b = 2, f_n = b\), значит сложность алгоритма будет такой же как у сортировки слиянием: \(T^_n = \mathcal(n \cdot \log n)\).

     Однако, в худшем случае в качестве опорного будет постоянно выбираться минимальный или максимальный элемент массива. Тогда \(b = 1\), а значит, мы опять не можем использовать основную теорему. Однако, мы знаем, что в этом случае будет выполнено n рекурсивных вызовов, каждый из которых выполняет разделение массива на части (\(\mathcal(n)\)) — значит сложность алгоритма \(T^_n = \mathcal(n^2)\).

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

     Хвостовая рекурсия и цикл

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

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

     Для реализации такого поведения используется стек (стек вызовов, call stack) — в него помещаются номер команды для возврата и информация о локальных переменных. Стек не является бесконечным, поэтому рекурсивные алгоритмы могут приводить к его переполнению, в любом случае на работу с ним может уходить значительная часть времени.

     В ряде случаев рекурсивную функцию достаточно легко заменить циклом, например, рассмотренные выше алгоритмы поиска и бинарного поиска [4]. В некоторых случаях требуется более творческий подход, но чаще всего такая замена оказывается возможной. Кроме того, существует особый вид рекурсии, когда рекурсивный вызов является последней операцией, выполняемой функцией. Очевидно, что в таком случае вызывающая функция не будет каким-либо образом изменять результат, а значит ей нет смысла возвращать управление. Такая рекурсия называется хвостовой — компиляторы автоматически заменяют ее циклом.

     Зачастую сделать рекурсию хвостовой помогает метод накапливающего параметра [7], который заключается в добавлении функции дополнительного аргумента-аккумулятора, в котором накапливается результат. Функция выполняет вычисления с аккумулятором до рекурсивного вызова. Хорошим примером использования такой техники служит функция вычисления факториала:
     \(fact_n = n \cdot fact(n-1) \\
     fact_3 = 3 \cdot fact_2 = 3 \cdot (2 \cdot fact_1) = 3\cdot (2 \cdot (1 \cdot fact_0)) = 6 \\
     fact_n = factTail_ \\
     \\
     factTail_ = factTail(n-1, accumulator \cdot n)\\
     factTail_ = factTail_ = factTail_ = factTail_ = 6
     \)

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

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

     Читайте также:

       
     • Реферат на тему князь святослав
       
     • Горный и металлургический надзор реферат
       
     • Базовые шаги аэробики реферат
       
     • Организация и проведение экспертизы технических систем реферат
       
     • Реферат договор с потребителем