Файл: Think likea programmer.pdf

186 Глава 6
int
XarraySumRecursive(int integers[], int size) {
if (size == 0) return 0;
int lastNumber = integers[size — 1];
int allButLastSum =
YarraySumRecursive(integers, size — 1);
return lastNumber + allButLastSum;
}
В предыдущий код были внесены только два изменения. Имя функ- ции было изменено для лучшего описания ее новой формы
X
, и теперь функция вызывает сама себя там, где ранее она вызывала итеративную функцию
Y
. Логика функций arraySumDelegate и arraySumRecursive одинакова. Каждая функция проверяет тривиальный случай, когда сум- ма уже известна, в данном примере это массив размером 0 с суммой эле- ментов равной 0. В противном случае каждая функция вычисляет сум- му значений в массиве, вызывая функцию для вычисления суммы всех значений, кроме последнего. Наконец, каждая функция добавляет это последнее значение к возвращенной общей сумме. Разница лишь в том, что первая версия функции вызывает другую функцию, в то время как рекурсивная версия вызывает саму себя. БРИ говорит нам о том, что если мы будем следовать изложенным выше правилам написания дис- петчера, то сможем проигнорировать это различие.
Вам не обязательно буквально следовать всем приведенным выше шагам для реализации БРИ. В частности, вы обычно не будете при- менять итерационное решение задачи до реализации рекурсивного решения. Написание итеративной функции в качестве одного из эта- пов — это дополнительная работа, которая в конечном итоге будет от- брошена. Кроме того, рекурсия лучше всего применима к ситуациям, в которых итерационное решение трудно реализуемо, о чем мы пого- ворим далее. Тем не менее вы можете следовать схеме БРИ без факти- ческого написания итерационного решения. Ключ в том, чтобы рас- сматривать рекурсивный вызов в качестве вызова другой функции, независимо от свойств этой функции. Таким образом, вы устраняете сложности рекурсивной логики из рекурсивного решения.
Распространенные ошибки
Как показано выше, при правильном подходе рекурсивные реше- ния часто могут быть очень легки в написании. Однако так же легко можно придумать неправильную рекурсивную реализацию, либо ре- курсивное решение, которое «работает», но является неуклюжим.
Большинство проблем рекурсивной реализации связано с двумя ос- новными ошибками: чрезмерным обдумыванием задачи или началом реализации при отсутствии четкого плана.
Чрезмерное обдумывание рекурсивных задач свойственно про- граммистам-новичкам, поскольку ограниченный опыт и недостаток уверенности при работе с рекурсией заставляют их считать задачу бо- лее сложной, чем она есть на самом деле. Код, полученный в резуль- тате такого чрезмерного обдумывания, легко узнать по его слишком

Решение задач с помощью рекурсии 187
аккуратному виду. Например, рекурсивная функция может иметь не- сколько особых случаев, когда ей требуется только один.
Слишком раннее начало реализации может привести к чрезмер- но сложному, «заумному» коду, где непредвиденные взаимодействия приводят к необходимости внесения поправок в исходный код.
Давайте рассмотрим некоторые конкретные ошибки и способы их избежать.
Слишком много параметров
Метод головной рекурсии может уменьшить количество данных, пере- дающихся рекурсивному вызову, тогда как метод хвостовой рекурсии может привести к передаче рекурсивному вызову дополнительных дан- ных. Программисты часто застревают на хвостовой рекурсии, потому что слишком много думают и слишком рано приступают к реализации.
Рассмотрим нашу задачу рекурсивного вычисления суммы элемен- тов целочисленного массива. При написании итеративного решения этой задачи программист знает, что потребуется переменная с «про- межуточной суммой» (в предлагаемом итеративном решении я назвал ее sum) и что значения массива будут суммироваться, начиная с пер- вого элемента. Учитывая рекурсивное решение, программист, есте- ственно, представляет себе реализацию, которая наиболее непосред- ственным образом отражает итерационное решение с переменной, в которой хранится промежуточная сумма, и рекурсивным вызовом, об- рабатывающим первый элемент в массиве. Однако этот подход требу- ет того, чтобы рекурсивная функция сообщала значение промежуточ- ной суммы и место, где следующий рекурсивный вызов должен начать обработку. Такое решение будет выглядеть следующим образом: int arraySumRecursiveExtraParameters(int integers[],
Xint size, Yint sum, int currentIndex) {
if (currentIndex == size) return sum;
sum += integers[currentIndex];
return arraySumRecursiveExtraParameters(integers, size, sum,currentIndex
+ 1);
}
Этот код так же короток, как и другая рекурсивная версия, но зна- чительно более сложный семантически из-за дополнительных пара- метров, sum
X
и currentIndex
Y
. С точки зрения клиентского кода, до- полнительные параметры не важны и всегда должны иметь значение
0 в вызове, как показано в этом примере: int a[10] = {20, 3, 5, 22, 7, 9, 14, 17, 4, 9};
int total = arraySumRecursiveExtraParameters(a, 10, 0, 0);
Эту проблему можно обойти с помощью функции-обертки, как опи- сано в следующем разделе, однако поскольку мы не можем полно- стью устранить данные параметры, это не лучшее решение. Итера- тивная функция для этой задачи и исходная рекурсивная функция отвечают на вопрос относительно суммы значений массива с данным

