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

Алгоритм, в состав которого входит итерационный цикл, называется итерационным алгоритмом. Итерационные алгоритмы используются при реализации итерационных численных методов. В итерационных алгоритмах необходимо обеспечить обязательное достижение условия выхода из цикла (сходимость итерационного процесса). В противном случае произойдет зацикливание алгоритма, т.е. не будет выполняться основное свойство алгоритма — результативность.Примером такого рода алгоритмов, могут служить алгоритмы и методы приближенного вычисления функций и решения различного рода уравнений.Задача вычисления суммы бесконечного ряда с заданной точностью - метод итерации.Задача вычисления определенных интегралов: метод прямоугольников, метод трапеций, метод Симпсона (парабол) [14].Рассмотрим задачу вычисления функции y=cos(x) с погрешностью Ɛ,используя разложение косинуса в рядНакопление суммы производим по рекуррентной формулеSn=Sn-1+tn(x)Текущий член ряда будем вычислять по формулеАлгоритм вычисления бесконечного ряда с заданной погрешностью eps:Начало|x|>epst:=-t*x*x/(2*n*(2*n-1)); S:=S+t; n:=n+1;x, epss=1 t=1 n=1даВывод результатаКонецнетВ общем, программа вычисления суммы имеет следующий вид:{Цель: вычисление суммы с заданной погрешностью по }{ итерационному алгоритму }{Переменные:x-аргумент функции,S-сумма }{ eps-погрешность вычисления суммы }{ n-переменная суммирования }{ t- слагаемое }V.СРАВНЕНИЕ РЕКУРСИИ И ИТЕРАЦИИ НА ПРИМЕРЕ ПРОГРАММ В СРЕДЕ PASCALВычисление факториалаНахождение факториала некоторого числа - несложный пример, иллюстрирующий применение методов рекурсии или итерации[1]. Рассмотрим пример нахождения факториала для некоторого числа n, применив оба способа:Черезиттерацию:Program p1;Var n,s,i: integer;begins:=1;writeln('n');readln(n);if n >= 0 thenBeginfor i:=1 to n doS:=S*i;writeln(s);endelsewriteln('ошибка');readln;end.Черезрекурсию:Program Factorial;var n: Integer;function Fac (n: Integer): Real;beginif n<0 thenwriteln (‘Ошибкавзадании N’)elseif n=0 thenFac:=1else Fac:=n*Fac(n-1)end {Fac};begin {main}ReadLn(n);WriteLn(‘n! = ’,Fac(n))End. {main}При использовании рекурсивной формыструктура алгоритма обычно выглядит более наглядной итерационной и выражается более компактным текстом программы, но,как правило, при выполнении медленнее и может вызвать переполнение стека (при каждом входе в программу её локальные переменные размещаются в организованной области памяти, называемой программным стеком). Особенно переполнение стека ощущается при работе с сопроцессором: если программа использует арифметический сопроцессор, результат любой вещественной функции возвращается через аппаратный стек сопроцессора, рассчитанный всего на 8 уровней. Если, например, попытаться заменить тип REAL функции FAC на EXTENDED, программа перестанет работать уже при N=8[2].Архитектура стека непосредственно поддерживает рекурсию, поскольку каждый вызов процедуры автоматически размещает новую копию локальных переменных. Например, при каждом рекурсивном вызове функции факториала требуется одно слово памяти для параметра и одно слово памяти для адреса возврата. То, что издержки на рекурсию больше, чем на итерацию, связано с дополнительными командами, затраченными на вход в процедуру и выход из неё. Некоторые компиляторы пытаются выполнить оптимизацию, называемую оптимизацией хвостовой рекурсии (tail-recursion) или оптимизацией последнего вызова (last-call). Если единственный рекурсивный вызов в процедуре – последний оператор процедуры, то можно автоматически перевести рекурсию в итерацию [14].ЗАКЛЮЧЕНИЕТермин алгоритмхарактеризуется как один из фундаментальных понятий не только математики. Работы по формализации этого понятия способствовали появлению такого нового научного направления, как теория алгоритмов.По итогам анализа и сравнения рекурсивных и итерационных алгоритмов можно сделать вывод: рекурсивный метод организации алгоритма обычно выглядит изящнее итерационного, но при выполнении, как правило, медленнее и может вызвать переполнение стека.Н.Вирт говорил, что “... понятие рекурсивных алгоритмов обычно объяснялось на неподходящих примерах, что приводилок широкому распространенному предубеждению против рекурсии в программировании”. Тот факт, что издержки на рекурсию больше, чем на итерацию, связан с дополнительными командами, которые затрачиваются на вход в процедуру и выход из неё. В том случае, если единственный рекурсивный вызов в процедуре – последний оператор процедуры, то можно автоматически перевести рекурсию в итерацию.Н.Вирт считает, что "...мощность рекурсии определяется тем, что этот метод дает возможность определить бесконечное множество объектов с помощью конечного высказывания". Удобство же итерации заключается в том, что алгоритм, по сути, остается линейным [13].По итогам разностороннего исследования рекурсивных и итерационных алгоритмов можно сделать ряд важных и, стоит отметить, особых выводов.Во-первых, рекурсивные (итерационные) алгоритмы - это универсальные средствадля решения различных алгоритмических проблем. Показано, что любая разрешимая задача такого рода имеет рекурсивное или итерационное решение, отличающееся изяществом и простотой для восприятия человеком.Во-вторых, рекурсивные методы частенько имеют более низкую асимптотическую сложность, чем эквивалентные им итерационные. То есть теоретически они быстрее.В-третьих, развитие современных программных средств сделало практическое использование рекурсии достаточно несложным делом, а новые концепции и технологии программирования преодолели проблему низкой эффективности рекурсивных программ, созданную необходимостью вызова большого количества подпроцедур.Что же выбрать в конечном итоге: рекурсивный метод или итерационный метод? Выбор будет зависеть от ситуации или конкретной задачи. В общем говоря,для реализации рекурсии требуются дополнительные расходы памяти, посколькупри этом используются стеки. Нов том случае, когда задача или применяемые данные определены рекурсивно, использование рекурсии часто приводит к более простому решению,и реализация структуры выглядит изящнее, чем при итерационном методе [11].СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫГлухов М.М. Математическая логика. – М., 1982.Дональд Кнут Искусство программирования, том 1. Основныеалгоритмы = The Art of Computer Programming, vol.1. Fundamental Algorithms. — 3-еизд. — М.: «Вильямс», 2006. — С. 720. — ISBN 0-201-89683-4Емельченков Е.П., Емельченков В.Е. Вычислимость. Введение в теорию алгоритмов. – М., 2000.Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. – М., 1983.Клейн М. Математика. Утрата неопределённости. – М.: Мир, 1987.Колмогоров А. Н. Теория информации и теория алгоритмов. — М.: Наука, 1987. — 304 с.Марков А. А., Нагорный Н. М. Теория алгорифмов, изд. 2. — М.: ФАЗИС, 1996.Мальцев А.И. Алгоритмы и рекурсивные функции. – М., 1965.Носов В.А. Основы теории алгоритмов и анализа их сложности. – М., 1992.Фалина И. Н. Элементы теории алгоритмов / И. Н. Фалина // Информатика. – 2004 г. – №3 (435). – 2-11Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1Трахтенброт Б.А. Сложность алгоритмов и вычислений: спецкурс для студентов НГУ. – Новосибирск, 1967.Трахтенброт Б.А. Алгоритмы и вычислительные автоматы. – М., 1974.Успенский В.А., Семёнов А.Л. Теория алгоритмов: основные открытия и приложения. – М., 1987.Фалина И. Н. Элементы теории алгоритмов / И. Н. Фалина // Информатика. – 2004 г. – №3 (435). – 2-11.Федер Е. Фракталы. – М.: Мир, 1991.