Рекурсия и рекурсивные алгоритмы
|
|
Рекурсией называется ситуация, когда подпрограмма вызывает сама себя. Впервые сталкиваясь с такой алгоритмической конструкцией, большинство людей испытывает определенные трудности, однако немного практики и рекурсия станет понятным и очень полезным инструментом в вашем программистском арсенале.
Содержание
1. Сущность рекурсии
2. Сложная рекурсия
3. Имитация работы цикла с помощью рекурсии
4. Рекуррентные соотношения. Рекурсия и итерация
5. Деревья
5.1. Основные определения. Способы изображения деревьев
5.2. Прохождение деревьев
5.3. Представление дерева в памяти компьютера
6. Примеры рекурсивных алгоритмов
6.1. Рисование дерева
6.2. Ханойские башни
6.3. Синтаксический анализ арифметических выражений
6.4. Быстрые сортировки
6.5. Произвольное количество вложенных циклов
6.6. Задачи на графах
6.7. Фракталы
7. Избавление от рекурсии
7.1. Явное использование стека
7.2. Запоминание последовательности рекурсивных вызовов
7.3. Определение узла дерева по его номеру
Контрольные вопросы
Задачи
Литература
1. Сущность рекурсии
Процедура или функция может содержать вызов других процедур или функций. В том числе процедура может вызвать саму себя. Никакого парадокса здесь нет – компьютер лишь последовательно выполняет встретившиеся ему в программе команды и, если встречается вызов процедуры, просто начинает выполнять эту процедуру. Без разницы, какая процедура дала команду это делать.
Пример рекурсивной процедуры:
1
2
3
4
5
6
|
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), где операторы поменялись местами.
1
2
3
4
5
6
|
procedure Rec2(a: integer);
begin
writeln(a);
if a>0 then
Rec2(a-1);
end;
|
Обратите внимание, что в приведенных примерах рекурсивный вызов стоит внутри условного оператора. Это необходимое условие для того, чтобы рекурсия когда-нибудь закончилась. Также обратите внимание, что сама себя процедура вызывает с другим параметром, не таким, с каким была вызвана она сама. Если в процедуре не используются глобальные переменные, то это также необходимо, чтобы рекурсия не продолжалась до бесконечности.
2. Сложная рекурсия
Возможна чуть более сложная схема: функция A вызывает функцию B, а та в свою очередь вызывает A. Это называетсясложной рекурсией. При этом оказывается, что описываемая первой процедура должна вызывать еще не описанную. Чтобы это было возможно, требуется использовать опережающее описание.
Пример:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
procedure A(n: integer); {Опережающее описание (заголовок) первой процедуры}
procedure B(n: integer); {Опережающее описание второй процедуры}
procedure A(n: integer); {Полное описание процедуры A}
begin
writeln(n);
B(n-1);
end;
procedure B(n: integer); {Полное описание процедуры B}
begin
writeln(n);
if n<10 then
A(n+2);
end;
|
Опережающее описание процедуры B позволяет вызывать ее из процедуры A. Опережающее описание процедуры A в данном примере не требуется и добавлено из эстетических соображений.
Если обычную рекурсию можно уподобить уроборосу (рис. 3), то образ сложной рекурсии можно почерпнуть из известного детского стихотворения, где «Волки с перепуга, скушали друг друга». Представьте себе двух съевших друг друга волков, и вы поймете сложную рекурсию.
Рис. 3. Уроборос – змей, пожирающий свой хвост. Рисунок из алхимического трактата «Synosius» Теодора Пелеканоса (1478г).
Рис. 4. Сложная рекурсия.
3. Имитация работы цикла с помощью рекурсии
Если процедура вызывает сама себя, то, по сути, это приводит к повторному выполнению содержащихся в ней инструкций, что аналогично работе цикла. Некоторые языки программирования не содержат циклических конструкций вовсе, предоставляя программистам организовывать повторения с помощью рекурсии (например, Пролог, где рекурсия - основной прием программирования).
Для примера сымитируем работу цикла for. Для этого нам потребуется переменная счетчик шагов, которую можно реализовать, например, как параметр процедуры.
Пример 1.
1
2
3
4
5
6
7
8
|
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.
1
2
3
4
5
6
|
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 наоборот от более поздних к ранним.
Наконец, рекурсивный вызов можно расположить между двумя блоками инструкций. Например:
1
2
3
4
5
6
7
|
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. Без рекурсии это будет выглядеть так:
1
2
3
4
5
6
|
while x>0 do
begin
c:=x mod 2;
x:=x div 2;
write(c);
end;
|
Проблема здесь в том, что цифры двоичного представления вычисляются в обратном порядке (сначала последние). Чтобы напечатать число в нормальном виде придется запомнить все цифры в элементах массива и выводить в отдельном цикле.
С помощью рекурсии нетрудно добиться вывода в правильном порядке без массива и второго цикла. А именно:
1
2
3
4
5
6
7
8
9
10
11
12
13
|
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. Тем не менее, такое решение кажется мне красивым.
4. Рекуррентные соотношения. Рекурсия и итерация
Говорят, что последовательность векторов  задана рекуррентным соотношением, если задан начальный вектор  и функциональная зависимость последующего вектора от предыдущего
Простым примером величины, вычисляемой с помощью рекуррентных соотношений, является факториал
Очередной факториал  можно вычислить по предыдущему как:
Введя обозначение  , получим соотношение:
Вектора  из формулы (1) можно интерпретировать как наборы значений переменных. Тогда вычисление требуемого элемента последовательности будет состоять в повторяющемся обновлении их значений. В частности для факториала:
1
2
3
4
|
x := 1;
for i := 2 to n do
x := x * i;
writeln(x);
|
Каждое такое обновление (x := x * i) называется итерацией, а процесс повторения итераций – итерированием.
Обратим, однако, внимание, что соотношение (1) является чисто рекурсивным определением последовательности и вычисление n-го элемента есть на самом деле многократное взятие функции f от самой себя:
В частности для факториала можно написать:
1
2
3
4
5
6
7
|
function Factorial(n: integer): integer;
begin
if n > 1 then
Factorial := n * Factorial(n-1)
else
Factorial := 1;
end;
|
Следует понимать, что вызов функций влечет за собой некоторые дополнительные накладные расходы, поэтому первый вариант вычисления факториала будет несколько более быстрым. Вообще итерационные решения работают быстрее рекурсивных.
Прежде чем переходить к ситуациям, когда рекурсия полезна, обратим внимание еще на один пример, где ее использовать не следует.
Рассмотрим частный случай рекуррентных соотношений, когда следующее значение в последовательности зависит не от одного, а сразу от нескольких предыдущих значений. Примером может служить известная последовательность Фибоначчи, в которой каждый следующий элемент есть сумма двух предыдущих:
При «лобовом» подходе можно написать:
1
2
3
4
5
6
7
|
function Fib(n: integer): integer;
begin
if n > 1 then
Fib := Fib(n-1) + Fib(n-2)
else
Fib := 1;
end;
|
Каждый вызов Fib создает сразу две копии себя, каждая из копий – еще две и т.д. Количество операций растет с номером n экспоненциально, хотя при итерационном решении достаточно линейного по n количества операций.
На самом деле, приведенный пример учит нас не КОГДА рекурсию не следует использовать, а тому КАК ее не следует использовать. В конце концов, если существует быстрое итерационное (на базе циклов) решение, то тот же цикл можно реализовать с помощью рекурсивной процедуры или функции. Например:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
// x1, x2 – начальные условия (1, 1)
// n – номер требуемого числа Фибоначчи
function Fib(x1, x2, n: integer): integer;
var
x3: integer;
begin
if n > 1 then
begin
x3 := x2 + x1;
x1 := x2;
x2 := x3;
Fib := Fib(x1, x2, n-1);
end else
Fib := x2;
end;
|
И все же итерационные решения предпочтительны. Спрашивается, когда же в таком случае, следует пользоваться рекурсией?
Любые рекурсивные процедуры и функции, содержащие всего один рекурсивный вызов самих себя, легко заменяются итерационными циклами. Чтобы получить что-то, не имеющее простого нерекурсивного аналога, следует обратиться к процедурам и функциям, вызывающим себя два и более раз. В этом случае множество вызываемых процедур образует уже не цепочку, как на рис. 1, а целое дерево. Существуют широкие классы задач, когда вычислительный процесс должен быть организован именно таким образом. Как раз для них рекурсия будет наиболее простым и естественным способом решения.
5. Деревья
Теоретической базой для рекурсивных функций, вызывающих себя более одного раза, служит раздел дискретной математики, изучающий деревья.
5.1. Основные определения. Способы изображения деревьев
Определение: Деревом будем называть конечное множество T, состоящее из одного или более узлов, таких что:
а) Имеется один специальный узел, называемый корнем данного дерева.
б) Остальные узлы (исключая корень) содержатся в  попарно непересекающихся подмножествах  , каждое из которых в свою очередь является деревом. Деревья называются поддеревьями данного дерева.
Это определение является рекурсивным. Если коротко, то дерево это множество, состоящее из корня и присоединенных к нему поддеревьев, которые тоже являются деревьями. Дерево определяется через само себя. Однако данное определение осмысленно, так как рекурсия конечна. Каждое поддерево содержит меньше узлов, чем содержащее его дерево. В конце концов, мы приходим к поддеревьям, содержащим всего один узел, а это уже понятно, что такое.
Рис. 3. Дерево.
На рис. 3 показано дерево с семью узлами. Хотя обычные деревья растут снизу вверх, рисовать их принято наоборот. При рисовании схемы от руки такой способ, очевидно, удобнее. Из-за данной несогласованности иногда возникает путаница, когда говорят о том, что один из узлов находится над или под другим. По этой причине удобнее пользоваться терминологией, употребляемой при описании генеалогических деревьев, называя более близкие к корню узлы предками, а более далекие потомками.
Узлы, не содержащие поддеревьев, называются концевыми узлами или листьями. Множество не пересекающихся деревьев называется лесом. Например, лес образуют поддеревья, исходящие из одного узла.
Графически дерево можно изобразить и некоторыми другими способами. Некоторые из них представлены на рис. 4. Согласно определению дерево представляет собой систему вложенных множеств, где эти множества или не пересекаются или полностью содержатся одно в другом. Такие множества можно изобразить как области на плоскости (рис. 4а). На рис. 4б вложенные множества располагаются не на плоскости, а вытянуты в одну линию. Рис. 4б также можно рассматривать как схему некоторой алгебраической формулы, содержащей вложенные скобки. Рис. 4в дает еще один популярный способ изображения древовидной структуры в виде уступчатого списка.
Рис. 4. Другие способы изображения древовидных структур: (а) вложенные множества; (б) вложенные скобки; (в) уступчатый список.
Уступчатый список имеет очевидное сходство со способом форматирования программного кода. Действительно, программа, написанная в рамках парадигмы структурного программирования, может быть представлена как дерево, состоящее из вложенных друг в друга конструкций.
Также можно провести аналогию между уступчатым списком и внешним видом оглавлений в книгах, где разделы содержат подразделы, те в свою очередь поподразделы и т.д. Традиционный способ нумерации таких разделов (раздел 1, подразделы 1.1 и 1.2, подподраздел 1.1.2 и т.п.) называется десятичной системой Дьюи. В применении к дереву на рис. 3 и 4 эта система даст:
1. A; 1.1 B; 1.2 C; 1.2.1 D; 1.2.2 E; 1.2.3 F; 1.2.3.1 G;
5.2. Прохождение деревьев
Во всех алгоритмах, связанных с древовидными структурами неизменно встречается одна и та же идея, а именно идеяпрохождения или обхода дерева. Это – такой способ посещения узлов дерева, при котором каждый узел проходится точно один раз. При этом получается линейная расстановка узлов дерева. В частности существует три способа: можно проходить узлы в прямом, обратном и концевом порядке.
</10>
|
|
