Файл: Think likea programmer.pdf

192 Глава 6
избежать передачи дополнительных данных в рекурсивный вызов и использования глобальных переменных.
Также обратите внимание на то, как первое правило для связного списка, «если список L минимален», интерпретируется в конкретной реализации этой задачи как «если список не имеет узлов». Дело в том, что мы можем сказать, что список без узлов имеет ноль отрицатель- ных значений. Тем не менее в некоторых случаях не существует ника- кого содержательного ответа на наш вопрос Q для списка без узлов, а минимальным случаем является список с одним узлом. Предположим, наш вопрос звучит так: «Каково наибольшее число в этом списке?» На этот вопрос нельзя ответить в случае списка без значений. Если вы не понимаете, почему, представьте, что вы учитель начальной школы и ваш класс состоит из одних девочек. Если бы директор вашей школы спросил вас, сколько мальчиков из вашего класса поют в хоре, вы мог- ли бы просто ответить «ноль», поскольку в вашем классе нет мальчи- ков. Если бы директор школы попросил вас назвать самого высокого мальчика в вашем классе, вы не смогли бы дать осмысленный ответ на этот вопрос, поскольку для этого в вашем классе должен быть хотя бы один мальчик. Точно так же, если вопрос о наборе данных требует на- личия по крайней мере одного значения, чтобы на него можно было осмысленно ответить, то минимальный набор данных включает один элемент. Однако вы все равно можете возвратить какой-то ответ для случая, когда размер равен нулю, хотя бы для обеспечения гибкости при использовании функции и для предотвращения сбоя.

Решение задач с помощью рекурсии 193
ми списками, мы как разработчики рекурсивного решения просто со- средоточиваемся на существовании левого и правого поддеревьев, не учитывая их содержимое. Это показано на рис. 6.8.
Рис. 6.7. Двоичное дерево, разделенное на корневой узел и левое и правое поддеревья
Как всегда, при рекурсивном решении задачи с двоичными дере- вьями мы хотим использовать БРИ. Мы сделаем рекурсивные вызо- вы функций и предположим, что они возвращают правильные резуль- таты, не беспокоясь о том, как рекурсивный процесс решает задачу в целом. Как и в случае со связными списками, мы будем работать с естественным делением двоичного дерева. Эта дает следующий об- щий план. Чтобы ответить на вопрос Q для дерева T:
Рис. 6.8. Двоичное дерево, каким его должен представлять программист, использующий рекур-
сию: корневой узел с левым и правым поддеревьями неизвестной и неучитываемой структуры
1. Если дерево T имеет минимальный размер, следует напрямую присвоить значение по умолчанию. В противном случае...
2. Сделать рекурсивный вызов, чтобы ответить на вопрос Q для ле- вого поддерева T.
3. Сделать рекурсивный вызов, чтобы ответить на вопрос Q для правого поддерева T.
4. Проверить значение в корневом узле дерева T.
5. Использовать результаты предыдущих трех шагов, чтобы отве- тить на вопрос Q для всего дерева T.
Теперь давайте применим общий план к решению конкретной задачи.