188 Глава 6
количеством элементов. Напротив, у второй рекурсивной функции спрашивается, какова сумма значений этого массива, если он содер- жит столько-то элементов, мы начинаем с такого-то конкретного эле- мента и имеем такую-то сумму всех предшествующих элементов.
Проблему чрезмерного количества параметров можно обойти, если выбрать параметры своей функции до обдумывания рекурсии.
Другими словами, заставьте себя использовать тот же список параме- тров, что и в том случае с итеративным решением. Если вы используе- те полный процесс БРИ и на самом деле сначала пишите итеративную функцию, то сможете автоматически избежать этой проблемы. Однако если вы не реализуете весь процесс формально, вы все равно сможете использовать эту идею концептуально, если выпишете список параме- тров, имея в виду итеративную функцию.
Глобальные переменные
Избегая чрезмерного количества параметров, программисты иногда совершают другую ошибку — используют глобальные переменные для передачи данных от одного рекурсивного вызова другому. Использова- ние глобальных переменных, как правило, является плохой практикой программирования, хотя иногда это допустимо из соображений произ- водительности. Использования глобальных переменных в рекурсивных функциях следует избегать, насколько это возможно. Давайте рассмо- трим конкретную задачу, чтобы увидеть, как программисты убеждают сами себя совершить эту ошибку. Предположим, нас попросили напи- сать рекурсивную функцию, которая подсчитывает количество нулей в целочисленном массиве. Эту задачу легко решить с помощью итерации: int zeroCountIterative(int numbers[], int size) {
X int count = 0;
for (int i = 0; i < size; i++) {
if (numbers[i] == 0) count ++;
}
return count;
}
Логика этого кода проста. Мы просто просматриваем массив от первого до последнего элемента, подсчитывая при этом нули и исполь- зуя локальную переменную, count
X
, в качестве трекера. Однако если мы имеем в виду подобную функцию при написании рекурсивной функ- ции, то можем предположить, что нам нужна переменная-трекер и в этой версии кода. Мы не можем просто объявить count в качестве ло- кальной переменной в рекурсивной версии, поскольку тогда это будет новая переменная в каждом рекурсивном вызове. Поэтому у нас может возникнуть соблазн объявить ее глобальной переменной: int count;
int zeroCountRecursive(int numbers[], int size) {
if (size == 0) return count;
if (numbers[size — 1] == 0) count++;
zeroCountRecursive(numbers, size — 1);
}

Решение задач с помощью рекурсии 189
Этот код работает, однако глобальная переменная совершенно не нужна и вызывает все проблемы, которые обычно возникают из-за гло- бальных переменных, такие как плохая читаемость и усложнение об- служивания кода. Некоторые программисты могут попытаться облег- чить эту проблему, сделав переменную локальной, но статической: int zeroCountStatic(int numbers[], int size) {
X static int count Y= 0;
if (size == 0) return count;
if (numbers[size — 1] == 0) count++;
zeroCountStatic(numbers, size — 1);
}
В языке C++ локальная переменная, объявленная как статическая, сохраняет свое значение от одного вызова функции к другому; таким образом, локальная статическая переменная count
X
будет действовать так же, как глобальная переменная в предыдущей версии. Так в чем про- блема? Инициализация этой переменной нулем
Y
происходит только при первом вызове функции. Это необходимо для того, чтобы объявле- ние static было полезным, однако это означает, что функция вернет правильный ответ только при первом вызове. Если эту функцию вызы- вать дважды — сначала с массивом, в котором содержится три нуля, а затем с массивом, в котором содержится пять нулей то функция вернет значение 8 для второго массива, поскольку значение переменной count будет начинаться с того места, где оно остановилось.
В данном случае, чтобы избежать использования глобальной пере- менной, можно применить БРИ. Мы можем предположить, что рекур- сивный вызов с меньшим значением size вернет правильный резуль- тат и на его основе вычислит правильное значение для всего массива.
Это приведет к решению, предполагающему головную рекурсию: int zeroCountRecursive(int numbers[], int size) {
if (size == 0) return 0;
X int count = zeroCountRecursive(numbers, size — 1);
Y if (numbers[size — 1] == 0) count++;
Z return count;
}
В этой функции у нас все еще есть локальная переменная, count
X
, но здесь не делается попытки сохранить ее значение от одного вызова к другому. Вместо этого в этой переменной сохраняется значение, воз- вращаемое из нашего рекурсивного вызова; мы при необходимости инкрементируем эту переменную
Y
перед ее возвращением
Z
Применение рекурсии к динамическим
структурам данных
Рекурсия часто применяется к таким динамическим структурам, как связные списки, деревья и графы. Чем сложнее структура, тем боль- ше процесс кодирования может выиграть от применения рекурсив- ного решения. Зачастую обработка сложных структур напоминает

