Антон Спрол - Думай как программист: креативный подход к созданию кода. С++ версия

Когда мы объявляем стек X, то указываем тип элементов, которые собираемся в нем
хранить. В данном случае мы будем хранить указатели на структуру
binaryTreeNode Y. В этом коде мы будем использовать четыре метода класса stack. Метод push Z помещает элемент (в данном случае
указатель на узел) на вершину стека. Метод empty [ говорит нам,
остались ли в стеке какие-либо элементы. Метод top \ предоставляет нам копию элемента на вершине стека, а метод pop ] удаляет
верхний элемент из стека.
Данный код решает задачу, помещая на стек указатель на первый узел, а затем последовательно удаляя из стека указатель на узел,

Решение задач с помощью рекурсии

199

проверяя, является ли он листом, увеличивая счетчик на 1, если это
так, и помещая на стек указатели на дочерние узлы, если они существуют. Таким образом, стек отслеживает узлы, которые мы обнаружили, но еще не обработали, так же, как цепочка рекурсивных вызовов в рекурсивной версии отслеживает узлы, которые мы должны
повторно посетить. Сравнивая эту итеративную версию с рекурсивной, мы видим, что ни одно из стандартных возражений против рекурсии не имеет в данном случае достаточной силы. Во-первых, этот
код длиннее и сложнее, чем его рекурсивная версия, поэтому против рекурсивной версии нельзя выдвинуть аргумент, связанный с
концептуальной сложностью. Во-вторых, посмотрите, сколько вызовов функций совершает stackBasedCountLeaves — на каждое посещение внутреннего узла (то есть узла, который не является листом)
эта функция совершает до пяти вызовов функций: по одному для методов empty, top и pop и один или два для метода push. Рекурсивная
версия совершает только два рекурсивных вызова для каждого внутреннего узла. (Обратите внимание на то, что мы можем избежать
вызовов функцией объекта стека, включив в функцию логику стека.
Однако это еще больше увеличит сложность функции.) В-третьих,
хотя эта итеративная версия не использует дополнительное пространство системного стека, она явно использует приватный стек.
Справедливости ради следует сказать, что при этом расход пространства меньше, чем расход пространства системного стека при рекурсивных вызовах, однако это по-прежнему расходование системной
памяти, пропорциональное максимальной глубине двоичного дерева, которое мы обходим.
Поскольку в данной ситуации возражения против рекурсии
смягчаются или сводятся к минимуму, рекурсия — хороший выбор для решения этой задачи. В общем случае, если задачу легко
решить итеративно, то итерация должна быть вашим первым выбором. Рекурсию следует использовать, когда решение с помощью
итерации представляется сложным. Часто это требует использования описанного здесь механизма создания «тропы из хлебных крошек». Обход ветвящихся структур, таких как деревья и графы, по
своей сути рекурсивен. Обработка линейных структур, таких как
массивы и связные списки, обычно не требует рекурсии, однако существуют исключения. Вы никогда не ошибетесь, если начнете решать задачу с помощью итерации и посмотрите, как далеко вас это
заведет. В качестве последних примеров рассмотрим следующие задачи со связными списками.
:  
 D"      
"" 
Напишите функцию, которой передается указатель на головной элемент односвязного
списка, где типом данных каждого узла является целое число, и которая отображает
эти целые числа по одному на строке в порядке их следования в списке.

200

Глава 6

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

Поскольку эти задачи являются зеркальными версиями друг
друга, естественно предположить, что их решения также будут зеркальными. Это действительно так в случае рекурсивных реализаций. Далее приведены рекурсивные функции для решения обеих
этих задач с использованием приведенных ранее типов listNode и
listPtr:
void displayListForwardsRecursion(listPtr head) {
if (head != NULL) {
X cout data next);
}
}
void displayListBackwardsRecursion(listPtr head) {
if (head != NULL) {
Z displayListBackwardsRecursion(head->next);
[ cout data next)
cout data next)
nodes.push(current);
[ while (!nodes.empty()) {
\ nodePtr current = nodes.top();
] nodes.pop();
^ cout data 0) {
total += array[i];
positiveCount++;
}
}
X return total / (double) positiveCount;
}

Думайте как программист

235

На первый взгляд эта --">