Рекурсия

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

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

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

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

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;

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

Имитация работы цикла с помощью рекурсии

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

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

Пример 1.

procedure LoopImitation(i, n: integer); {Первый параметр – счетчик шагов, второй параметр – общее количество шагов} begin writeln('Hello N ', i); //Здесь любые инструкции, которые будут повторятся if i<=n then //Пока счетчик цикла не станет равным максимальному LoopImitation(i+1, n); //значению n, повторяем инструкции путем вызова //нового экземпляра процедуры end;

Результатом вызова вида LoopImitation(1, 10) станет десятикратное выполнение инструкций с изменением счетчика от 1 до 10. В данном случае будет напечатано:

Hello N 1
Hello N 2
…
Hello N 10

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

Можно поменять местами рекурсивный вызов и подлежащие повторению инструкции, как в следующем примере.

Пример 2.

procedure LoopImitation2(i, n: integer); begin if i<=n then LoopImitation2(i+1, n); writeln('Hello N ', i); end;

В этом случае, прежде чем начнут выполняться инструкции, произойдет рекурсивный вызов процедуры. Новый экземпляр процедуры также, прежде всего, вызовет еще один экземпляр и так далее, пока не дойдем до максимального значения счетчика. Только после этого последняя из вызванных процедур выполнит свои инструкции, затем выполнит свои инструкции предпоследняя и т.д. Результатом вызова LoopImitation2(1, 10) будет печать приветствий в обратном порядке:

Hello N 10
…
Hello N 1

Если представить себе цепочку из рекурсивно вызванных процедур, то в примере 1 мы проходим ее от раньше вызванных процедур к более поздним. В примере 2 наоборот от более поздних к ранним.

Наконец, рекурсивный вызов можно расположить между двумя блоками инструкций. Например:

procedure LoopImitation3(i, n: integer); begin writeln('Hello N ', i); {Здесь может располагаться первый блок инструкций} if i<=n then LoopImitation3(i+1, n); writeln('Hello N ', i); {Здесь может располагаться второй блок инструкций} end;

Здесь сначала последовательно выполнятся инструкции из первого блока затем в обратном порядке инструкции второго блока. При вызове LoopImitation3(1, 10) получим:

Hello N 1
…
Hello N 10
Hello N 10
…
Hello N 1

Потребуется сразу два цикла, чтобы сделать то же самое без рекурсии.

Тем, что выполнение частей одной и той же процедуры разнесено по времени можно воспользоваться. Например:

Пример 3: Перевод числа в двоичную систему.

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

.

Взяв же целую часть от деления на 2:

,

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

while x>0 do begin c:=x mod 2; x:=x div 2; write(c); end;

Проблема здесь в том, что цифры двоичного представления вычисляются в обратном порядке (сначала последние). Чтобы напечатать число в нормальном виде придется запомнить все цифры в элементах массива и выводить в отдельном цикле.

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

procedure BinaryRepresentation(x: integer); var c, x: integer; begin {Первый блок. Выполняется в порядке вызова процедур} c:= x mod 2; x:= x div 2; {Рекурсивный вызов} if x>0 then BinaryRepresentation(x); {Второй блок. Выполняется в обратном порядке} write(c); end;

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