Содержание:

ВВЕДЕНИЕ

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

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

Алгоритм - это строгая и четкая, конечная система правил, которая определяет последовательность действий над некоторыми объектами и после конечного числа шагов приводит к достижению поставленной цели.[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 в Паскаль имеет следующий формат записи:

while выражение do

оператор;

Рисунок 2.2 - Блок-схема цикла while

Рассмотрим работу оператора цикла while.

1. Вычисляется значение выражения (т. е. условие, стоящее после ключевого слова while), которое должно быть логическим выражением.
2. Если результат вычисления выражения равен true (истина), то выполняется тело цикла (простой или составной оператор, расположенный после ключевого слова do). Затем, снова проверяется условие и т. д.
3. Если результат равен false (ложь), то происходит выход из цикла и управление передается на первый оператор, следующий за циклом.

2.1.3. Цикл с постусловием. Оператор repeat

Цикл while может не выполниться ни разу, если логическое выражение в заголовке сразу вернуло false. Однако такая ситуация не всегда может быть приемлемой. Бывает, что тело цикла должно выполниться хотя бы один раз, не зависимо оттого, что вернет логическое выражение. В таком случае используется цикл repeat – цикл с постусловием.

В цикле repeat логическое выражение стоит после тела цикла. Причем, в отличие от цикла while, здесь всё наоборот: в случае true происходит выход из цикла, в случае false – его повторение.

Оператор repeat имеет следующий формат записи:

repeat

тело цикла

until выражение

Рисунок 2.3 - Блок-схема цикла repeat

Работа оператора цикла repeat происходит следующим образом:

1. Выполняется последовательность операторов, заключенная между ключевыми словами repeat и until (поэтому тело цикла выполнится хотя бы один раз).
2. Производится проверка продолжения цикла: если значение выражения, записанного после ключевого слова until, равно false (ложь), то тело цикла выполняется снова.
3. Если значение выражения равно true (истина), то происходит выход из цикла.

Чтобы рассмотренные выше операторы цикла выполнялись конечное число раз, при построении цикла необходимо предусмотреть, чтобы среди выполняемых операторов обязательно был оператор, который изменял бы значение условия, таким образом, чтобы когда-нибудь значение условия принимало бы false(для оператора while-do)или true(для оператора repeat- until). В противном случае цикл будет повторяться бесконечное число раз и программа "зациклится".[2]

2.1.4. Вложенные циклы

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

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

var i, j: integer;

begin

for i := 1 to 9 do // цикл по строкам таблицы, счетчик как левый множитель

begin

for j := 1 to 9 do // выводим равенства очередной строки, счётчик как правый множитель

write(i, '*', j, '=', i*j:2, #9);

writeln(); // переносим строку

end;

end.

Пример работы программы представлен на рисунке 2.4.

Рисунок 2.4 - Результат работы программы вывода таблицы умножения

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

Огромное количество различного рода задач решается с применением алгоритмов циклической структуры:

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

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

Данная задача решается с использованием вложенных циклов.

Алгоритм:

1) Последовательно бежим по массиву и сравниваем два соседних элемента, если порядок не верный то меняем их местами.

2) Повторять проходы на один меньше, чем кол-во элементов в массиве или пока не окажеться, что за проход не произведено ни одной замены.

Просмотрим алгоритм на примере:

Отсортируем массив: 524613 где каждая цифра это элемент массива.

Начало цикла, в массиве 524613 нет отсортированных чисел:

1) Первый проход:

524613->254613->245613->245613->245163->245136

Мы бежим по массиву и меняем элементы местами, которые находятся рядом друг с другом и не соответствуют порядку сортировки. Первый шаг это цифры 5 и 2, второй 5 и 4, третий 6 и 5, четвёртый 6 и 1, пятый 6 и 3.

2) Второй проход.

245136->245136->245136->241536->241356->241356

3) Третий проход.

241356->241356->214356->213456->213456->213456

4) Четвёртый проход.

213456->123456->123456->123456->123456->123456

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

