Решение задач с помощью рекурсии

Многие вычислительные задачи имеют весьма простую и изящную фор­мулировку, которая непосредственно переводится в рекурсивный код. В разделе 1 рассмотрен пример, про Ханойскую башню. В этом разделе мы расширим диапазон примеров и рассмотрим рекурсивное определение алгоритма бинарного поиска.

Бинарный поиск

При бинарном поиске берется некоторый ключ и просматривается упоря­доченный массив из n элементов на предмет совпадения с этим ключом. Функция возвращает индекс совпавшего с ключом элемента или –1 при отсутствии такового. Алгоритм бинарного поиска может быть описан рекурсивно.

Допустим, отсортированный список А характеризуется нижним граничным индексом low и верхним – high. Имея ключ, мы начинаем искать совпадение в середине списка (индекс mid).

mid = (low+high)/2 Сравнить A[mid] с ключом

Если совпадение произошло, мы имеем условие останова, что позволяет нам прекратить поиск и возвратить индекс mid.

Если совпадение не происходит, можно воспользоваться тем фактом, что список упорядочен, и ограничить диапазон поиска "нижним подсписком" (слева от mid) или "верхним подсписком" (справа от mid).

Бели ключ < A[mid], совпадение может произойти только в левой половине списка в диапазоне индексов от low до mid-1.

Бели ключ > A[mid], совпадение может произойти только в правой половине списка в диапазоне индексов от mid+1 до high.

Шаг рекурсии направляет бинарный поиск для продолжения в один из подсписков. Рекурсивный процесс просматривает все меньшие и меньшие списки. В конце концов поиск заканчивается неудачей, если подсписки ис­чезли. Это происходит тогда, когда верхний предел списка становится меньше чем нижний предел. Условие low>high — второе условие останова. В этом случае алгоритм возвращает -1.

Бинарный поиск (рекурсивная форма). В шаблонной версии бинарного поиска в качестве параметров используется массив элементов типа Т, значение ключа, а также верхний и нижний граничные индексы. Оператор IF обрабатывает два условия останова: 1) совпадение произошло; 2) ключевого значения нет в списке. В блоке ELSE оператора IF выполняется шаг рекурсии, который направляет дальнейший поиск в левый (ключ<А[mid]) или в правый подсписок (ключ>А[mid]). Тот же алгоритм применяется по принципу "разделяй и властвуй" к последовательности все меньших интервалов, пока не произойдет успех (совпадение) или неудача.

// рекурсивная версия бинарного поиска ключевого значения

//в упорядоченном массиве А

template <clasa T>

int BinSearch{t A[], int low, int high, Т key)

{

 int mid;                                                   J

 Т midvalue;                                                ;1

// условие останова:! ключ не найден

 if (low > high) return (-1);

// сравнить ключ с элементом в середине списка.

// если совпадения нет, разделить на подсписки.

// применить процедуру бинарного поиска к подходящему подсписку

 else

 {

mid = (low+high)/2;

midvalue = A[mid]; // условие останова: ключ найден

if (key == midvalue)

return mid; // ключ найден по индексу mid

// просматривать левый подсписок, если key < midvalue;

//в противном случае - правый подсписок

else if (key < midvalue)

// шаг рекурсии

return BinSearch(A, low, mid-1, key);

 else

// шаг рекурсии

return BinSearch(A, mid+1, high, key);

 }

}

Введение

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

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

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

а) 0 есть натуральное число,

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

2. Деревья:

а) 0 есть дерево (его называют "пустым деревом"),

б) если t1 и t2 – деревья, то построение, содержащее вершину с двумя ниже расположенными деревьями, опять же дерево.

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

а) 0! = 1,

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

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

P=P[S,P].                                            (3.1)

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

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

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

Р = IF В THEN P [S, P] END,

P = Р [S, IF В THEN P END].

Основной способ доказательства конечности некоторого повторяющегося процесса таков:

1. Определяется функция f(х) (х – множество переменных) такая, что из f(х) < 0 следует истинность условия окончания цикла (с предусловием или постусловием).

2. Доказывается, что при каждом прохождении цикла f(x) уменьшается.

Аналогично доказывается и окончание рекурсии – noказывается, что Р уменьшает f(x), такую, что из f(x) £ 0 следует –В. В частности, наиболее надежный способ обеспечить окончание процедуры – ввести в нее некоторый параметр (значение), назовем его n, и при рекурсивном обращении к Р в качестве пара задавать n – 1. Если в этом случае в качестве В используется n>0, то окончание гарантировано. Это опять же выражается двумя схемами:

Р(п) = IF п > О THEN P[S, Р (n – 1)] END,

P(р) = Р [S, IF п > О THEN Р ( п – 1) END].

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

 

---

Дата добавления: 2018-10-26; просмотров: 210; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!