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

Основная цель этой главы заключается в исследовании рекурсивных программ и структур данных как практических инструментов. Вначале исследуется взаимосвязь между математической рекурсией и простыми рекурсивными программами и приводится ряд примеров применения рекурсии. Затем рассматривается фундаментальная рекурсивная схема, известная под названием разделяй и властвуй , которая используется для решения задач общего характера в нескольких последующих разделах этой книги. После этого приводится общий подход к реализации рекурсивных программ, называемый динамическим программированием, который предоставляет эффективные и элегантные решения для обширного класса задач. Затем подробно рассматриваются деревья, их математические свойства и связанные с ними алгоритмы, в том числе базовые методы обхода дерева (tree traversal), которые лежат в основе рекурсивных программ обработки деревьев. В завершение будут анализироваться тесно связанные с рекурсией алгоритмы обработки графов - в частности, особое внимание будет уделяться фундаментальной рекурсивной программе поиска в глубину (depth-first search), которая служит основой для многих алгоритмов обработки графов.

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

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

5.1 Рекурсивные алгоритмы

Рекурсивный алгоритм - это алгоритм, решающий задачу путем решения одного или нескольких более узких вариантов той же задачи. Для реализации рекурсивных алгоритмов в С++ используются рекурсивные функции - функции, которые вызывают самих себя. Рекурсивные функции в С++ соответствуют рекурсивным определениям математических функций. Изучение рекурсии начнем с исследования программ, которые непосредственно вычисляют математические функции. Как будет показано, базовые механизмы можно расширить, что приведет к обобщенной парадигме программирования.

Программа 5.1 Функция вычисления факториала (рекурсивная реализация)

Эта рекурсивная функция вычисляет функцию Л/!, используя стандартное рекурсивное определение. Она возвращает правильное значение, когда вызывается с неотрицательным и достаточно малым аргументом N, чтобы N\ можно было представить типом int.

int factorial(int N) {

if (N == 0) return 1; return N*factorial(N-l) ;

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

Л! = N- {N- 1)!, для Л > 1, причем О! = 1

Это определение непосредственно соответствует рекурсивной функции С++ в программе 5.1.

Программа 5.1 эквивалентна простому циклу. Например, следующий цикл for выполняет такое же вычисление:

for ( t = 1, i = 1; i <= N; i++) t *= i;

Как будет показано, рекурсивную программу всегда можно преобразовать в нерекурсивную, которая выполняет такое же вычисление. И наоборот, используя рекурсию, любое вычисление, предполагающее выполнение циклов, можно реализовать, не прибегая к циклам.

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

Программа 5.2 Сомнительная рекурсивная программа

Если аргумент Л/ является нечетным, эта функция вызывает саму себя с ЗЛ/+1 в качестве аргумента. Если N является четным, она вызывает себя с Л 2 в качестве аргумента. Для гарантированного завершения этой программы нельзя использовать индукцию, поскольку не каждый рекурсивный вызов использует аргумент, меньший заданного.

int puzzle(int N) {

if (N == 1) return 1; if (N % 2 = 0)

return puzzle(N/2); else return puzzle(3*N+1);

puzzle(3) puzzle(10) puzzle(5) puzzle(16) puzzle(8) puzzle(4) puzzle(2) puzzled)

РИСУНОК 5.1 ПРИМЕР ЦЕПОЧКИ РЕКУРСИВНЫХ ВЫЗОВОВ

Эта вложенная последовательность вызовов функции со временем завершается, однако нельзя гарантировать, что рекурсивная функция, используемая в программе 5.2, не будет иметь произвольную глубину вложенности для какого-либо аргумента. Желательно использовать рекурсивные программы, которые всегда вызывают себя с меньшими значениями аргументов.

Профамма 5.1 иллюстрирует базовые особенности рекурсивной профаммы: она вызывает саму себя (с меньшими значениями аргументов) и содержит условие завершения, при выполнении которого непосредственно вычисляет свое результирующее значение. Дабы убедиться в правильности работы профаммы, можно применить метод математической индукции:

Профамма вычисляет О! (исходное значение)

Если допустить, что программа вычисляет к\ для к < N (индуктивное предположение), то она вычисляет и Л!.

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

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

Они должны явно решать задачу для исходного значения.

В каждом рекурсивном вызове должны использоваться меньшие значения аргументов.

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

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