5) Пятый проход финальный.

123456->123456->123456->123456->123456->123456

Сразу удовлетворилось два условия выхода, не было произведено ни одного изменения и проход по счёту равен количеству элементов в массиве минус 1.

Ниже представлена код процедуры реализующей данный алгоритм на языке программирования Pascal.

Procedure Bubble_Sort (var a : array of real; LengthArray :Integer);

var i,i2:integer;

begin

for i:=1 to LengthArray-1 do

for i2:=1 to LengthArray-2 do

if a[i2+1]<a[i2] then

Swap(a[i2],a[i2+1]);

end;

Рассмотрим еще одну задачу решаемую с применением итерационных алгоритмов - вычисление определенного интеграла. Рассмотрим на примере метода трапеций. Блок-схема данного метода приведена на рисунке 2.5.

Рисунок 2.5 - Блок-схема алгоритма метода трапеций

Ниже приведен код программы на языке паскаль реализующий данный алгоритм.

function f(x: real): real;

begin

f := sqr(x) - x - 1;

end;

var

a, b, S, h, integ: real;

i, n: integer;

begin

readln(a, b, n);

h := (b - a) / n;

for i := 1 to n - 1 do

S := s + f(a + h * i);

integ := h * ((f(a) + f(b)) / 2 + S);

writeln('S=', integ);

end.

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

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

3.1. Вычисление N-го числа Фибоначчи

Числа Фибоначчи — элементы числовой последовательности в которой первые два числа равны либо 1 и 1, либо 0 и 1, а каждое последующее число равно сумме двух предыдущих чисел[3].

Ниже приведена программа на языке программирования Pascal вычисляющая n-е число Фибоначчи.

program Fibonacci;

function Recursion (n: word): longint;

begin

if (n = 0) or (n = 1) then

Recursion:= 1

else Recursion := Recursion(n - 1) + Recursion(n - 2); {рекурсивный вызов}

end;

function Iteration(n: word): longint;

var

x, y, t: longint;

k: integer;

begin

x := 1;

y := 1;

for k := 2 to n do

begin

t := y;

y := x + y;

x := t;

end;

Iteration := y; {итерация}

end;

Var

n:integer = 20;

begin

writeln('Рекурсивный алгоритм : F(', n, ')= ', Recursion(n));

writeln('Итерационный алгоритм : F(', n, ')= ', Iteration(n));

end.

Исходя из алгоритма можно сделать следующие выводы:

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

3.2. Вычисление факториала

Слово факториал произошло от латинского factor (делающий, производящий). Факториал числа — это произведение натуральных чисел от 1 до самого числа (включая данное число).

Ниже приставлен код вычисления факториала на языке программирования Pascal.

function FacRecursive(n: Integer): Real;

begin

if n = 0 then

FacRecursive := 1

else FacRecursive := n * FacRecursive(n - 1)

end;

function FacIteration(n: Integer): Real;

var

s, i: integer;

begin

s := 1;

for i := 1 to n do

S := S * i;

FacIteration:=s;

end;

var

n: integer;

begin

write('n: ');

readln(n);

writeln('Итерация: ',FacIteration(n));

writeln('Рекурсия: ',FacRecursive(n));

end.

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

Список использованных источников

1. Алексеев Е. Р., Чеснокова О. В., Кучер Т. В. Free Pascal и Lazarus: Учебник по программированию / Е. Р. Алексеев, О. В. Чеснокова, Т. В. Кучер — М. : ALT Linux ; Издательский дом ДМК-пресс, 2010. — 440 с. : ил. — (Библиотека ALT Linux).
2. Мансуров К.Т. Основы программирования в среде Lazarus, 2010. – 772 с.: ил.
3. НОУ Интуит [Электронный ресурс], URL: https://www.intuit.ru/studies/courses/648/504/lecture/11458 (дата обращения 13.04.2020)
4. НОУ Интуит [Электронный ресурс], URL: https://www.intuit.ru/studies/courses/648/504/lecture/11423 (дата обращения 13.04.2020)