Глава 3
Рекурсивные алгоритмы
3.1. Введение .......................... 132 3.2. Когда не следует использовать рекурсию ........... 134 3.3. Два примера рекурсивных программ ............ 137 3.4. Алгоритмы с возвратом .... 143 3.5. Задача о восьми ферзях ... 149 3.6. Задача о стабильных браках ...................................... 154 3.7. Задача оптимального выбора ..................................... 160
Упражнения ............................. 164
Литература .............................. 166
Рекурсивные алгоритмы
132
3.1. ВведениеОбъект
называется рекурсивным, если его части определены через него самого.
Рекурсия встречается не только в математике, но и в обычной жизни. Кто не видел рекламной картинки, которая содержит саму себя?
Рис. 3.1. Рекурсивное изображение
Рекурсия особенно хорошо являет свою мощь в математических определени%
ях. Знакомые примеры – натуральные числа, древесные структуры и некоторые функции:
1. Натуральные числа:
(a) 0 является натуральным числом.
(b) Число, следующее за натуральным, является натуральным.
2. Древесные структуры:
(a)
∅ является деревом (и называется «пустым деревом»).
(b) Если t
1
и t
2
– деревья, то конструкция, состоящая из узла с двумя по%
томками t
1
и t
2
, тоже является деревом (двоичным или бинарным).
3. Факториальная функция f(n)
:
f(0) = 1
f(n) = n
×
f(n – 1)
для n > 0
Очевидно, мощь рекурсии заключается в возможности определить бесконеч%
ное множество объектов с помощью конечного утверждения. Подобным же обра%
зом бесконечное число расчетов может быть описано конечной рекурсивной программой, даже если программа не содержит явных циклов. Однако рекур%
сивные алгоритмы уместны прежде всего тогда, когда решаемая проблема, вычис%
ляемая функция или обрабатываемая структура данных заданы рекурсивным образом. В общем случае рекурсивная программа
P
может быть выражена как композиция
P
P
P
P
P
последовательности инструкций
S
(не содержащей
P
) и самой
P
:
P
≡ PPPPP[S, P]
133
Необходимое и достаточное средство для рекурсивной формулировки про%
грамм – процедура, так как она позволяет дать набору инструкций имя, с помо%
щью которого эти инструкции могут быть вызваны. Если процедура
P
содержит явную ссылку на саму себя, то говорят, что она явно рекурсивна; если
P
содержит ссылку на другую процедуру
Q
, которая содержит (прямую или косвенную) ссыл%
ку на
P
, то говорят, что
P
косвенно рекурсивна. Последнее означает, что наличие рекурсии может быть не очевидно из текста программы.
С процедурой обычно ассоциируется набор локальных переменных, констант,
типов и процедур, которые определены как локальные в данной процедуре и не существуют и не имеют смысла вне ее. При каждой рекурсивной активации про%
цедуры создается новый набор локальных переменных. Хотя у них те же имена,
что и у переменных в предыдущей активации процедуры, их значения другие,
и любая возможность конфликта устраняется правилами видимости идентифика%
торов: идентификаторы всегда ссылаются на набор переменных, созданный по%
следним. Такое же правило действует для параметров процедуры, которые по оп%
ределению связаны с ней.
Как и в случае операторов цикла, рекурсивные процедуры открывают возмож%
ность бесконечных вычислений. Следовательно, необходимо рассматривать про%
блему остановки. Очевидное фундаментальное требование состоит в том, чтобы рекурсивные вызовы процедуры
P
имели место лишь при выполнении условия
B
,
которое в какой%то момент перестает выполняться. Поэтому схема рекурсивных алгоритмов точнее выражается одной из следующих форм:
P
≡ IF B THEN PPPPP[S, P] END
P
≡ PPPPP[S, IF B THEN P END]
Основной метод доказательства остановки повторяющихся процессов состоит из следующих шагов:
1) определяется целочисленная функция f(x)
(где x
– набор переменных) –
такая, что из f(x) < 0
следует условие остановки (фигурирующее в операто%
ре while или repeat
);
2) доказывается, что f(x)
уменьшается на каждом шаге процесса.
Аналогично доказывают прекращение рекурсии: достаточно показать, что каж%
дая активация
P
уменьшает некоторую целочисленную функцию f(x)
и что f(x) < 0
влечет
B
. Особенно ясный способ гарантировать остановку состоит в том, чтобы ассоциировать передаваемый по значению параметр (назовем его n
) с процедурой
P
, и рекурсивно вызывать
P
с n–1
в качестве значения этого параметра. Тогда, под%
ставляя n > 0
вместо
B
, получаем гарантию прекращения. Это можно выразить следующими схемами:
P(n)
≡ IF n > 0 THEN PPPPP[S, P(n–1)] END
P(n)
≡ PPPPP[S, IF n > 0 THEN P(n–1) END]
В практических приложениях нужно доказывать не только конечность глуби%
ны рекурсии, но и что эта глубина достаточно мала. Причина в том, что при каж%
дой рекурсивной активации процедуры
P
используется некоторый объем опера%
Введение
Рекурсивные алгоритмы
134
тивной памяти для размещения ее локальных переменных. Кроме того, нужно за%
помнить текущее состояние вычислительного процесса, чтобы после окончания новой активации
P
могла быть возобновлена предыдущая. Мы уже встречали та%
кую ситуацию в процедуре
QuickSort в главе 2. Там было обнаружено, что при наивном построении программы из операции, которая разбивает n
элементов на две части, и двух рекурсивных вызовов сортировки для двух частей глубина ре%
курсии может в худшем случае приближаться к n
. Внимательный анализ позво%
лил ограничить глубину величиной порядка l og(n)
. Разница между n
и log(n)
дос%
таточно существенна, чтобы превратить ситуацию, в которой рекурсия в высшей степени неуместна, в такую, где рекурсия становится вполне практичной.
3.2. Когда не следует использовать
рекурсию
Рекурсивные алгоритмы особенно хорошо подходят для тех ситуаций, когда ре%
шаемая задача или обрабатываемые данные определены рекурсивно. Однако на%
личие рекурсивного определения еще не означает, что рекурсивный алгоритм даст наилучшее решение. Именно попытки объяснять понятие рекурсивного ал%
горитма с помощью неподходящих примеров стали главной причиной широко распространенного предубеждения против использования рекурсии в програм%
мировании, а также мнения о неэффективности рекурсии.
Программы, в которых следует избегать использования алгоритмической рекурсии, характеризуются определенной структурой. Для них характерно нали%
чие единственного вызова
P
в конце (или в начале) композиции (так называемая
концевая рекурсия):
P
≡ IF B THEN S; P END
P
≡ S; IF B THEN P END
Такие схемы естественно возникают в тех случаях, когда вычисляемые значе%
ния определяются простыми рекуррентными соотношениями. Возьмем извест%
ный пример факториала f
i
= i!
:
i
= 0, 1, 2, 3, 4, 5, ...
f i
= 1, 1, 2, 6, 24, 120, ...
Первое значение определено явно: f
0
= 1
, а последующие – рекурсивно через предшествующие:
f i+1
= (i+1) * f i
Это рекуррентное соотношение наводит на мысль использовать рекурсивный алгоритм для вычисления n
%го факториала. Если ввести две переменные
I
и
F
для обозначения значений i
и f
i на i
%м уровне рекурсии, то переход к следующим чле%
нам пары последовательностей для i
и f
i требует такого вычисления:
I := I + 1; F := I * F
135
Подставляя эту пару инструкций вместо
S
, получаем рекурсивную программу
P
≡ IF I < n THEN I := I + 1; F := I * F; P END
I := 0; F := 1; P
В принятой нами нотации первая строка выражается следующим образом:
PROCEDURE P;
BEGIN
IF I < n THEN I := I + 1; F := I*F; P END
END P
Чаще используется эквивалентная форма, данная ниже.
P
заменяется процеду%
рой%функцией
F
, то есть процедурой, с которой явно ассоциируется вычисляемое значение и которая может поэтому быть использована как непосредственная со%
ставная часть выражений. Тогда переменная
F
становится лишней, а роль
I
берет на себя явно задаваемый параметр процедуры:
PROCEDURE F(I: INTEGER): INTEGER;
BEGIN
IF I > 0 THEN RETURN I * F(I – 1) ELSE RETURN 1 END
END F
Ясно, что в этом примере рекурсия может быть довольно легко заменена итера%
цией. Это выражается следующей программой:
I := 0; F := 1;
WHILE I < n DO I := I + 1; F := I*F END
В общем случае программы, построенные по обсуждаемым частным рекурсив%
ным схемам, следует переписывать в соответствии со следующим образцом:
P
≡ [x := x0; WHILE B DO S END]
Существуют и более сложные рекурсивные композиционные схемы, которые могут и должны приводиться к итеративному виду. Пример – вычисление чисел
Фибоначчи, определенных рекуррентным соотношением fib n+1
= fib n
+ fib n–1
для n > 0
и соотношениями fib
1
= 1
, fib
0
= 0
. Непосредственный наивный перевод на язык программирования дает следующую рекурсивную программу:
PROCEDURE Fib (n: INTEGER): INTEGER;
VAR res: INTEGER;
BEGIN
IF n = 0 THEN res := 0
ELSIF n = 1 THEN res := 1
ELSE res := Fib(n–1) + Fib(n–2)
END;
RETURN res
END Fib
Когда не следует использовать рекурсию
Рекурсивные алгоритмы
136
Вычисление fib n
с помощью вызова
Fib(n)
вызывает рекурсивные активации этой процедуры%функции. Сколько происходит таких активаций? Очевидно, каж%
дый вызов с n > 1
приводит к двум дальнейшим вызовам, то есть полное число вы%
зовов растет экспоненциально (см. рис. 3.2). Такая программа явно непрактична.
Рис. 3.2. Пятнадцать активаций при вызове
Fib(5)
К счастью, числа Фибоначчи можно вычислять по итерационной схеме без многократного вычисления одних и тех же значений благодаря использованию вспомогательных переменных – таких, что x = fib i
и y = fib i–1
i := 1; x := 1; y := 0;
WHILE i < n DO z := x; x := x + y; y := z; i := i + 1 END
Отметим, что три присваивания переменным x
, y
, z
можно заменить всего лишь двумя присваиваниями без привлечения вспомогательной переменной z
:
x := x + y;
y := x – y
Отсюда мораль: следует избегать рекурсии, когда есть очевидное решение,
использующее итерацию. Но это не значит, что от рекурсии нужно избавляться любой ценой. Как будет показано в последующих разделах и главах, существует много хороших применений рекурсии. Тот факт, что имеются реализации рекур%
сивных процедур на
принципиально нерекурсивных машинах, доказывает, что любая рекурсивная программа действительно может быть преобразована в чисто итерационную. Но тогда требуется явно управлять стеком рекурсии, и это часто затемняет сущность программы до такой степени, что понять ее становится весь%
ма трудно. Отсюда вывод: алгоритмы, которые по своей природе являются рекур%
сивными, а не итерационными, должны программироваться в виде рекурсивных процедур. Чтобы оценить это обстоятельство, полезно сравнить два варианта ал%
горитма быстрой сортировки в разделе 2.3.3: рекурсивный (
QuickSort
) и нерекур%
сивный (
NonRecursiveQuickSort
).
Оставшаяся часть главы посвящена разработке некоторых рекурсивных про%
грамм в ситуациях, когда применение рекурсии оправдано. Кроме того, в главе 4
рекурсия широко используется в тех случаях, когда соответствующие структуры данных делают выбор рекурсивных решений очевидным и естественным.
137
3.3. Два примера рекурсивных программСимпатичный узор на рис. 3.4 представляет собой суперпозицию пяти кривых.
Эти кривые являют регулярность структуры, так что их, вероятно, можно изобра%
зить на дисплее или графопостроителе под управлением компьютера. Наша цель –
выявить рекурсивную схему, с помощью которой можно написать программу для рисования этих кривых. Можно видеть, что три из пяти кривых имеют вид, пока%
занный на рис. 3.3; обозначим их как
H
1
,
H
2
и
H
3
. Кривая
H
i называется
гильберто вой кривой порядка i
в честь математика Гильберта (D. Hilbert, 1891).
Рис. 3.3. Гильбертовы кривые порядков 1, 2 и 3
Каждая кривая
H
i состоит из четырех копий кривой
H
i–1
половинного размера,
поэтому мы выразим процедуру рисования
H
i в виде композиции четырех вызовов для рисования
H
i–1
половинного размера и с соответствующими поворотами. Для целей иллюстрации обозначим четыре по%разному повернутых варианта базовой кривой как
A
,
B
,
C
и
D
, а шаги рисования соединительных линий обозначим стрел%
ками, направленными соответственно. Тогда возникает следующая рекурсивная схема (ср. рис. 3.3):
A:
D
←
A
↓
A
→
B
B:
C
↑
B
→
B
↓
A
C:
B
→
C
↑
C
←
D
D:
A
↓
D
←
D
↑
C
Предположим, что для рисования отрезков прямых в нашем распоряжении есть процедура line
, которая передвигает чертящее перо в заданном направлении на заданное расстояние. Для удобства примем, что направление указывается целочисленным параметром i
, так что в градусах оно равно
45
×
i
. Если длину от%
резков, из
которых составляется кривая, обозначить как u
, то процедуру, соответ%
ствующую схеме
A
, можно сразу выразить через рекурсивные вызовы аналогич%
ных процедур
B
и
D
и ее самой:
PROCEDURE A (i: INTEGER);
BEGIN
IF i > 0 THEN
D(i–1); line(4, u);
A(i–1); line(6, u);
Два примера рекурсивных программ
Рекурсивные алгоритмы
138
A(i–1); line(0, u);
B(i–1)
END
END A
Эта процедура вызывается в главной программе один раз для каждой гильбер%
товой кривой, добавляемой в рисунок. Главная программа определяет начальную точку кривой, то есть начальные координаты пера, обозначенные как x0
и y0
,
а также длину базового отрезка u
. Квадрат, в котором рисуются кривые, помеща%
ется в середине страницы с заданными шириной и высотой. Эти параметры, так же как и рисующая процедура line
, берутся из модуля
Draw
. Отметим, что этот модуль помнит текущее положение пера.
DEFINITION Draw;
(* ADruS33_Draw *)
CONST width = 1024; height = 800;
PROCEDURE Clear; (* *)
PROCEDURE SetPen(x, y: INTEGER); (* x, y*)
PROCEDURE line(dir, len: INTEGER);
(* len dir*45 # ;
(*
# *)
END Draw.
Процедура
Hilbert рисует гильбертовы кривые
H
1
... H
n
. Она рекурсивно использует четыре процедуры
A
,
B
,
C
и
D
:
VAR u: INTEGER;
(* ADruS33_Hilbert *)
PROCEDURE A (i: INTEGER);
BEGIN
IF i > 0 THEN
D(i–1); Draw.line(4, u); A(i–1); Draw.line(6, u); A(i–1); Draw.line(0, u); B(i–1)
END
END A;
PROCEDURE B (i: INTEGER);
BEGIN
IF i > 0 THEN
C(i–1); Draw.line(2, u); B(i–1); Draw.line(0, u); B(i–1); Draw.line(6, u); A(i–1)
END
END B;
PROCEDURE C (i: INTEGER);
BEGIN
IF i > 0 THEN
B(i–1); Draw.line(0, u); C(i–1); Draw.line(2, u); C(i–1); Draw.line(4, u); D(i–1)
END
END C;
PROCEDURE D (i: INTEGER);
BEGIN
IF i > 0 THEN
A(i–1); Draw.line(6, u); D(i–1); Draw.line(4, u); D(i–1); Draw.line(2, u); C(i–1)
END
END D;
139
PROCEDURE Hilbert (n: INTEGER);
CONST SquareSize = 512;
VAR i, x0, y0: INTEGER;
BEGIN
Draw.Clear;
x0 := Draw.width DIV 2; y0 := Draw.height DIV 2;
u := SquareSize; i := 0;
REPEAT
INC(i); u := u DIV 2;
x0 := x0 + (u DIV 2); y0 := y0 + (u DIV 2);
Draw.Set(x0, y0);
A(i)
UNTIL i = n
END Hilbert.
Похожий, но чуть более сложный и эстетически изощренный пример показан на рис. 3.6. Этот узор тоже получается наложением нескольких кривых, две из ко%
торых показаны на рис. 3.5.
S
i называется кривой Серпиньского порядка i
. Какова ее рекурсивная структура? Есть соблазн в качестве основного строительного бло%
ка взять фигуру
S
1
, возможно, без одного ребра. Но так решение не получится.
Главное отличие кривых Серпиньского от кривых Гильберта – в том, что первые замкнуты (и не имеют самопересечений). Это означает, что базовой рекурсивной схемой должна быть разомкнутая кривая и что четыре части соединяются связка%
ми, не принадлежащими самому рекурсивному узору. В самом деле, эти связки состоят из четырех отрезков прямых в четырех самых внешних углах, показанных жирными линиями на рис. 3.5. Их можно считать принадлежащими непустой на%
чальной кривой
S
0
, представляющей собой квадрат, стоящий на одном из углов.
Теперь легко сформулировать рекурсивную схему. Четыре узора, из которых со%
ставляется кривая, снова обозначим как
A
,
B
,
C
и
D
, а линии%связки будем рисовать явно. Заметим, что четыре рекурсивных узора действительно идентичны, отлича%
ясь поворотами на 90 градусов.
Вот базовая схема кривых Серпиньского:
S: A
B C D
А вот схема рекурсий (горизонтальные и вертикальные стрелки обозначают линии двойной длины):
A: A
B → D A
B: B
C ↓ A B
C: C
D ← B C
D: D
A ↑ C D
Если
использовать те же примитивы рисования, что и в примере с кривыми
Гильберта, то эта схема рекурсии легко превращается в рекурсивный алгоритм
(с прямой и косвенной рекурсиями).
Два примера рекурсивных программ
Рекурсивные алгоритмы
140
Рис. 3.4. Гильбертовы кривые
H
1
… H
5
Рис. 3.5. Кривые Серпиньского
S
1
и
S
2
141
PROCEDURE A (k: INTEGER);
BEGIN
IF k > 0 THEN
A(k–1); Draw.line(7, h); B(k–1); Draw.line(0, 2*h);
D(k–1); Draw.line(1, h); A(k–1)
END
END A
Эта процедура реализует первую строку схемы рекурсий. Процедуры для узо%
ров
B
,
C
и
D
получаются аналогично. Главная программа составляется по базовой схеме. Ее назначение – установить начальное положение пера и определить длину единичной линии h
в соответствии с размером рисунка. Результат выполнения этой программы для n = 4
показан на рис. 3.6.
VAR h: INTEGER;
(* ADruS33_Sierpinski *)
PROCEDURE A (k: INTEGER);
BEGIN
IF k > 0 THEN
A(k–1); Draw.line(7, h); B(k–1); Draw.line(0, 2*h);
D(k–1); Draw.line(1, h); A(k–1)
END
END A;
PROCEDURE B (k: INTEGER);
BEGIN
IF k > 0 THEN
B(k–1); Draw.line(5, h); C(k–1); Draw.line(6, 2*h);
A(k–1); Draw.line(7, h); B(k–1)
END
END B;
PROCEDURE C (k: INTEGER);
BEGIN
IF k > 0 THEN
C(k–1); Draw.line(3, h); D(k–1); Draw.line(4, 2*h);
B(k–1); Draw.line(5, h); C(k–1)
END
END C;
PROCEDURE D (k: INTEGER);
BEGIN
IF k > 0 THEN
D(k–1); Draw.line(1, h); A(k–1); Draw.line(2, 2*h);
C(k–1); Draw.line(3, h); D(k–1)
END
END D;
PROCEDURE Sierpinski* (n: INTEGER);
CONST SquareSize = 512;
VAR i, x0, y0: INTEGER;
BEGIN
Два примера рекурсивных программ
Рекурсивные алгоритмы
142
Draw.Clear;
h := SquareSize DIV 4;
x0 := Draw.width DIV 2; y0 := Draw.height DIV 2 + h;
i := 0;
REPEAT
INC(i); x0 := x0-h;
h := h DIV 2; y0 := y0+h; Draw.Set(x0, y0);
A(i); Draw.line(7,h); B(i); Draw.line(5,h);
C(i); Draw.line(3,h); D(i); Draw.line(1,h)
UNTIL i = n
END Sierpinski.
Элегантность приведенных примеров убеждает в полезности рекурсии. Пра%
вильность получившихся программ легко установить по их структуре и по схемам композиции. Более того, использование явного (и уменьшающегося) параметра уровня гарантирует остановку, так как глубина рекурсии не может превысить n
Напротив, эквивалентные программы, не использующие рекурсию явно, оказыва%
ются весьма громоздкими, и понять их нелегко. Читатель легко убедится в этом,
если попытается разобраться в программах, приведенных в [3.3].
Рис. 3.6. Кривые Серпиньского
S
1
… S
4
Скачать 2.67 Mb.