Главная - Литература

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 [127] 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294

17.2. Рекурсия

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

Рекурсия не часто бывает необходима, но при аккуратном использовании она позволяет создавать элегантные решения, как в этом примере, где алгоритм сортировки иллюстрирует отличное применение рекурсии:

Пример алгоритма сортировки, использующего рекурсию (Java)

void QuickSort( int firstlndex, int lastlndex, String [] names ) { if ( lastlndex > firstlndex ) {

int midPoint - Partition( firstlndex, lastlndex, names );

- Здесь выполняются рекурсивные вызовы.

•-Г QuickSort( firstlndex, midPoint-1, names );

QuickSort( midPoint+1, lastlndex, names )

В этом фрагменте алгоритм сортировки разрезает массив на две части и затем вызывает сам себя для сортировки каждой половины массива. Когда ему будет передан участок массива, слишком короткий для сортировки, т. е. когда (lastlndex <= firstlndex), он перестанет вызывать сам себя.

Для малой группы задач рекурсия позволяет создать простые, элегантные решения. Для несколько большей группы задач она позволяет создать простые, элегантные, трудные для понимания решения. Для большинства задач она создает исключительно запутанные решения - в таких случаях использование простых итераций обычно более понятно. Поэтому применяйте рекурсию выборочно.

Примеры рекурсии

Допустим, у вас есть тип данных, представляющий лабиринт. Лабиринт - это обычно некая сетка, в узлах которой вы можете повернуть направо, налево, переместиться вверх или вниз. Часто существует возможность двигаться в нескольких направлениях.

Как вы будете разрабатьтать программу для поиска пути через лабиринт (рис. 17-1)? Если вы используете рекурсию, ответ довольно прост. Вы начинаете от входа и пробуете все возможные повороты, пока не найдете выхода. Попадая в точку в первый раз, вы пробуете повернуть налево, если это невозможно, то пробуете пойти вверх или вниз. В конце концов вы пытаетесь пойти направо. Вам не надо боять-

Минимизируйте число возвратов из каждого метода Тяжело понять логику метода, если при чтении его последних строк вы не подозреваете о возможности выхода из него где-то вверху. По этой причине используйте операторы возврата благоразумно - только если они улучшают читабельность.



ся заблудиться, потому что на каждом перекрестке вы оставляете несколько хлебных крошек и не поворачиваете в одну и ту же сторону дважды.

Верх

Идем вверх, поскольку налево нельзя

Лево


4 « » 9 « « 1» « I * «

Рис, 17-1, Рекурсия может быть мощным оружием в борьбе со сложностью, если используется по назначению

Рекурсивный код может выглядеть, например, так:

Пример рекурсивного перемещения по лабиринту (С++)

bool FinclPathThroughMaze( Maze maze, Point position ) {

Если это место уже исследовано, не надо снова его проверять, if ( AlreaclyTriecl( maze, position ) ) { return false;

Если это место и есть выход, объявляем успешное завершение, if ( ThisIsTheExit( maze, position ) ) { return true;

Запоминаем, что это место исследовано. RememberPosition( maze, position );

Проверяем пути налево, вверх, направо, вниз; если один из путей приводит к успеху, прекращаем поиск, if ( MoveLeft( maze, position, &newPosition ) ) { if ( FinclPathThroughMaze( maze, newPosition ) ) { return true;

if ( MoveUp( maze, position, &newPosition ) ) { if ( FinclPathThroughMaze( maze, newPosition ) ) { return true;



Первая строка кода проверяет, исследована ли уже данная точка. Одна из ключевых задач рекурсивного метода - предотвращение бесконечной рекурсии. В данном случае, если вы не будете проверять, что эта развилка уже исследовалась, вы можете бесконечно обследовать ее.

Второе выражение проверяет, не является ли эта позиция выходом из лабиринта. Если TbisIsTbeExitO возвращает true, метод тоже возвращает true. Третье выражение запоминает, что вы посетили данную точку. Это предотвращает бесконечную рекурсию, которая может возникнуть в результате замкнутого пути.

Остальные строки пытаются найти выход при движении налево, вверх, вниз и направо. Рекурсия прекратится, если метод когда-нибудь вернет true, т. е. будет найден выход из лабиринта.

Логика, используемая в этом примере, довольно прямолинейна. Большинство людей испытывают некоторый дискомфорт при виде рекурсивных методов, ссылающихся сами на себя. Однако в данном случае альтернативное решение было бы гораздо более трудоемким, и поэтому рекурсия отлично подходит.

Советы по использованию рекурсии

При применении рекурсии имейте в виду эти советы.

Убедитесь, что рекурсия остановится Проверьте метод, чтобы убедиться, что он включает нерекурсивный путь. Обычно это значит, что в методе присутствует проверка, останавливающая дальнейшую рекурсию, когда в ней отпадает необходимость. В примере с лабиринтом условия jijmMreadyTriedO и TbisIsTbeExitO гарантируют, что рекурсия остановится.

Предотвращайте бесконечную рекурсию с помощью

счетчиков безопасности Если вы применяете рекурсию %ь%т%ыш тштхь

в ситуации, не позволяющей сделать простую проверку вро- %штт иШтШ, шгому

де описанной выше, добавьте счетчики безопасности, дабы в Visual Basic она обшш?«й избежать бесконечной рекурсии. Счетчиком должна быть В$Шрвт1р. такая переменная, которая не будет создаваться при каждом

вызове метода. Используйте переменную-член класса или передавайте счетчик безопасности в виде параметра. Приведем пример:

if ( MoveDown( maze, position, &newPosition ) ) { if ( FinclPathThroughMaze( maze, newPosition ) ) { return true;

if ( MoveRight( maze, position, &newPosition ) ) { if ( FinclPathThroughMaze( maze, newPosition ) ) { return true;

return false;



0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 [127] 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294



0.003