190 Глава 6
поиск пути сквозь лабиринт, а рекурсия позволяет нам возвращаться к предыдущим этапам нашего процесса обработки.
Рекурсия и связные списки
Начнем с самой простой из динамических структур — со связного спи- ска. Для целей обсуждения, приведенного в этом разделе, предполо- жим, что у нас есть простейшая структура узлов для нашего связного списка — всего один тип данных int. Вот наши объявления типов: struct listNode {
int data;
listNode * next;
};
typedef listNode * listPtr;
Применение БРИ к односвязному списку следует той же общей схеме вне зависимости от конкретной задачи. Рекурсия требует от нас разделения задачи, чтобы мы могли передать рекурсивному вы- зову уменьшенную версию исходной задачи. Существует только один практический способ разделения односвязного списка — на первый узел в списке и остальную часть списка.
На рис. 6.5 мы видим пример списка, разделенного на неравные части: первый узел и остальные узлы. Концептуально мы можем рас- сматривать «остальную часть» исходного списка как отдельный спи- сок, начинающийся со второго узла исходного списка. Именно эта точка зрения обеспечивает гладкую работу рекурсии.
Рис. 6.5. Список, разделенный на первый узел и «остальную часть списка»
Опять же, нам необязательно изображать все этапы рекурсии, чтобы обеспечить ее работу. С точки зрения того, кто пишет рекур- сивную функцию для обработки связного списка, это может быть концептуализировано как первый узел, с которым нам приходится иметь дело, и остальная часть списка, с которой мы не будем рабо- тать и, следовательно, не обращаем на нее внимание. Такое отноше- ние изображено на рис. 6.6.
Рис. 6.6. Список, изображенный так, как его должен представлять программист, использу-
ющий рекурсию: первый узел и «остальная часть списка» в виде туманной формы, переда-
ваемой рекурсивному вызову
Обеспечив таким образом разделение труда, мы можем сказать, что рекурсивная обработка односвязных списков будет происходить

Решение задач с помощью рекурсии 191
в соответствии со следующим общим планом. При наличии связного списка L и вопроса Q...
1. При минимальном L мы напрямую присваиваем значение по умолчанию. В противном случае...
2. Используем рекурсивный вызов для получения ответа на Q для
«остального» списка L (списка, начинающегося со второго узла L).
3. Проверяем значение в первом узле L.
4. Используем результаты предыдущих двух шагов, чтобы ответить на Q для всего L.
Как вы можете видеть, это прямое применение БРИ с учетом практических ограничений на разбиение связного списка. Теперь давайте применим этот план к конкретной задаче.
: & # 9
"
Напишите рекурсивную функцию, которой дан односвязный список с целочисленным типом данных. Функция должна возвращать количество отрицательных чисел в этом списке.
Вопрос Q, на который мы хотим ответить: сколько отрицатель- ных чисел в списке? Поэтому наш план можно сформулировать так.
1. Если в списке нет узлов, значением по умолчанию является 0.
В противном случае...
2. Используем рекурсивный вызов для подсчета количества отри- цательных чисел в «остальной части» списка.
3. Смотрим, является ли значение в первом узле списка отрица- тельным.
4. Используем результаты предыдущих двух шагов, чтобы опреде- лить количество отрицательных чисел во всем списке.
5. Ниже показана реализация функции, непосредственно вытекаю- щая из данного плана: int countNegative(listPtr head) {
if (head == NULL) return 0;
int listCount = countNegative(head->next);
if (head->data < 0) listCount++;
return listCount;
}
Обратите внимание на то, что этот код следует тем же принци- пам, что и код в предыдущих примерах. Он будет подсчитывать от- рицательные числа «в обратном направлении», от конца списка к его началу. Также обратите внимание на то, что в коде используется метод головной рекурсии; мы обрабатываем «остальную часть» спи- ска перед обработкой первого узла. Как и прежде, это позволяет нам