Введение
Не так давно человечество вступило в новый XXI век — век информации и компьютеров. Благодаря бурному развитию научных, технических и технологических исследований стало возможным хранить огромные объёмы данных и преобразовывать их со скоростями, которые ещё несколько десятилетий назад могли только сниться. При создании сложных информационных систем перед проектировщиками стали нетривиальные задачи, требующие разработки новых концепций программирования.
Для решения проблем такого рода, особенно при учёте человеческого фактора, возникает необходимость обеспечения понятности алгоритма, так называемой «читабельности» исходного кода программы, и как следствие модифицируемости и относительной лёгкости сопровождения конечного программного продукта. Часто этого можно достигнуть включением в реализацию приложения рекурсивных подпрограмм, механизмы использования которых предоставляются практически всеми современными компиляторами и средами разработки.
Объект называется рекурсивным, если для своего определения или функционирования он прямо или косвенно обращается к объекту в некотором смысле такого же типа. Так, например, в теле рекурсивных подпрограмм, которые будут подробно рассмотрены ниже, в простейшем случае содержится вызов самих себя, но с другими параметрами.
Рекурсия является одним из наиболее мощных и, наверно, самым общим методом научного познания. Она эффективно применяется во многих прикладных и теоретических естественнонаучных дисциплинах, и стала неотъемлемой их частью.
Этому нетрудно найти множество подтверждений, однако один и тот же по сути метод, применительно к различным областям носит различные названия, такие как индукция, рекурсия или рекуррентные соотношения. Различия касаются особенностей использования.
Под индукцией понимается метод доказательства утверждений с формулировкой зависящей от натурального переменного , который строится на базе индукции (правильности утверждения при или ), затем утверждение полагается правильным при и проводится доказательство для .
Термин рекуррентное соотношение связан с американским научным стилем и определяет математическое задание функции с помощью рекурсии.
Важную роль в теории алгоритмов сыграл аппарат рекурсивных функций, разработанный Алонзо Чёрчем и позволивший ему формализовать понятие алгоритма.
Последние двадцать лет получили бурное развитие созданная и глубоко развитая Бенуа Мандельбротом фрактальная геометрия, теория мультифракталов и их приложения. Нужно заметить, что в теориях понятие рекурсии одно из основных. Так, например, многие фрактальные геометрические фигуры, такие как совершенное канторово множество или салфетка Серпинского, определяются рекурсивно.
Как видим, понятие рекурсии очень широко и многогранно. В настоящей работе будет освещён лишь один аспект этого понятия, а именно рекурсивные алгоритмы. Они рассмотрены как с позиций теории алгоритмов и теории сложности, так и с точки зрения практического программирования. Читатель сможет узнать, как применять на практике алгоритмы, содержащие рекурсию, а главное когда стоит это делать. Важно сохранять баланс между изящностью и простотой восприятия, присущие рекурсивным алгоритмам, и сложностью его реализации на конкретной вычислительной системе.
1. Сущность рекурсии
Процедура или функция может содержать вызов других процедур или функций. В том числе процедура может вызвать саму себя. Никакого парадокса здесь нет — компьютер лишь последовательно выполняет встретившиеся ему в программе команды и, если встречается вызов процедуры, просто начинает выполнять эту процедуру. Без разницы, какая процедура дала команду это делать.
Пример рекурсивной процедуры:
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;
Обратите внимание, что в приведенных примерах рекурсивный вызов стоит внутри условного оператора. Это необходимое условие для того, чтобы рекурсия когда-нибудь закончилась. Также обратите внимание, что сама себя процедура вызывает с другим параметром, не таким, с каким была вызвана она сама. Если в процедуре не используются глобальные переменные, то это также необходимо, чтобы рекурсия не продолжалась до бесконечности.
2. Сложная рекурсия
Возможна чуть более сложная схема: функция A вызывает функцию B, а та в свою очередь вызывает A. Это называется сложной рекурсией. При этом оказывается, что описываемая первой процедура должна вызывать еще не описанную. Чтобы это было возможно, требуется использовать опережающее описание.
Пример:
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. Имитация работы цикла с помощью рекурсии
Если процедура вызывает сама себя, то, по сути, это приводит к повторному выполнению содержащихся в ней инструкций, что аналогично работе цикла. Некоторые языки программирования не содержат циклических конструкций вовсе, предоставляя программистам организовывать повторения с помощью рекурсии (например, Пролог, где рекурсия — основной прием программирования).
Для примера сымитируем работу цикла 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. Тем не менее, такое решение является наиболее приемлемым.
4. Рекуррентные соотношения. Рекурсия и итерация
Говорят, что последовательность векторов задана рекуррентным соотношением, если задан начальный вектор и функциональная зависимость последующего вектора от предыдущего
Простым примером величины, вычисляемой с помощью рекуррентных соотношений, является факториал
Очередной факториал можно вычислить по предыдущему как:
Введя обозначение , получим соотношение:
Вектора из формулы (1) можно интерпретировать как наборы значений переменных. Тогда вычисление требуемого элемента последовательности будет состоять в повторяющемся обновлении их значений. В частности для факториала:
x := 1;
for i := 2 to n do
x := x * i;
writeln(x);
Каждое такое обновление (x := x * i) называется итерацией, а процесс повторения итераций — итерированием.
Обратим, однако, внимание, что соотношение (1) является чисто рекурсивным определением последовательности и вычисление n-го элемента есть на самом деле многократное взятие функции f от самой себя:
В частности для факториала можно написать:
function Factorial(n: integer): integer;
begin
if n > 1 then
Factorial := n * Factorial(n-1)
else
Factorial := 1;
end;
Следует понимать, что вызов функций влечет за собой некоторые дополнительные накладные расходы, поэтому первый вариант вычисления факториала будет несколько более быстрым. Вообще итерационные решения работают быстрее рекурсивных. Прежде чем переходить к ситуациям, когда рекурсия полезна, обратим внимание еще на один пример, где ее использовать не следует. Рассмотрим частный случай рекуррентных соотношений, когда следующее значение в последовательности зависит не от одного, а сразу от нескольких предыдущих значений. Примером может служить известная последовательность Фибоначчи, в которой каждый следующий элемент есть сумма двух предыдущих:
При «лобовом» подходе можно написать:
function Fib(n: integer): integer;
begin
if n > 1 then
Fib := Fib(n-1) + Fib(n-2)
else
Fib := 1;
end;
Каждый вызов Fib создает сразу две копии себя, каждая из копий — еще две и т.д. Количество операций растет с номером n экспоненциально, хотя при итерационном решении достаточно линейного по n количества операций.
На самом деле, приведенный пример учит нас не КОГДА рекурсию не следует использовать, а тому КАК ее не следует использовать. В конце концов, если существует быстрое итерационное (на базе циклов) решение, то тот же цикл можно реализовать с помощью рекурсивной процедуры или функции. Например:
// 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 Прохождение деревьев
рекурсивный алгоритм программирование арифметический
Во всех алгоритмах, связанных с древовидными структурами неизменно встречается одна и та же идея, а именно идея прохождения или обхода дерева. Это — такой способ посещения узлов дерева, при котором каждый узел проходится точно один раз. При этом получается линейная расстановка узлов дерева. В частности существует три способа: можно проходить узлы в прямом, обратном и концевом порядке.
Алгоритм обхода в прямом порядке:
Попасть в корень,
Пройти все поддеревья слева на право в прямом порядке.
Данный алгоритм рекурсивен, так как прохождение дерева содержит прохождение поддеревьев, а они в свою очередь проходятся по тому же алгоритму.
В частности для дерева на рис. 3 и 4 прямой обход дает последовательность узлов: A, B, C, D, E, G, H.
Получающаяся последовательность соответствует последовательному слева направо перечислению узлов при представлении дерева с помощью вложенных скобок и в десятичной системе Дьюи, а также проходу сверху вниз при представлении в виде уступчатого списка.
При реализации этого алгоритма на языке программирования попадание в корень соответствует выполнение процедурой или функцией некоторых действий, а прохождение поддеревьев — рекурсивным вызовам самой себя. В частности для бинарного дерева (где из каждого узла исходит не более двух поддеревьев) соответствующая процедура будет выглядеть так:
// Preorder Traversal — английское название для прямого порядка
procedure PreorderTraversal({Аргументы});
begin
//Прохождение корня
DoSomething({Аргументы});
//Прохождение левого поддерева
if {Существует левое поддерево} then
PreorderTransversal({Аргументы 2});
//Прохождение правого поддерева
if {Существует правое поддерево} then
PreorderTransversal({Аргументы 3});
end;
То есть сначала процедура производит все действия, а только затем происходят все рекурсивные вызовы.
Алгоритм обхода в обратном порядке:
Пройти левое поддерево,
Попасть в корень,
Пройти следующее за левым поддерево.
Попасть в корень,
и т.д пока не будет пройдено крайнее правое поддерево.
То есть проходятся все поддеревья слева на право, а возвращение в корень располагается между этими прохождениями. Для дерева на рис. 3 и 4 это дает последовательность узлов: B, A, D, C, E, G, F.
В соответствующей рекурсивной процедуре действия будут располагаться в промежутках между рекурсивными вызовами. В частности для бинарного дерева:
// Inorder Traversal — английское название для обратного порядка
procedure InorderTraversal({Аргументы});
begin
//Прохождение левого поддерева
if {Существует левое поддерево} then
InorderTraversal({Аргументы 2});
//Прохождение корня
DoSomething({Аргументы});
//Прохождение правого поддерева
if {Существует правое поддерево} then
InorderTraversal({Аргументы 3});
end;
Алгоритм обхода в концевом порядке:
Пройти все поддеревья слева на право,
Попасть в корень.
Для дерева на рис. 3 и 4 это даст последовательность узлов: B, D, E, G, F, C, A.
В соответствующей рекурсивной процедуре действия будут располагаться после рекурсивных вызовов. В частности для бинарного дерева:
// Postorder Traversal — английское название для концевого порядка
procedure PostorderTraversal({Аргументы});
begin
//Прохождение левого поддерева
if {Существует левое поддерево} then
PostorderTraversal({Аргументы 2});
//Прохождение правого поддерева
if {Существует правое поддерево} then
PostorderTraversal({Аргументы 3});
//Прохождение корня
DoSomething({Аргументы});
end;
5.3 Представление дерева в памяти компьютера
Если некоторая информация располагается в узлах дерева, то для ее хранения можно использовать соответствующую динамическую структуру данных. На Паскале это делается с помощью переменной типа запись (record), содержащей указатели на поддеревья того же типа. Например, бинарное дерево, где в каждом узле содержится целое число можно сохранить с помощью переменной типа PTree, который описан ниже:
type
PTree = TTree;
TTree = record
Inf: integer;
LeftSubTree, RightSubTree: PTree;
end;
Каждый узел имеет тип PTree. Это указатель, то есть каждый узел необходимо создавать, вызывая для него процедуру New. Если узел является концевым, то его полям LeftSubTree и RightSubTree присваивается значение nil. В противном случае узлы LeftSubTree и RightSubTree также создаются процедурой New.
Схематично одна такая запись изображена на рис. 5.
Рис. 5. Схематичное изображение записи типа TTree.
Запись имеет три поля: Inf — некоторое число, LeftSubTree и RightSubTree — указатели на записи того же типа TTree.
Пример дерева, составленного из таких записей, показан на рисунке 6.
Рис. 6. Дерево, составленное из записей типа TTree.
Каждая запись хранит число и два указателя, которые могут содержать либо nil, либо адреса других записей того же типа.
Если вы ранее не работали со структурами состоящими из записей, содержащих ссылки на записи того же типа, то рекомендуем ознакомиться с материалом о рекурсивных структурах данных.
6. Примеры рекурсивных алгоритмов
6.1 Рисование дерева
Рассмотрим алгоритм рисования деревца, изображенного на рис. 6. Если каждую линию считать узлом, то данное изображение вполне удовлетворяет определению дерева, данному в предыдущем разделе.
Рис. 6. Деревце.
Рекурсивная процедура, очевидно должна рисовать одну линию (ствол до первого разветвления), а затем вызывать сама себя для рисования двух поддеревьев. Поддеревья отличаются от содержащего их дерева координатами начальной точки, углом поворота, длиной ствола и количеством содержащихся в них разветвлений (на одно меньше). Все эти отличия следует сделать параметрами рекурсивной процедуры.
Пример такой процедуры, написанный на Delphi, представлен ниже:
procedure Tree(
Canvas: TCanvas; //Canvas, на котором будет рисоваться дерево
x,y: extended; //Координаты корня
Angle: extended; //Угол, под которым растет дерево
TrunkLength: extended; //Длина ствола
n: integer //Количество разветвлений (сколько еще предстоит рекурсивных вызовов)
);
var
x2, y2: extended; //Конец ствола (точка разветвления)
begin
x2 := x + TrunkLength * cos(Angle);
y2 := y — TrunkLength * sin(Angle);
Canvas.MoveTo(round(x), round(y));
Canvas.LineTo(round(x2), round(y2));
if n > 1 then
begin
Tree(Canvas, x2, y2, Angle+Pi/4, 0.55*TrunkLength, n-1);
Tree(Canvas, x2, y2, Angle-Pi/4, 0.55*TrunkLength, n-1);
end;
Для получения рис. 6 эта процедура была вызвана со следующими параметрами:
Tree(Image1.Canvas, 175, 325, Pi/2, 120, 15);
Заметим, что рисование осуществляется до рекурсивных вызовов, то есть дерево рисуется в прямом порядке.
6.2 Ханойские башни
Согласно легенде в Великом храме города Бенарас, под собором, отмечающим середину мира, находится бронзовый диск, на котором укреплены 3 алмазных стержня, высотой в один локоть и толщиной с пчелу. Давным-давно, в самом начале времен монахи этого монастыря провинились перед богом Брамой. Разгневанный, Брама воздвиг три высоких стержня и на один из них поместил 64 диска из чистого золота, причем так, что каждый меньший диск лежит на большем. Как только все 64 диска будут переложены со стержня, на который Бог Брама сложил их при создании мира, на другой стержень, башня вместе с храмом обратятся в пыль и под громовые раскаты погибнет мир.
В процессе требуется, чтобы больший диск ни разу не оказывался над меньшим. Монахи в затруднении, в какой же последовательности стоит делать перекладывания? Требуется снабдить их софтом для расчета этой последовательности.
Независимо от Брамы данную головоломку в конце 19 века предложил французский математик Эдуард Люка. В продаваемом варианте обычно использовалось 7-8 дисков (рис. 7).
Рис. 7. Головоломка «Ханойские башни».
Предположим, что существует решение для n-1 диска. Тогда для перекладывания n дисков надо действовать следующим образом:
1)Перекладываем n-1 диск.
2) Перекладываем n-й диск на оставшийся свободным штырь.
3) Перекладываем стопку из n-1 диска, полученную в пункте (1) поверх n-го диска.
Поскольку для случая n = 1 алгоритм перекладывания очевиден, то по индукции с помощью выполнения действий (1) — (3) можем переложить произвольное количество дисков.
Создадим рекурсивную процедуру, печатающую всю последовательность перекладываний для заданного количества дисков. Такая процедура при каждом своем вызове должна печатать информацию об одном перекладывании (из пункта 2 алгоритма). Для перекладываний из пунктов (1) и (3) процедура вызовет сама себя с уменьшенным на единицу количеством дисков.
//n — количество дисков
//a, b, c — номера штырьков. Перекладывание производится со штырька a,
//на штырек b при вспомогательном штырьке c.
procedure Hanoi(n, a, b, c: integer);
begin
if n > 1 then
begin
Hanoi(n-1, a, c, b);
writeln(a, ‘ -> ‘, b);
Hanoi(n-1, c, b, a);
end else
writeln(a, ‘ -> ‘, b);
end;
Заметим, что множество рекурсивно вызванных процедур в данном случае образует дерево, проходимое в обратном порядке.
6.3 Синтаксический анализ арифметических выражений
Задача синтаксического анализа заключается в том, чтобы по имеющейся строке, содержащей арифметическое выражение, и известным значениям, входящих в нее переменных, вычислить значение выражения.
Процесс вычисления арифметических выражений можно представить в виде бинарного дерева. Действительно, каждый из арифметических операторов (+, -, *, /) требует двух операндов, которые также будут являться арифметическими выражениями и, соответственно могут рассматриваться как поддеревья. Рис. 8 показывает пример дерева, соответствующего выражению:
Рис. 8. Синтаксическое дерево, соответствующее арифметическому выражению (6).
В таком дереве концевыми узлами всегда будут переменные (здесь x) или числовые константы, а все внутренние узлы будут содержать арифметические операторы. Чтобы выполнить оператор, надо сначала вычислить его операнды. Таким образом, дерево на рисунке следует обходить в концевом порядке. Соответствующая последовательность узлов
называется обратной польской записью арифметического выражения.
При построении синтаксического дерева следует обратить внимание на следующую особенность. Если есть, например, выражение
и операции сложения и вычитания мы будем считывать слева на право, то правильное синтаксическое дерево будет содержать минус вместо плюса (рис. 9а). По сути, это дерево соответствует выражению Облегчить составление дерева можно, если анализировать выражение (8) наоборот, справа налево. В этом случае получается дерево с рис. 9б, эквивалентное дереву 8а, но не требующее замены знаков.
Аналогично справа налево нужно анализировать выражения, содержащие операторы умножения и деления.
Рис. 9. Синтаксические деревья для выражения a — b + c при чтении слева направо (а) и справа налево (б).
6.4 Быстрые сортировки
Простые методы сортировки вроде метода выбора или метода пузырька сортируют массив из n элементов за O(n2) операций. Однако с помощью принципа «разделяй и властвуй» удается построить более быстрые, работающие за O(n log2 n) алгоритмы. Суть этого принципа в том, что решение получается путем рекурсивного разделения задачи на несколько простые подзадачи того же типа до тех пор, пока они не станут элементарными. Приведем в качестве примеров несколько быстрых алгоритмов такого рода.
Алгоритм 1: «Быстрая» сортировка (quicksort).
1. Выбирается опорный элемент (например, первый или случайный).
2. Реорганизуем массив так, чтобы сначала шли элементы меньшие опорного, потом равные ему, затем большие. Для этого достаточно помнить, сколько было найдено меньших (m1) и больших (m2), чем опорный и ставить очередной элемент на место с индексом m1, а очередной больший на место с индексом n-1-m2.
После выполнения такой операции опорный элемент и равные ему стоят на своем месте, их переставлять больше не придется. Между «меньшей» и «большей» часть массива перестановок также быть не может. То есть эти части можно сортировать независимо друг от друга.
3. Если «меньшая» или «большая» часть состоит из одного элемента, то она уже отсортирована и делать ничего не надо. Иначе сортируем эти части с помощью алгоритма быстрой сортировки (то есть, выполняем для нее шаги 1-3).
Как видите, быстрая сортировка состоит из выполнения шагов 1 и 2 и рекурсивного вызова алгоритма для получившихся частей массива.
Алгоритм 2: Сортировка слиянием (merge sort).
Делим массив на две части примерно одинакового размера и, если получившаяся половина массива содержит больше одного элемента, то сортируем ее с помощью сортировки слиянием. Как видите, этот пункт содержит рекурсивное обращение ко всему алгоритму в целом.
Соединяем две отсортированные половины так, чтобы получился один отсортированный массив. Для этого помещаем во вспомогательный массив элементы из первой половины, пока они не превосходят очередного элемента из второй половины. Затем начинаем помещать туда элементы второй половины, пока они не превосходят очередного элемента из первой половины. Затем снова берем элементы первой половины и т.д. Эта операция называется слиянием и требует столько шагов, сколько элементов в обоих соединяемых массивах.
Алгоритм 3: Сортировка деревом (tree sort).
Прежде чем переходить к объяснению сути алгоритма введем одно понятие. Двоичным деревом поиска называется бинарное дерево, в узлах которого располагаются числа таким образом, что в левом поддереве каждого узла находятся числа меньшие, чем в этом узле, а в правом поддереве больше или равные тому, что в этом узле. На рис. 10 показано два примера деревьев поиска, составленных из одних и тех же чисел.
Рис. 10. Двоичные деревья поиска, составленные из чисел 1, 3, 4, 6, 7, 8, 10, 13, 14.
Если для каждой вершины высота поддеревьев различается не более чем на единицу, то дерево называется сбалансированным. Сбалансированные деревья поиска также называются АВЛ-деревьями (по первым буквам фамилий изобретателей Г. М. Адельсона-Вельского и Е. М. Ландиса). Как видно на рис. 10а показано сбалансированное дерево, на рис. 10б несбалансированное.
Заметим, что расположение чисел по возрастанию получится, если обходить эти деревья в обратном прядке.
Сортировка деревом получится, если мы сначала последовательно будем добавлять числа из массива в двоичное дерево поиска, а затем обойдем его в обратном порядке.
Если дерево будет близко к сбалансированному, то сортировка потребует примерно n log2 n операций. Если не повезет и дерево окажется максимально несбалансированным, то сортировка займет n2 операций.
6.5 Произвольное количество вложенных циклов
Разместив рекурсивные вызовы внутри цикла, по сути, получим вложенные циклы, где уровень вложенности равен глубине рекурсии.
Для примера напишем процедуру, печатающую все возможные сочетания из k чисел от 1 до n (). Числа, входящие в каждое сочетание, будем печатать в порядке возрастания. Сочетания из двух чисел (k=2) печатаются так:
for i1 := 1 to n do
for i2 := i1 + 1 to n do
written(i1, ‘ ‘, i2);
Сочетания из трех чисел (k=3) так:
for i1 := 1 to n do
for i2 := i1 + 1 to n do
for i3 := i2 + 1 to n do
written(i1, ‘ ‘, i2, ‘ ‘, i3);
Однако, если количество чисел в сочетании задается переменной, то придется прибегнуть к рекурсии.
procedure Combinations(
n, k: integer;
//Массив, в котором будем формировать сочетания
var Indexes: array of integer;
//Счетчик глубины рекурсии
d: integer);
var
i, i_min: integer;
s: string;
begin
if d < k then
begin
if d = 0 then
i_min := 1
else
i_min := Indexes[d-1] + 1;
for i := i_min to n do
Indexes[d] := i;
Combinations(n, k, Indexes, d+1);
end;
else
begin
for i := 0 to k-1 do
write(Indexes[i], ‘ ‘);
writeln;
end;
6.6 Задачи на графах
Графом называют графическое изображение, состоящее из вершин (узлов) и соединяющих некоторые пары вершин ребер (рис. 11а).
Более строго: граф — совокупность множества вершин и множества ребер. Множество ребер — подмножество евклидова квадрата множества вершин (то есть ребро соединяет ровно две вершины).
Ребрам можно также присвоить направление. Граф в этом случае называется ориентированным (рис. 11б).
Рис. 11. (а) Граф. (б) Ориентированный граф.
Теория графов находит применения в самых разных областях. Несколько примеров:
Логистика и транспортные системы. Вершинами будут склады с товарами или пункты назначения, а ребра — дороги, их соединяющие.
Маршрутизация сетей. Вершины — компьютеры, соединенные в сеть, ребра — связи между ними. Решается задача о путях передачи данных с одного компьютера на другой.
Компьютерная химия. Модели в виде графов используются для описания путей протекания сложных реакций. Вершины — участвующие в реакциях вещества, ребра — пути превращений веществ. Также графом является изображение структур молекул: вершины — атомы, ребра — химические связи.
Электрические сети.
Сайты в Интернете можно считать узлами ориентированного графа, ребрами которого будут гиперссылки.
Современная теория графов представляет собой мощную формальную систему, имеющую необозримое множество применений.
Путем или цепью в графе называется последовательность вершин, в которой каждая вершина соединена ребром со следующей. Пути, в которых начальная и конечная вершина совпадают, называют циклами. Если для каждой пары вершин существует путь их соединяющих, то такой граф называют связным.
В программировании используются три способа хранения в памяти информации о структуре графов.
1) Матрицы смежности
Квадратная матрица M, где как строки, так и столбцы соответствуют вершинам графа. Если вершины с номерами i и j соединены ребром, то Mij = 1, иначе Mij = 0. Для неориентированного графа матрица, очевидно, симметрична. Ориентированный граф задается антисимметричной матрицей. Если ребро выходит из узла i и приходит в узел j, то Mij = 1, а симметричный элемент Mji = -1.
2) Матрица инцидентности
Столбцы матрицы соответствуют вершинам, а строки ребрам. Если ребро с номером i соединяет вершины с номерами j и k, то элементы матрицы Iij = Iik = 1. Остальные элементы i-й строки равны 0.
3) Список ребер
Просто набор пар номеров вершин, соединенных ребрами.
Рассмотренные выше деревья являются частным случаем графов. Деревом будет любой связный граф, не содержащий циклов.
Задачи, возникающие в теории графов многочисленны и разнообразны. Про них пишутся толстые книги, и нет никакой возможности сколько-нибудь полно их здесь обозреть. Поэтому мы ограничимся замечанием, что многие из этих задач требуют систематического перебора вершин. Если перебирать вершины, связанные ребрами и при этом посещать каждую вершину только один раз, то множество посещаемых алгоритмом вершин будет образовывать дерево, а сам алгоритм естественно сделать рекурсивным.
Например, классической задачей является поиск пути из одной вершины в другую. Алгоритм поиска должен будет построить дерево возможных путей из начальной вершины, концевыми узлами которого будут вершины, из которых нельзя попасть ни в какую вершину, не принадлежащую ранее построенной ветви (не помеченную как уже посещенную). Задача будет решена, когда один из концевых узлов совпадет с конечной вершиной, путь в которую требуется найти.
Заключение
По итогам разностороннего исследования рекурсивных алгоритмов можно сделать ряд важных выводов.
Во-первых, рекурсивные алгоритмы есть универсальное средство решения разнообразных алгоритмических проблем. Показано, что любая разрешимая задача такого рода имеет рекурсивное решение, которое при этом отличается изяществом и простотой для восприятия человеком.
Во-вторых, рекурсивные алгоритмы часто имеют более низкую асимптотическую сложность, чем эквивалентные им итерационные. То есть теоретически они быстрее.
В-третьих, развитие современных программных средств сделало практическое использование рекурсии достаточно несложным делом, а новые концепции и технологии программирования преодолели проблему низкой эффективности рекурсивных программ, созданную необходимостью вызова большого количества подпроцедур.
Конечно, после всего вышесказанного не стоит считать рекурсивные алгоритмы панацеей от всех профессиональных болезней программиста. Но в то же время не стоит умалять их значения. Основное — это быстро и качественно найти решение стоящей задачи, и тут следует принимать во внимание и возможность применения рекурсивных алгоритмов.
Цель курсовой работы достигнута. Задачи выполнены.
Список использованной литературы
1. Носов В.А. Основы теории алгоритмов и анализа их сложности. — М., 1992.
2. Федер Е. Фракталы. — М.: Мир, 1991.
3. Клейн М. Математика. Утрата неопределённости. — М.: Мир, 1987.
4. Фиошин М. -исчисление. — М., 1990.
5. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. — М., 1983.
6. Емельченков Е.П., Емельченков В.Е. Вычислимость. Введение в теорию алгоритмов. — М., 2000.
7. Глухов М.М. Математическая логика. — М., 1982.
8. Мальцев А.И. Алгоритмы и рекурсивные функции. — М., 1965.
9. Трахтенброт Б.А. Сложность алгоритмов и вычислений: спецкурс для студентов НГУ. — Новосибирск, 1967.
10. Трахтенброт Б.А. Алгоритмы и вычислительные автоматы. — М., 1974.
11. Успенский В.А., Семёнов А.Л. Теория алгоритмов: основные открытия и приложения. — М., 1987.
12. Абрамов С.А. Математические построения и программирование. — М.: Наука, 1978.
13. Кнут Д. Искусство программирования для ЭВМ.
14. Шилдт Г. Работа с Турбо Паскалем. — М., 1990.
