Файл: Руководство по стилю программирования и конструированию по.pdf

ГЛАВА 17 Нестандартные управляющие структуры
385
Минимизируйте число возвратов из каждого метода Тяжело понять ло- гику метода, если при чтении его последних строк вы не подозреваете о возмож- ности выхода из него где-то вверху. По этой причине используйте операторы воз- врата благоразумно — только если они улучшают читабельность.
17.2. Рекурсия
При рекурсии метод решает небольшую часть задачи, разбивает задачу на мень- шие порции и вызывает сам себя для решения каждой из этих порций. Обычно рекурсию применяют, когда небольшую часть задачи легко решить, а саму задачу просто разложить на составные части.
Рекурсия не часто бывает необходима, но при аккуратном использова- нии она позволяет создавать элегантные решения, как в этом примере,
где алгоритм сортировки иллюстрирует отличное применение рекурсии:
Пример алгоритма сортировки, использующего рекурсию (Java)
void QuickSort( int firstIndex, int lastIndex, String [] names ) {
if ( lastIndex > firstIndex ) {
int midPoint = Partition( firstIndex, lastIndex, names );
Здесь выполняются рекурсивные вызовы.
QuickSort( firstIndex, midPoint-1, names );
QuickSort( midPoint+1, lastIndex, names )
}
}
В этом фрагменте алгоритм сортировки разрезает массив на две части и затем вызывает сам себя для сортировки каждой половины массива. Когда ему будет передан участок массива, слишком короткий для сортировки, т. е. когда
( lastIndex
<= firstIndex ), он перестанет вызывать сам себя.
Для малой группы задач рекурсия позволяет создать простые, элегантные реше- ния. Для несколько большей группы задач она позволяет создать простые, элегант- ные, трудные для понимания решения. Для большинства задач она создает исклю- чительно запутанные решения — в таких случаях использование простых итера- ций обычно более понятно. Поэтому применяйте рекурсию выборочно.
Примеры рекурсии
Допустим, у вас есть тип данных, представляющий лабиринт. Лабиринт — это обычно некая сетка, в узлах которой вы можете повернуть направо, налево, пере- меститься вверх или вниз. Часто существует возможность двигаться в нескольких направлениях.
Как вы будете разрабатывать программу для поиска пути через лабиринт (рис. 17-1)?
Если вы используете рекурсию, ответ довольно прост. Вы начинаете от входа и пробуете все возможные повороты, пока не найдете выхода. Попадая в точку в первый раз, вы пробуете повернуть налево, если это невозможно, то пробуете пойти вверх или вниз. В конце концов вы пытаетесь пойти направо. Вам не надо боять-
>

386
ЧАСТЬ IV Операторы ся заблудиться, потому что на каждом перекрестке вы оставляете несколько хлебных крошек и не поворачиваете в одну и ту же сторону дважды.
Рис. 17-1. Рекурсия может быть мощным оружием в борьбе со сложностью,
если используется по назначению
Рекурсивный код может выглядеть, например, так:
Пример рекурсивного перемещения по лабиринту (C++)
bool FindPathThroughMaze( Maze maze, Point position ) {
// Если это место уже исследовано, не надо снова его проверять.
if ( AlreadyTried( maze, position ) ) {
return false;
}
// Если это место и есть выход, объявляем успешное завершение.
if ( ThisIsTheExit( maze, position ) ) {
return true;
}
// Запоминаем, что это место исследовано.
RememberPosition( maze, position );
// Проверяем пути налево, вверх, направо, вниз;
// если один из путей приводит к успеху, прекращаем поиск.
if ( MoveLeft( maze, position, &newPosition ) ) {
if ( FindPathThroughMaze( maze, newPosition ) ) {
return true;
}
}
if ( MoveUp( maze, position, &newPosition ) ) {
if ( FindPathThroughMaze( maze, newPosition ) ) {
return true;
}
}

ГЛАВА 17 Нестандартные управляющие структуры
387
if ( MoveDown( maze, position, &newPosition ) ) {
if ( FindPathThroughMaze( maze, newPosition ) ) {
return true;
}
}
if ( MoveRight( maze, position, &newPosition ) ) {
if ( FindPathThroughMaze( maze, newPosition ) ) {
return true;
}
}
return false;
}
Первая строка кода проверяет, исследована ли уже данная точка. Одна из ключе- вых задач рекурсивного метода — предотвращение бесконечной рекурсии. В дан- ном случае, если вы не будете проверять, что эта развилка уже исследовалась, вы можете бесконечно обследовать ее.
Второе выражение проверяет, не является ли эта позиция выходом из лабиринта.
Если
ThisIsTheExit() возвращает true, метод тоже возвращает true.
Третье выражение запоминает, что вы посетили данную точку. Это предотвраща- ет бесконечную рекурсию, которая может возникнуть в результате замкнутого пути.
Остальные строки пытаются найти выход при движении налево, вверх, вниз и направо. Рекурсия прекратится, если метод когда-нибудь вернет
true, т. е. будет найден выход из лабиринта.
Логика, используемая в этом примере, довольно прямолинейна. Большинство людей испытывают некоторый дискомфорт при виде рекурсивных методов, ссылающихся сами на себя. Однако в данном случае альтернативное решение было бы гораздо более трудоемким, и поэтому рекурсия отлично подходит.
Советы по использованию рекурсии
При применении рекурсии имейте в виду эти советы.
Убедитесь, что рекурсия остановится Проверьте метод, чтобы убедиться,
что он включает нерекурсивный путь. Обычно это значит, что в методе присут- ствует проверка, останавливающая дальнейшую рекурсию, когда в ней отпадает необходимость. В примере с лабиринтом условия для
AlreadyTried() и ThisIsTheExit()
гарантируют, что рекурсия остановится.
Предотвращайте бесконечную рекурсию с помощью
счетчиков безопасности Если вы применяете рекурсию в ситуации, не позволяющей сделать простую проверку вро- де описанной выше, добавьте счетчики безопасности, дабы избежать бесконечной рекурсии. Счетчиком должна быть такая переменная, которая не будет создаваться при каждом вызове метода. Используйте переменную-член класса или передавайте счетчик бе- зопасности в виде параметра. Приведем пример:
Рекурсивная процедура должна иметь возможность изменять значение safetyCounter, поэтому в Visual Basic она объявляется как ByRef-параметр.