194 Глава 6
: 9
"
Напишите функцию, которая при передаче двоичного дерева, где каждый узел содер- жит целое число, возвращает наибольшее целое число в дереве.
Применение общего плана к этой конкретной задаче предпола- гает выполнение следующих действий:
1. Если корень дерева не имеет дочерних элементов, верните зна- чение в корневой узел. В противном случае...
2. Сделайте рекурсивный вызов, чтобы найти наибольшее значе- ние в левом поддереве.
3. Сделайте рекурсивный вызов, чтобы найти наибольшее значе- ние в правом поддереве.
4. Проверьте значение в корневом узле.
5. Верните наибольшее из значений, найденных на предыдущих трех этапах.
Имея в виду эти шаги, мы можем прямо написать код для реше- ния этой задачи:
int maxValue(treePtr root) {
X if (root == NULL) return 0;
Y if (root->right == NULL && root->left == NULL) return root->data;
Z int leftMax = maxValue(root->left);
[ int rightMax = maxValue(root->right);
\ int maxNum = root->data;
if (leftMax > maxNum) maxNum = leftMax;
if (rightMax > maxNum) maxNum = rightMax;
return maxNum;
}
Обратите внимание на то, что минимальное дерево для этой за- дачи представляет собой единственный узел
Y
(хотя случай с пустым деревом учитывается по соображениям безопасности
X
). Это связа- но с тем, что на вопрос, который мы задаем, можно дать осмыслен- ный ответ с помощью минимум одного значения. Рассмотрим прак- тическую проблему, когда базовым случаем является пустое дерево.
Какое значение мы могли бы вернуть? Если мы возвращаем ноль, мы неявно требуем наличия в этом дереве нескольких положительных значений; если все значения в дереве отрицательные, то ноль будет ошибочно возвращен как наибольшее значение в дереве. Мы мог- ли бы решить эту проблему, возвращая наименьшее (самое отрица- тельное) целое число, но в этом случае нам бы пришлось осторожно адаптировать код для других числовых типов. Сделав базовым случа- ем единственный узел, мы полностью избегаем необходимости при- нятия этого решения.
Остальная часть кода проста. Мы используем рекурсию для на- хождения максимальных значений в левом
Z
и правом поддере-

Решение задач с помощью рекурсии 195
вьях
[
. Затем мы находим наибольшее из трех значений (значение в корневом узле, наибольшее значение в левом поддереве, наиболь- шее значение в правом поддереве), используя вариант алгоритма
«Царь горы», который мы использовали на протяжении всей этой книги
\
Функции-обертки
В предыдущих примерах в этой главе мы обсуждали только саму ре- курсивную функцию. Однако в некоторых случаях эту рекурсивную функцию требуется «настраивать» с помощью второй функции.
Чаще всего это происходит, когда мы пишем рекурсивные функции внутри структур классов. Это может привести к несоответствию между параметрами, необходимыми для рекурсивной функции, и па- раметрами, необходимыми для общедоступного метода класса. По- скольку классы обычно обеспечивают сокрытие информации, код клиента класса может не иметь доступа к данным или типам, кото- рый требуется рекурсивной функции. Эта проблема и ее решение показаны в следующем примере.
: 9
"
Для класса, реализующего двоичное дерево, добавьте общедоступный метод, кото- рый возвращает количество листьев (узлов без дочерних элементов) в дереве. Подсчет листьев должен выполняться с использованием рекурсии.
Давайте обрисуем схему того, как мог бы выглядеть этот класс, прежде чем мы попытаемся реализовать решение этой задачи. Для простоты мы будем включать только соответствующие части класса, игнорируя конструкторы, деструктор и даже методы, которые по- зволили бы нам построить дерево, чтобы сосредоточиться на нашем рекурсивном методе. class binaryTree {
public:
X int leafCount();
private:
struct binaryTreeNode {
int data;
binaryTreeNode * left;
binaryTreeNode * right;
};
typedef binaryTreeNode * treePtr;
treePtr _root;
};
Обратите внимание на то, что наша функция для подсчета ли- стьев не принимает параметров
X
. С точки зрения интерфейса это корректно. Рассмотрим образец вызова для ранее построенного объекта binaryTree bt:

196 Глава 6
int numLeaves = bt.leafCount();
В конце концов, если мы спрашиваем у дерева, сколько у него ли- стьев, то какую информацию мы могли бы предоставить этому объек- ту, которую он еще о себе не знает? Так же, как это является правиль- ным для интерфейса, это не является правильным для рекурсивной реализации. Если не существует параметра, что же меняется от одно- го рекурсивного вызова к другому? В этом случае ничто не может из- мениться, кроме как благодаря глобальным переменным, использо- вания которых, как говорилось ранее, следует избегать. Если ничего не изменяется, то для прогресса или прекращения рекурсии нет воз- можности.
Чтобы обойти эту проблему, нужно сначала написать рекурсив- ную функцию, концептуализируя ее как функцию вне класса. Дру- гими словами, мы напишем эту функцию для подсчета листьев в двоичном дереве в том же стиле, который мы использовали при на- писании функции для нахождения наибольшего значения в двоич- ном дереве. Единственным параметром, который нам необходимо передать, является указатель на нашу структуру узла.
Это дает нам еще одну возможность использовать БРИ. В чем за- ключается вопрос Q в данном случае? Сколько листьев в дереве? При- менение общего плана рекурсивной обработки двоичных деревьев к этой конкретной задаче приводит к следующей последовательности шагов.
1. Если корень дерева не имеет дочерних элементов, то дерево имеет только один узел. Этот узел является листом по определе- нию, поэтому возвратите 1. В противном случае...
2. Сделайте рекурсивный вызов для подсчета листьев в левом под- дереве.
3. Сделайте рекурсивный вызов для подсчета листьев в правом под- дереве.
4. В данном случае нет необходимости проверять корневой узел, поскольку, если мы добрались до этого этапа, значит, корневой узел не может быть листом. Поэтому...
5. Возвратите сумму значений, полученных на этапах 2 и 3.
Переведя этот план в код, мы получим следующее: struct binaryTreeNode {
int data;
binaryTreeNode * left;
binaryTreeNode * right;
};
typedef binaryTreeNode * treePtr;
int leafCount(treePtr rootPtr) {
if (rootPtr == NULL) return 0; if (rootPtr->right == NULL && rootPtr->left == NULL) return 1;
int leftCount = leafCount(rootPtr->left);

Решение задач с помощью рекурсии 197
int rightCount = leafCount(rootPtr->right);
return leftCount + rightCount;
}
Как вы можете видеть, код представляет собой прямой перевод пла- на. Вопрос в том, как мы переходим от этой независимой функции к тому, что мы можем использовать в классе? Именно здесь неосторож- ный программист может легко попасть в неприятности, посчитав, что нам нужно использовать глобальную переменную или сделать корневой указатель общедоступным. Нам не нужно этого делать; мы можем оста- вить все внутри класса. Трюк заключается в использовании функции-
обертки. Сначала мы помещаем независимую функцию с параметром treePtr в приватный раздел нашего класса. Затем мы пишем публичную функцию, которая будет служить «функцией-оберткой» для приватной функции. Поскольку публичная функция имеет доступ к приватному элементу данных _root, она может передать его рекурсивной функции, а затем возвратить клие нту результаты следующим образом: class binaryTree {
public:
int publicLeafCount();
private:
struct binaryTreeNode {
int data;
binaryTreeNode * left;
binaryTreeNode * right;
};
typedef binaryTreeNode * treePtr;
treePtr _root;
int privateLeafCount(treePtr rootPtr);
};
X int binaryTree::privateLeafCount(treePtr rootPtr) {
if (rootPtr == NULL) return 0;
if (rootPtr->right == NULL && rootPtr->left == NULL) return 1;
int leftCount = privateLeafCount(rootPtr->left);
int rightCount = privateLeafCount(rootPtr->right);
return leftCount + rightCount;
}
Y int binaryTree::publicLeafCount() {
Z return privateLeafCount(_root);
}
Несмотря на то, что язык C++ позволяет обеим функциям иметь одно и то же имя, для ясности я использовал разные имена, чтобы раз- личать публичную и приватную функции для «подсчета листьев». Код в функции privateLeafCount
X
точно повторяет код в нашей предыду- щей, независимой функции leafCount. Функция-обертка publicLeaf-
Count
Y
проста. Она вызывает функцию privateLeafCount, передавая приватный элемент данных _root, и возвращает результат
Z
. По сути, она стимулирует рекурсивный процесс. Функции-обертки очень по- лезны при написании рекурсивных функций внутри классов, однако их можно использовать в любое время при несоответствии между спи- ском параметров, которые требуются функции, и желаемым списком параметров вызывающей функции.

198 Глава 6
В каких случаях использовать рекурсию
Начинающие программисты часто задаются вопросом, зачем ис- пользовать рекурсию. Возможно, они уже узнали, что любую про- грамму можно создать, используя базовые управляющие структуры, такие как выбор (утверждения if) и итерация (циклы for и while).
Если рекурсию использовать труднее, чем базовые управляющие структуры, и она не является необходимой, возможно, ее следует просто игнорировать.
На этого существует несколько возражений. Во-первых, рекурсив- ное программирование помогает программистам думать рекурсивно, а рекурсивное мышление применяется повсюду в мире информатики в таких областях, как проектирование компилятора. Во-вторых, не- которые языки просто требуют использования рекурсии, поскольку в них отсутствуют некоторые элементарные управляющие структуры.
Чистые версии языка Lisp, например, требуют рекурсии почти в каж- дой нетривиальной функции.
Тем не менее остается вопрос: если программист изучил рекурсию достаточно для того, чтобы ее понять, и использует такой полнофунк- циональный язык, как C++, Java или Python, следует ли ему применять рекурсию? Имеет ли рекурсия практическую ценность в таких языках, или это просто упражнение для ума?
Аргументы против рекурсии
Чтобы изучить этот вопрос, давайте перечислим недостатки рекурсии.
Концептуальная сложность
В большинстве случаев среднему программисту бывает сложнее решить задачу с помощью рекурсии. Даже если вы понимаете
Большую Рекурсивную Идею, в большинстве ситуаций будет про- ще написать код с использованием циклов.
Производительность
Вызовы функций очень требовательны к ресурсам компьютера.
Рекурсия предусматривает множество вызовов функций и, сле- довательно, может приводить к замедлению работы системы.
Требования к пространству
Рекурсия не просто предусматривает много вызовов функций; она также вкладывает их один в другой. То есть в итоге вы мо- жете получить длинную цепочку вызовов функций, ожидающих завершения других вызовов. Каждый вызов функции, который начался, но еще не закончился, занимает дополнительное про- странство в системном стеке.
На первый взгляд этот список свойств представляет собой силь- ное обвинение против рекурсии, характеризуя ее как сложный, мед- ленный и требовательный к пространству метод. Тем не менее эти аргументы работают не во всех случаях. Поэтому самым базовым