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

ВВЕДЕНИЕ

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

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

Алгоритм - это строгая и четкая, конечная система правил, которая определяет последовательность действий над некоторыми объектами и после конечного числа шагов приводит к достижению поставленной цели.[2]

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

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

Задачи:

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

1. Рекурсия

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

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

Рекурсия в широком смысле – это определение объекта посредством ссылки на себя. Рекурсия в программировании – это пошаговое разбиение задачи на подзадачи, подобные исходной.[4]

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

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

Функция или процедура называется рекурсивной, если в своем теле она содержит обращение к самой себе с измененным набором параметров.[4]

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

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

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

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

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

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

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

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

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

procedure Rec;

begin

S;

if условие then

Rec;

end;

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

procedure Rec;

begin

if условие then

Rec;

S;

end;

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

procedure Rec;

begin

S1;

if условие then

Rec;

S2 ;

end;

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

Рассмотрим пример рекурсивной функции rever выводящею цифры переданного ей числа n в обратном порядке.

procedure rever (n: integer);

begin

write (n mod 10);

if (n div 10) <> 0 then

rever (n div 10)

end;

begin

rever (3096);

end.

Алгоритм работы функции:

1. На вход функции rever в качестве параметра n поступает число 3096.
2. Процедура rever выводит на экран остаток от деления на 10. Это число 6.
3. Переход на новую строку не происходит, т.к. используется write.
4. Проверяется условие того, что 3096 при деление нацело на 10 больше нуля.
5. Вызывается rever с фактическим параметром, равным 309.
6. Вторая запущенная процедура выводит на экран цифру 9 и запускает третью процедуру с параметром 30.
7. Третья процедура выводит 0 и вызывает четвертый rever с 3 в качестве параметра.
8. Четвертая процедура выводит 3 на экран и ничего больше не вызывает, т.к. условие (3 div 10) <> 0 ложно.
9. Четвертая процедура завершается и передает управление третьей.
10. Третья процедура завершается и передает управление второй.
11. Вторая процедура завершается и передает управление первой.
12. Первая процедура завершается и передает управление в основную ветку программы.

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

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

Возможна чуть более сложная схема: функция A вызывает функцию B, а та в свою очередь вызывает A. Это называется сложной рекурсией. Ниже представлен пример сложной рекурсии.

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;

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

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

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

На рисунке 1.1 приведен пример бинарного дерева.

Рисунок 1.1 - Бинарное дерево

В свою очередь деревья различных типов применяются:

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

На рисунке 1.2 представлен пример обхода дерева тремя различными структурами рекурсивной процедуры.

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

Рисунок 1.2 - Результат обхода дерева тремя различными структурами рекурсивной процедуры

Еще один пример рекурсии - это фракталы. Фракталами называют геометрические объекты, линии, поверхности, пространственные тела, имеющие сильно изрезанную форму и обладающие свойством самоподобия («fractus» - делить, ломать).

Ниже приведены примеры фракталов.

Рисунок 1.3 - Кривая коха

Рисунок 1.4 Дерево Пифагора

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

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

2. Итерации

2.1. Понятие итерационных алгоритмов

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

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

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

2.1.1. Цикл с известным числом повторений (for)

Если число повторений тела цикла заранее известно, то используется оператор цикла for, который также часто называют оператором цикла с параметром.

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

В зависимости от направления изменения параметра цикла (возрастание - to или убывание - downto) в языке Паскаль оператор цикла for может быть записан в одной из двух форм:

for параметр := нач_знач to кон_знач do

оператор;

или

for параметр := нач_знач downto кон_знач do

оператор;

Рисунок 2.1 - Блок-схема цикла for

Переменная-параметр цикла может принимать любой порядковый тип. При этом начальное и конечное значения должны иметь тип совместимый с типом переменной-параметром.

Рассмотрим работу цикла for.

Перед началом выполнения оператора цикла вычисляются начальное значение, присваиваемое переменной-параметру, и конечное значение. Затем, циклически выполняются следующие операции:

1. Сравнивается текущее значение параметра с конечным значением.
2. Если условие параметр <= кон_знач истинно, то выполняется тело цикла, в противном случае оператор for завершает работу и управление передается оператору, следующему за циклом.

2.1.2. Цикл с предусловием. Оператор while

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

Оператор цикла while в Паскаль имеет следующий формат записи: