Сущность рекурсии

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

 

Рекурсия — это такой способ организации вспомогательного алгоритма (подпрограммы), при котором эта подпрограмма (процедура или функция) в ходе выполнения ее операторов обращается сама к себе.

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

 

В программировании рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная рекурсия), например, функция A вызывает функцию B, а функция B — функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.

 

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

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

 

Пример рекурсивной процедуры:

procedure Rec(a: integer);

begin

if a>0 then

Rec(a-1);

writeln(a);

end;

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

Рис. 1. Блок схема работы рекурсивной процедуры.

 

Процедура Rec вызывается с параметром a = 3. В ней содержится вызов процедуры Rec с параметром a = 2. Предыдущий вызов еще не завершился, поэтому можете представить себе, что создается еще одна процедура и до окончания ее работы первая свою работу не заканчивает. Процесс вызова заканчивается, когда параметр a = 0. В этот момент одновременно выполняются 4 экземпляра процедуры. Количество одновременно выполняемых процедур называют глубиной рекурсии.

Четвертая вызванная процедура (Rec(0)) напечатает число 0 и закончит свою работу. После этого управление возвращается к процедуре, которая ее вызвала (Rec(1)) и печатается число 1. И так далее пока не завершатся все процедуры. Результатом исходного вызова будет печать четырех чисел: 0, 1, 2, 3.

Еще один визуальный образ происходящего представлен на рис. 2.

Рис. 2. Выполнение процедуры Rec с параметром 3 состоит из выполнения процедуры Rec с параметром 2 и печати числа 3. В свою очередь выполнение процедуры Rec с параметром 2 состоит из выполнения процедуры Rec с параметром 1 и печати числа 2. И т. д.

 

В качестве самостоятельного упражнения подумайте, что получится при вызове Rec(4). Также подумайте, что получится при вызове описанной ниже процедуры Rec2(4), где операторы поменялись местами.

procedure Rec2(a: integer);

begin

writeln(a);

if a>0 then

Rec2(a-1);

end;

Ответ: 4 3 2 1 0

 

1. Обратите внимание, что в приведенных примерах рекурсивный вызов стоит внутри условного оператора. Это необходимое условие для того, чтобы рекурсия когда-нибудь закончилась.

2. Также обратите внимание, что сама себя процедура вызывает с другим параметром, не таким, с каким была вызвана она сама.

 

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

if <условие>

then <оператор>

else <вызов функции или процедуры с другими параметрами>


В качестве <условия> обычно записываются некоторые граничные случаи параметров, передаваемых рекурсивной подпрограмме, при которых результат ее работы заранее известен. Поэтому в ветви then идут обычные операторы, а в ветви else происходит рекурсивный вызов данной подпрограммы с другими параметрами.

 

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

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

 

Замечание. При развертывании рекурсии за счет создания копий параметров (нескольких последовательных вызовах рекурсивной подпрограммы) возможно переполнения стека. Это является основным недостатком рекурсивной подпрограммы.