388
ЧАСТЬ IV Операторы
Пример использования счетчика безопасности для предотвращения бесконечной
рекурсии (Visual Basic)
Public Sub RecursiveProc( ByRef safetyCounter As Integer )
If ( safetyCounter > SAFETY_LIMIT ) Then
Exit Sub
End If safetyCounter = safetyCounter + 1
RecursiveProc( safetyCounter )
End Sub
В данном случае, если вложенность превысит предел счетчика безопасности, ре- курсия прекратится.
Если вы не хотите передавать счетчик безопасности в виде отдельного парамет- ра, можно использовать классовую переменную в C++, Java, Visual Basic или соот- ветствующий эквивалент в других языках.
Ограничьте рекурсию одним методом Циклическая рекурсия (A вызывает B
вызывает C вызывает A) представляет опасность, потому что ее сложно обнару- жить. Осмысление рекурсии в одном методе — достаточно трудоемкое занятие, а понимание рекурсии, охватывающей несколько методов, — это уже слишком. Если возникла циклическая рекурсия, обычно можно так перепроектировать методы,
что рекурсия будет ограничена одним из них. Если это не получается, а вы все равно считаете, что рекурсия — это лучший подход, используйте счетчики безо- пасности в качестве страховки.
Следите за стеком При использовании рекурсии вы точно не знаете, сколько места в стеке будет занимать ваша программа. Кроме того, тяжело заранее пред- сказать, как будет вести себя программа во время выполнения. Однако вы можете предпринять некоторые усилия для контроля ее поведения.
Во-первых, если вы добавили счетчик безопасности, одним из принципов уста- новки его предела является возможный размер используемого стека. Сделайте этот предел достаточно низким, чтобы предотвратить переполнение стека.
Во-вторых, следите за выделением памяти для локальных переменных в рекурсив- ных функциях, особенно если эти переменные достаточно объемны. Иначе го- воря, лучше использовать
new для создания объектов в куче, чем позволять ком- пилятору генерировать автоматические объекты в стеке.
Не используйте рекурсию для факториалов и чисел Фибоначчи Одна из проблем с учебниками по вычислительной технике в том, что они предлагают глупые примеры рекурсии. Типичными примерами являются вычисление факто- риала или последовательности Фибоначчи. Рекурсия — мощный инструмент, и очень глупо использовать ее в этих двух случаях. Если бы программист, работаю- щий у меня, применял рекурсию для вычисления факториала, я бы нанял кого-то другого. Вот рекурсивная версия вычисления факториала:

