Рекурсивная триада

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

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

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

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

Алгоритм называется рекурсивным, если в его определении содержится прямой или косвенный вызов этого же алгоритма. Вычисления, проводимые с помощью рекурсивных алгоритмов (процедур, функций) называют рекурсивными. Различают два основных вида рекурсии: прямая и косвенная. Под прямой рекурсией понимается непосредственный вызов алгоритма (функции, процедуры) F из текста самого алгоритма F. При косвенной рекурсии мы имеем циклическую последовательность вызовов нескольких алгоритмов F ₁, F ₂, …, F_k (функций, процедур) друг друга: F ₁ вызывает F ₂, F ₂ вызывает F ₃, …, F_k вызывает F ₁ (k >1).

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

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

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

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

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

Дата добавления: 2014-01-07