Программирование рекурсивных алгоритмов

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

В математике рекурсией называется способ описания функций или процессов через самих себя.

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

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

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

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

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.

Пример 3.1.

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 является характерным примером прямой рекурсии. Косвенная рекурсия возникает тогда, когда один блок вызывает второй, а второй, в свою очередь, первый.

Опережающие объявления

В Турбо Паскале существует правило: перед употреблением любой элемент программы должен быть объявлен. Если строго следовать этому правилу, то реализовать косвенную рекурсию в Турбо Паскале невозможно. Для того чтобы это все же можно было сделать, в язык введены так называемые опережающие объявления (описания). Для задания опережающих объявлений используется директива компилятора Forward, которая позволяет объявить имя подпрограммы, отложив при этом ее окончательное определение, т.е. объявление проводится в два этапа. На первом задаются имя подпро­граммы и параметры, за которыми следует атрибут Forward. Позднее появляется полное определение подпрограммы, но в ее заголовок не включается список параметров. Ниже приведен фрагмент программы, являющийся примером задания косвенной рекурсии.

Пример 3.2. Процедура First вызывает процедуру Second, а та, в свою очередь, процедуру First.

Procedure First(A, В: Integer); Forward; {Заголовок первой процедуры}

Procedure Second(C: Real); {Вторая процедура}

Var X, Y: Integer;

begin

...

First(X, Y);

...

end;

Procedure First; {Снова краткий вызов первой процедуры}

Var Z: Real;

begin

Second(Z);

end;

Директиву Forward можно использовать не только в рекурсивных подпрограммах, но и для более удобного размещения подпрограмм: сначала описать все заголовки, а затем - сами подпрограммы. Эту директиву не следует использовать в модулях для подпрограмм, объявленных в интерфейсе модуля. Подробнее об этом см. работы [4,5].