2. Рекурсия

«Итерация свойственна людям, рекурсия - богам...»

Процедура или функция может обращаться к самой себе. Такой вызов называется рекурсией (от латинского recursio – возвращение).

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

Основной метод построения рекурсивных алгоритмов – это метод декомпозиции.

• Идея метода состоит в разделении задачи на части меньшей размерности, получение решения для полученных частей и объединение решений.

Рассмотрим функцию факториала n!. Как правило, ее определяют как произведение первых n чисел:

n! = 1∙2∙3…∙n.

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

f := 1;

For i := 1 To n Do f := f * i;

С другой стороны ее можно определить рекурсивно следующим образом:

0! = 1,

n! = n(n-1)!, если n>0,

или в виде функции :

F (0) = 1, (1)

F (n) = n·F(n-1), если n>0. (2) рекуррентное соотношение

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

• (1) – нерекурсивно определенное начальное значение функции. Для каждой рекурсивной функции нужно хотя бы одно начальное значение, в противном случае ее нельзя вычислить в явном виде.

Function F ( i :Integer): LongInt; {вычисление факториала}

Begin

If i = 1 Then F := 1

Else F := i*F ( i – 1 );

End;

Вызов: ….. Ввод n; WriteLn(‘ n!= ‘, Fact(n)); …….

Аналогично числа Фибоначчи определяются следующей последовательностью целых чисел: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,… Эти числа можно получить исходя из рекуррентного соотношения:

F (n) = F ( n - 1 ) + F ( n - 2), F (0) = 0, F (1) = 1.

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

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

;

Function F( i :Integer): Integer; {вычисление чисел Фибоначчи}

Begin

Case i Of

0..1: F := i;

Else F := F ( i – 1) + F ( i – 2 );

End;

End;

Вызов: ….. Ввод n; WriteLn(‘ n!= ‘, F(n)); …….

Организовать вычисления по рекуррентным формулам можно и без использования рекурсии. Однако при этом встает вопрос о качестве программы и доказательстве ее эквивалентности начальным формулам. Использование рекурсии позволяет легко (почти дословно) запрограммировать вычисления по рекуррентным формулам.

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

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