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

Поделим отрезок  пополам. Получим точку  и два отрезка .

• Если , то корень  найден ().
• Если нет, то из двух полученных отрезков  и  надо выбрать один  такой, что , то есть
  • , если  или
  • , если .

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

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

Начало

e:=0.001

c:=(a+b)/2

F(a)*F(c)<=0

Да

b:=c

a:=c

abs(b-a)<e ;

Да

x:=(a+b)/2

x

Конец

Ввод а,b

Рисунок 3-Блок-схема метода дихотомии

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

2.1. Определение рекурсии

Рекурсия – определение некоторого понятия через самое себя.[6, 115]

С рекурсией мы постоянно сталкиваемся в повседневной жизни. Иллюстрации примеров рекурсии вокруг нас приведены на рисунках 5- 10.

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

Рисунок 4 - Что появилось раньше, яйцо или цыпленок?

Рекурсия в поэзии, музыке и литературе применяется часто. Повторяющие фразы в стихах и мелодии, которые в определенный момент воспроизведения одинакового фрагмента интерпретируются человеком по разному. Самый распространенный пример рекурсии в литературе приведен на рисунке 5^[3].

Рисунок 5 - Рекурсия в литературе

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

Рисунок 6 - Рекурсивная математика

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

Рисунок 7 - Рекурсия в древности

Треугольник Серпинского составлен по геометрическим закономерностям: внутри каждого треугольника чертится перевернутый такой же треугольник меньшего размера. Такой процесс можно продолжать до бесконечности. На рисунке 8 приведен пример треугольника Серпинского.

Рисунок 8 - Треугольник Серпинского-геометрические закономерности

Фракталы, как и треугольник Серпинского имеют различные закономерности, но состоят из кругов или фигур, полученных при использовании кривых Безье. Рисунок 9 показывает различные формы фракталов.

Рисунок 9 - Фракталы

Рекурсия является средством программирования, при котором процедура или функция прямо или косвенно вызывает сама себя. При прямой рекурсии в описании функции или процедуры используется обращение к ней же самой, но с другим набором параметров. При косвенной рекурсии подпрограмма вызывает какую-либо другую подпрограмму, в описании которой содержится вызов исходной подпрограммы (например, процедура V вызывает процедуру X, а процедура X вызывает процедуру V). Косвенный вызов может быть организован c использованием нескольких подпрограмм.

В книге^[4] Вьюковой Н.И. приведена интересная иллюстрация, показывающая разницу между рекурсивным и итерационным алгоритмом. Приведем её с небольшими изменениями.

Пусть в эксперименте "Позвони другу" участвуют n человек, причем k-й (0<k<n) знает только телефон следующего (k+1)-го человека, а n-й знает только то, что он последний. И возникла ситуация, когда некто, знающий телефон первого человека, решил выяснить, чему равно n. Если он будет действовать не рекурсивно, и на бумаге будет вести подсчеты. Сначала он напишет 0 и позвонит первому. Затем он прибавит 1 и спросит у первого телефон второго человека, повесит трубку, наберет номер второго, прибавит ещё 1 и получит 2, далее - спросит телефон третьего и т.д., пока не дойдет до человека, который сообщит, что он последний. Подсчитав сумму единиц, получит ответ.

Если же упомянутый некто захочет действовать рекурсивно, то он позвонит первому и прикажет: "Алло, не вешайте трубку! Сообщите мне, сколько вас". Поскольку первый не знает, сколько их, а трубку вешать нельзя, то ему предстоит взять трубку мобильного телефона и позвонить второму на домашний, сказав те же слова. Здесь рекурсия пошла вниз. Эти же действия повторит второй и далее все остальные по цепочке. Наконец последний сообщит предпоследнему, что он один. Рекурсия достигла точки выхода и пошла вверх. Предпоследний передаст предпредпоследнему что их двое, прибавив 1, предпредпоследний скажет что их трое, прибавив 1 к двойке и т.д. И, в конечном счете, первый услышит число, к которому нужно прибавить 1 и получится ответ.

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

Приведем пример программной реализации процедуры прямой рекурсии, написанной на языке Паскаль.

procedure Rec(х: intеger);

bеgin

if х>0 thеn

Rec (х-1);

writеln(х);

еnd;

Данная процедура в виде блок-схемы приведена на рисунке 10. Она вызывается в программе Rec(3).

Рисунок 10 - Пошаговая блок-схема работы процедуры

