Рекурсия и Итерация

Рекурсия

Объект называется рекурсивным если он содержит сам себя или определен при помощи самого себя. Пример – определение факториала. Мощность рекурсии связана с тем, что она позволяет определить бесконечное множество объектов с помощью конечного высказывания. Точно также бесконечные вычисления можно описать с помощью конечной рекурсивной программы, даже если эта программа не содержит явных циклов. Рекурсивные алгоритмы часто используются в тех случаях когда решаемая задача или вычисляемая функция или обрабатываемая структура данных определены с помощью рекурсии. Необходимое и достаточное средство для рекурсивного представления программ – это описание подпрограмм, т. к. оно позволяет присваивать какому-либо оператору имя с помощь которого можно вызвать этот оператор. Если процедура содержит явное обращение самой к себе, то он называется пряморекурсивной. Если про-ра Р содержит обращение к про-ре А, которая содержит (прямо или косвенно) обращение к про-ре Р, то пр-ра Р называется косвенно рекурсивной. Следо-но использование рекурсии не всегда видно из текста программы. ри выполнении правильно организованной рекурсивной подпрограммы осуществляется многократный переход от некоторого текущего уровня организации алгоритма к нижнему уровню последовательно до тех пор, пока, наконец, не будет получено тривиальное решение поставленной задачи. В примере решение при N = 0 тривиально и используется для остановки рекурсии.

Function Fac(n: Integer): Real;

begin

if n < 0 then

WriteLn ('n не может быть <0!!!')

Else

if n = 0 then

Fac:= 1

else

Fac:= n * Fac(n-l)

end; {Fac}

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

Procedure A (i: Byte);

begin

.......

В (i);

.......

end;

Procedure В (j: Byte);

.......

begin

.......

A(j);

.......

end;

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

- текущие значения параметров, передаваемых через значение;

- местонахождение (адреса) параметров переменных;

- адрес возврата, т.е. адрес оператора, который следует за оператором вызова.

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

Рекурсию необходимо использовать в случаях, когда написание нерекурсивных алгоритмов является очень сложным: перевод программ на языке ТУРБО ПАСКАЛЬ на язык компьютера, машинная графика, распознавание образов и т.д.

Рекурсия и Итерация

Итерация (Пример):

Вычислить факториал: I: =0; F: =1; While I<n do Begin I: =I+1; F: = I+F; End;

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

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

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

Ранее нами рассматривались рекурсивные алгоритмы. Но во многих случаях та же задача может быть решена и нерекурсивными методами. Рекурсивный подход к вычислению функций, заданных рекуррентными соотношениями: f(n) = j(f(n-1), n); f(0) = а.

Эту последовательность можно обратить: f(0) = а; f(1) = j(f(0),1); f(2) = j(f(1),2);... f(1) = j(f(n-1),n),

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

y:= a;

for i:= 1 to n do

у:= j(y, i)

называется итерацией.

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

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

Линейный поиск

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

Var a:array [0..n-1] of item

Обычно тип item описывает запись с некоторым полем выполняющим роль ключа. Задача заключается в том, что необходимо найти элемент ключ которого = заданному аргументу поиска Х, т. к. нас интересует сам процесс поиска, то для простоты будем считать, что тип item включает только ключ. Если нет никакой информации о разыскиваемых данных, то очевидный подход – простой последовательный просмотр массива с увеличением шаг за шагом той его части где желаемый еле-т не обнаружен. Условия окончания поиска – 1) эле-т найден ai=x 2) если все просмотрено а совпадений нет.

I:=0; While (I<n) and (a[I]<>x do I:=I+1;

Замечание: порядок эл-тов в лог. Выражении имеет существенное значение.

Инвариант цикла – т. е. условие выполняется перед каждым увеличением индекса. Записывается

(0<= I <N)&(для любого K: 0<=k< I: ak не =x)

Отсюда можно вывести условие окончания

((I=n) or (ai=x))& (для любого K: 0<=k< I: ak не =x)

Это условие указывает на желаемый результат, а также указывает, что если желаемый эл-т найден, то он найден с мин. индексом. Равенство I=N означает, что совпадений не было. На каждом шаге требуется вычисление индекса и лог. выражение. Единственная возможность ускорить поиск - попытаться упростить лог. выражение, т. к. оно состоит из 2-х членов, т. е. надо сформулировать простое условие эквивалентное исходному. Это можно зделать если мы гарантируем, что совпадение всегда произойдет. Для этого достаточно поместить в конец массива дополнительный эле-т со значение Х – барьер. Он будет охранять от перехода за границы барьера.

Var a:array [0..n] of item

Алгоритм

A[n]:=x; I:=0;

While a[I]<>x do I:=I+1;

Не нашли, что искали? Воспользуйтесь поиском: