Рекурсивная функция

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

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

Функция называется рекурсивной, если в её определении содержится вызов этой же функции. Различают простую рекурсию, когда текст программы функции F напрямую содержит вызов F, и косвенную рекурсию, когда F обращается к иным функциям, которые содержат вызов F. Поэтому, по тексту программы рекурсивность не всегда явно определима. Знание механизмов реализации рекурсии помогает эффективно её использовать. Что происходит, когда функция F выполняет рекурсивный вызов? Прежде всего, запоминается текущее состояние программы, необходимое для продолжения вычислений, когда управление снова вернется к ней. Затем F с новыми значениями аргументов начинает выполняться заново как бы с новым экземпляром программы. При следующем рекурсивном вызове F всё повторяется и т.д. до тех пор, пока очередной вызов F не приводит к какому-либо тривиальному случаю, разрешаемому без рекурсивных вызовов. Далее, в порядке, обратном тому, в котором запоминалась серия вызовов, производятся возвраты управления. В практических приложениях важно убедиться, что максимальная глубина рекурсивных вызовов не только конечна, но и достаточно мала. В противном случае не избежать переполнения стека - специально организованного участка памяти, где запоминаются отдельные состояния программы-функции.

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

1. параметризация,

2. выделение базы и возможных правил её модификации,

3. декомпозиция

4. проведение отложенных вычислений.

Первые три из них называют рекурсивной триадой. Остановимся на указанных этапах подробнее.

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

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

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

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

Напишите рекурсивный алгоритм вычисления наибольшего общего делителя (НОД) двух целых чисел.

Программирование с использованием рекурсии.

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

Function Factorial (N: Integer): Integer;

Begin

if N = 1 Then Factorial := 1

Else Factorial := N*Factorial(N -1)

End;

Здесь Factorial(N) определяется через значение Factorial(N-1), которое определяется через Factorial(N-2), и т.д. до сведения к значению Factorial(0), которое определено явно и равно 1. Любое рекурсивное описание должно содержать явное определение для некоторых значений аргумента (или аргументов), так как иначе процесс сведения оказался бы бесконечным. Таким образом при рекурсивном описании необходимо наличие базовой части описания, которая обеспечивала бы завершение рекурсивных вызовов функции (процедуры).

Рекурсивное обращение можно рассмотреть на примере вычисления определенного двойного интеграла по формуле трапеций. Точность этого приближения тем выше, чем больше число участков разбиения n. Увеличивая число n, можно достигнуть заданной точности. Если, допустим, функция TRAP вычисляет интеграл по методу трапеций при заданном числе интервалов N и А, В - пределы интегрирования, а FN - функция вычисления подынтегрального выражения, вычисление двойного интеграла можно осуществить с помощью следующего рекурсивного обращения к функции TRAP: J := TRAP (N1, A1, B1, TRAP (N2, A2, B2, FN));

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

Пример.

Function HighFactor(N1 ,N2:lnteger):lnteger;

Var P: Integer;

Begin

lf N1 > N2 Then P:=HighFactor(N1,N2)

Else

If N2<=0 Then p:= N1 {нерекурсивное решение}

Else P:=HighFactor(N2,N1 Mod N2);

HighFactor := P

End;

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

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

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

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

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