Рекурсия (Recursion) - это мощный метод программирования, который позволя-
ет делить проблему на части все меньшего и меньшего размера до тех пор, пока
они не станут настолько малы, что решение этих подзадач сведется к набору про-
стых операций.
После того как вы поработаете с рекурсией, вы обнаружите, что она встречается
достаточно часто. Многие программисты-новички иногда чрезмерно увлекаются рекурсией и начинают применять ее в ситуациях, где она не нужна и даже вредна.
В первых разделах этой главы рассматривается вычисление факториалов, чи-
сел Фибоначчи и наибольшего общего делителя. Приводятся примеры неправиль-
ного использования рекурсии (нерекурсивные версии более эффективны). Они
интересны и наглядны, поэтому имеет смысл поговорить о них.
Затем в главе рассматривается несколько примеров, в которых применение
рекурсии более уместно. Алгоритмы построения кривых Гильберта и Серпинско-
го используют рекурсию должным образом и очень эффективно.
В заключительных разделах этой главы объясняется, почему факториалы, чис-
ла Фибоначчи и наибольший общий делитель лучше вычислять без применения
рекурсии. Также говорится о том, когда не следует использовать рекурсию и при-
водятся способы ее устранения.
При работе с рекурсивными алгоритмами следует избегать трех основных опас-
ностей: бесконечная рекурсия. Убедитесь, что ваш алгоритм имеет надежное условие
остановки; глубокая рекурсия. Если алгоритм вызывает слишком глубокую рекурсию, он
исчерпает всю память стека. Сократите использование стека, уменьшив коли-
чество переменных, которые размещает процедура, или описывая переменные
глобально. Если процедура все еще исчерпывает память стека, перепишите
алгоритм без рекурсии с помощью устранения хвостовой рекурсии; неуместная рекурсия. Обычно это происходит, когда алгоритм, подобный
рекурсивному алгоритму подсчета чисел Фибоначчи, много раз вычисляет
одни и те же промежуточные значения. Если в вашей программе возникают
проблемы подобного рода, попытайтесь переписать алгоритм методом сни-
зу вверх. Если алгоритм нельзя преобразовать с помощью восходящего спо-
соба, создайте таблицу соответствия промежуточных значений.
Но применение рекурсии не всегда бывает неоправданным. Многие задачи ре-
курсивны по своей природе. В этих случаях рекурсивный алгоритм будет проще
понять, отладить и реализовать, чем нерекурсивный. Алгоритмы
и демонстрируют именно такую рекурсию. Оба они
естественно рекурсивны, и их гораздо проще понять в рекурсивном представлении.
Если имеется алгоритм, который является рекурсивным по своей природе, но
вы не уверены, можно ли с помощью рекурсивной версии решить задачу, перепи-
шите ее рекурсивно и выясните это. Проблемы может и не возникнуть. Если ка-
кие-либо трудности все же имеются, будет гораздо проще преобразовать рекурсив-
ный алгоритм в нерекурсивную форму, чем сразу создать нерекурсивную версию.
Опубликовал Kest
October 19 2009 09:49:24 ·
0 Комментариев ·
11101 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
