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

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

197

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

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

Глава 6

правилом для выбора между рекурсией и итерацией является следующее: выбирайте рекурсию, когда эти аргументы не работают.
Рассмотрим нашу функцию, которая подсчитывает количество
листьев в двоичном дереве. Как бы вы решили эту задачу без рекурсии? Это возможно, но вам бы понадобился явный механизм для поддержания «тропы из хлебных крошек» для обозначения узлов, дочерние элементы которых в левом поддереве уже были посещены,
а в правом — нет. К этим узлам пришлось бы вернуться в какой-то
момент, чтобы иметь возможность посетить дочерние элементы в
правом поддереве. Вы могли бы хранить эти узлы в такой динамической структуре, как стек. Для сравнения далее приведена реализация
функции, которая использует класс stack из стандартной библиотеки шаблонов C++:
int binaryTree::stackBasedCountLeaves() {
if (_root == NULL) return 0;
int leafCount = 0;
Xstack< YbinaryTreeNode *> nodes;
Znodes.push(_root);
while ([!nodes.empty()) {
treePtr currentNode = \nodes.top();
]nodes.pop();
if (currentNode->left == NULL && currentNode->right == NULL)
leafCount++;
else {
if (currentNode->right != NULL) wnodes.push(currentNode->right);
if (currentNode->left != NULL) wnodes.push(currentNode->left);
}
}
return leafCount;
}

Этот код следует той же схеме, что и оригинал, однако, если
вы никогда раньше не использовали класс stack, здесь будут уместны некоторые комментарии. Класс stack работает как системный
стек, который мы обсуждали в главе 3; вы можете добавлять и удалять элементы только на вершине. Обратите внимание на то, что
мы могли бы выполнить операцию подсчета листьев, используя любую структуру данных, которая не имеет фиксированного размера.
Например, мы могли бы использовать вектор, однако использование стека лучше всего отражает исходный код. --">