Книги
чёрным по белому
Главное меню
Главная О нас Добавить материал Поиск по сайту Карта книг Карта сайта
Книги
Археология Архитектура Бизнес Биология Ветеринария Военная промышленность География Геология Гороскоп Дизайн Журналы Инженерия Информационные ресурсы Искусство История Компьютерная литература Криптология Кулинария Культура Лингвистика Математика Медицина Менеджмент Металлургия Минералогия Музыка Научная литература Нумизматика Образование Охота Педагогика Политика Промышленные производства Психология Путеводители Религия Рыбалка Садоводство Саморазвитие Семиотика Социология Спорт Столярное дело Строительство Техника Туризм Фантастика Физика Футурология Химия Художественная литература Экология Экономика Электроника Энергетика Этика Юриспруденция
Новые книги
Цуканов Б.И. "Время в психике человека" (Медицина)

Суворов С. "Танк Т-64. Первенец танков 2-го поколения " (Военная промышленность)

Нестеров В.А. "Основы проэктирования ракет класса воздух- воздух и авиационных катапульных установок для них" (Военная промышленность)

Фогль Б. "101 вопрос, который задала бы ваша кошка своему ветеринару если бы умела говорить" (Ветеринария)

Яблоков Н.П. "Криминалистика" (Юриспруденция)
Реклама

Совершенный код. Мастер-класс - Макконнелл С.

Макконнелл С. Совершенный код. Мастер-класс — М.: Русская редакция, 2005. — 896 c.
ISBN: 5-469-00822-3
Скачать (прямая ссылка): soversheniykodmasterklass2005.djvu
Предыдущая << 1 .. 187 188 189 190 191 192 < 193 > 194 195 196 197 198 199 .. 426 >> Следующая

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;
}
Первая строка кода проверяет, исследована ли уже данная точка.
Одна из ключевых задач рекурсивного метода - предотвращение
бесконечной рекурсии. В данном случае, если вы не будете
проверять, что эта развилка уже исследовалась, вы можете
бесконечно обследовать ее.
Второе выражение проверяет, не является ли эта позиция выходом
из лабиринта. Если ThisIsTheExitQ возвращает true, метод тоже
возвращает true.
Третье выражение запоминает, что вы посетили данную точку. Это
предотвращает бесконечную рекурсию, которая может возникнуть в
результате замкнутого пути.
Остальные строки пытаются найти выход при движении налево,
вверх, вниз и направо. Рекурсия прекратится, если метод когда-
нибудь вернет true, т. е. будет найден выход из лабиринта.
Логика, используемая в этом примере, довольно прямолинейна.
Большинство людей испытывают некоторый дискомфорт при виде
рекурсивных методов, ссылающихся сами на себя. Однако в данном
случае альтернативное решение было бы гораздо более
трудоемким, и поэтому рекурсия отлично подходит.
Советы по использованию рекурсии
При применении рекурсии имейте в виду эти советы.
Убедитесь, что рекурсия остановится Проверьте метод, чтобы
убедиться, что он включает нерекурсивный путь. Обычно это
значит, что в методе присутствует проверка, останавливающая
дальнейшую рекурсию, когда в ней отпадает необходимость. В
примере с лабиринтом условия для AlreadyTried() и
ThisIsTheExitO гарантируют, что рекурсия остановится.
Предотвращайте бесконечную рекурсию с помощью
J " Рекурсивная процедура
должна
счетчиков безопасности Если вы применяете рекурсию тш
возможность ишенять
в ситуации, не позволяющей сделать простую проверку вро-
значение safetyCounter,
поэтому
де описанной выше, добавьте счетчики безопасности, дабы a
Visual Basic она э&ятотвя
избежать бесконечной рекурсии. Счетчиком должна быть к*к
Byft&n&pawtp*
такая переменная, которая не будет создаваться при каждом
вызове метода. Используйте переменную-член класса или
передавайте счетчик безопасности в виде параметра. Приведем
пример:
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 или соответствующий эквивалент в
других языках.
Ограничьте рекурсию одним методом Циклическая рекурсия (А
вызывает В вызывает С вызывает А) представляет опасность,
потому что ее сложно обнаружить. Осмысление рекурсии в одном
методе - достаточно трудоемкое занятие, а понимание рекурсии,
охватывающей несколько методов, - это уже слишком. Если
возникла циклическая рекурсия, обычно можно так
перепроектировать методы, что рекурсия будет ограничена одним
из них. Если это не получается, а вы все равно считаете, что
рекурсия - это лучший подход, используйте счетчики безо-
пасности в качестве страховки.
Следите за стеком При использовании рекурсии вы точно не
знаете, сколько места в стеке будет занимать ваша программа.
Кроме того, тяжело заранее предсказать, как будет вести себя
программа во время выполнения. Однако вы можете предпринять
некоторые усилия для контроля ее поведения.
Во-первых, если вы добавили счетчик безопасности, одним из
принципов установки его предела является возможный размер
используемого стека. Сделайте этот предел достаточно низким,
чтобы предотвратить переполнение стека.
Во-вторых, следите за выделением памяти для локальных
переменных в рекурсивных функциях, особенно если эти
переменные достаточно объемны. Иначе говоря, лучше
Предыдущая << 1 .. 187 188 189 190 191 192 < 193 > 194 195 196 197 198 199 .. 426 >> Следующая