ГЛАВА 17 Нестандартные управляющие структуры
389
Пример неправильного решения: вычисления
факториала с помощью рекурсии (Java)
int Factorial( int number ) {
if ( number == 1 ) {
return 1;
}
else {
return number * Factorial( number - 1 );
}
}
Не считая медленного выполнения и непредсказуемого использования памяти,
рекурсивный вариант функции трудней для понимания, чем итеративный вариант:
Пример правильного решения: использование
итераций для вычисления факториала (Java:)
int Factorial( int number ) {
int intermediateResult = 1;
for ( int factor = 2; factor <= number; factor++ ) {
intermediateResult = intermediateResult * factor;
}
return intermediateResult;
}
Из этого примера можно усвоить три урока. Первый: учебники по ВычТеху не оказывают миру услугу своими примерами рекурсии. Второй, и более важный:
рекурсия — гораздо более мощный инструмент, чем можно предположить из сби- вающих с толку примеров расчета факториала и чисел Фибоначчи. Третий — са- мый важный: вы должны рассмотреть альтернативные варианты перед использо- ванием рекурсии. Иногда один способ работает лучше, иногда — другой. Но прежде чем выбрать какой-то один, надо рассмотреть оба.
17.3. Оператор goto
Вы могли думать, что дебаты вокруг
goto утихли, но корот- кая экскурсия по современным репозиториям исходного кода,
таким как
SourceForge.net, показывает, что goto все еще жив- здоров и глубоко укоренился на сервере вашей компании. Более того, современ- ные эквиваленты обсуждения
goto до сих пор возникают под разными личинами,
включая дебаты о множественных возвратах из методов, множественных выходах из цикла, именованных выходах из цикла, обработке ошибок и исключений.
Аргументы против goto
Основной аргумент против
goto состоит в том, что код без goto — более качествен- ный. Знаменитое письмо Дейкстры «Go To Statement Considered Harmful» («Обо- снование пагубности оператора go to») в мартовском номере «Communications of the ACM» 1968 г. положило начало дискуссии. Дейкстра отметил, что качество кода http://cc2e.com/1785

390
ЧАСТЬ IV Операторы обратно пропорционально количеству
goto, использованных программистом.
В последующих работах Дейкстра утверждал, что корректность кода, не содержа- щего
goto, доказать легче.
Код с операторами
goto трудно форматировать. Для демонстрации логической структуры используются отступы, а
goto влияет на логическую структуру. Однако использовать отступы, чтобы показать логику
goto и места его перехода, сложно или даже невозможно.
Применение
goto препятствует оптимизации, выполняемой компилятором. Неко- торые виды оптимизации зависят от порядка выполнения нескольких выражений подряд. Безусловный переход
goto усложняет анализ кода и уменьшает возмож- ность оптимизации кода компилятором. Таким образом, даже если применение
goto увеличивает эффективность на уровне исходного кода, суммарный эффект из-за невозможности оптимизации может уменьшиться.
Сторонники операторов
goto иногда приводят довод, что они делают программу быстрее и проще. Но код, содержащий
goto, обычно не самый быстрый и корот- кий из всех возможных. Изумительная классическая статья Дональда Кнута «Struc- tured Programming with go to Statements» («Структурное программирование и операторы go to») содержит несколько примеров, в которых применение
goto
приводит к более медленному и объемному коду (Knuth, 1974).
На практике применение операторов
goto приводит к нарушению принципа, что нормальный ход алгоритма должен быть строго сверху вниз. Даже если
goto при аккуратном использовании не сбивают с толку, как только они появляются, они начинают распространяться по коду, как термиты по разрушающемуся дому. Если разрешен хотя бы один
goto, вместе с пользой в код проникает и вред, так что лучше вообще запретить использование этого оператора.
В целом опыт двух десятилетий, прошедших с публикации письма Дейкстры по- казал всю недальновидность создания кода, перегруженного операторами
goto.
В своем обзоре литературы Бен Шнейдерман (Ben Shneiderman) сделал вывод, что факты свидетельствуют в пользу Дейкстры и нам лучше обходиться без
goto (1980),
а многие современные языки, включая Java, даже не содержат такой оператор.
Аргументы в защиту goto
Сторонники
goto ратуют за осторожное применение оператора при определенных обстоятельствах, а не за неразборчивое употребление. Большинство аргументов против
goto говорит именно о неразборчивом его использовании. Дискуссия о goto
вспыхнула, когда Fortran был наиболее популярным языком. Fortran не имел при- личных циклов, и в отсутствие хорошего совета по поводу создания цикла с помо- щью
goto программисты написали кучу спагетти-кода. Такой код, несомненно, кор- релировал с выпуском низкокачественных программ, но это имело отдаленное отношение к аккуратному использованию
goto, позволяющему заполнить пробел в возможностях, предоставляемых современными языками программирования.
Правильно расположенный
goto способен помочь избавиться от дублирования кода.
Такой код создает проблемы, если две его части модифицируются по-разному. Дуб- лированный код увеличивает размер исходного и выполняемого файлов. Отри-