Спуск "вниз" осуществляется до х=0 и по итогам происходит подъём "вверх" до печати числа 3.

Иллюстрация работы данной процедуры приведена на рисунке 11.

Рисунок 11 - Визуальный образ работы процедуры

Приведем пример сложной рекурсии.

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

procedure A(n: longint); {Опережающее описание первой процедуры}

prоcеdure B(n: longint); {Опережающее описание второй процедуры}

prоcеdure A(n: longint); {Описание блока процедуры A}

begin

writeln('Из процедуры А ',n);

B(n-1);

end;

prоcеdure B(n: longint); {Описание блока процедуры B}

begin

writeln('Из процедуры В ',n);

if n<10 then

A(n+2);

end;

begin

A(3);

end.

Приведенный алгоритм схематично изображен на рисунке 12.

Рисунок 12 -Работа сложной рекурсии

После тестирования программы, вызова процедуры А(3) имеем следующую последовательность чисел:

Из процедуры В 3

Из процедуры А 2

Из процедуры В 4

Из процедуры А 3

Из процедуры В 5

Из процедуры А 4

Из процедуры В 6

Из процедуры А 5

Из процедуры В 7

Из процедуры А 6

Из процедуры В 8

Из процедуры А 7

Из процедуры В 9

Из процедуры А 8

Из процедуры В 10

Из процедуры А 9

Из процедуры В 11

Из процедуры А 10

Ответ: 10.

2.2. Механизм рекурсивных выводов

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

Вот текст стихотворения:

«10 негритят пошли купаться в море,

10 негритят резвились на просторе,

Один из них пропал и вот вам результат:

9 негритят пошли купаться в море,

9 негритят резвились на просторе,

Один из них пропал – и вот вам результат:

…

1 (из) негритят пошли(ел) купаться в море,

1 (из) негритят резвились(ся)на просторе,

Один из них пропал – и вот вам результат:

Нет больше негритят!»

Программная реализация на Паскале представлена на рисунке 13. Механизм вывода виден в окне вывода оболочки Паскаля. Механизм работы процедуры приведен на рисунке 14.

Рисунок 13 - Иллюстрация работы программы

Для вызова три раза процедуры необходимо в теле программы вызвать процедуру от трех (Negr(3))^[5].

Рисунок 14 - Механизм работы рекурсивной процедуры

Из примера можно сделать выводы:

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

2. Рекурсия не может иметь слишком много вызовов саму себя или вложений. Работа рекурсии зависит от объема стековой памяти компьютера. Объем стековой памяти зависит от архитектуры компьютера.

Рекурсивные определения представляют собой мощный аппарат в математике.

Например:

1. Натуральные числа:

а) 1 есть натуральное число;

б) число, следующее за натуральным, - есть натуральное число.

2. Деревья:

а) 0 есть дерево ("пустое дерево");

б) если А1 и А2 - деревья, то построение, содержащее вершину с двумя ниже расположенными деревьями, опять дерево.

3. Функция n! "факториал" (для неотрицательных целых чисел):

а) 0!=1;

б) n>0: n!=n·(n-1)!

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

N! = 1 * 2 * 3 * … * (N-1) * N (1)

Факториал представляет собой произведение натуральных чисел от 1 до N включительно. Запишем формулу (1) в виде рекурсии.

N! = N * (N-1)! (2)

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

если N>0, то N! = N * (N-1)! иначе функция равна 1.

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

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

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

Рисунок 15 - Вычисление чисел Фибоначчи

Аналогично числам Фибоначчи вычисляется НОД двух чисел. На рисунке 16 приведены алгоритмы рекурсивного и итерационного способов нахождения НОД. Итерационный способ длинее в написании, рекурсивный способ более понятен, т.к. визуально написана математическая формула.

Рисунок 16 - Определение НОД числа

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

Рисунок 17 - Вычисление Биноминальных коэффициентов

Рекурсия имеет много недостатков. Повторный запуск рекурсивного механизма вызовов функции приводит к росту накладных расходов: к нарастающим затратам процессорного времени или требуемого объема памяти. Каждый рекурсивный вызов приводит к созданию новой копии функции (в самом деле, копируются только переменные данной функции); для этого может потребоваться значительная память. Итерации обычно не связаны с функциями, так что в них отсутствуют накладные расходы на повторные вызовы функции и дополнительные затраты памяти. Тогда для чего же применять рекурсию?