Рекурсия (Recursion) — это мощный метод программирования, который позволя-
ет делить проблему на части все меньшего и меньшего размера до тех пор, пока
они не станут настолько малы, что решение этих подзадач сведется к набору про-
стых операций.
После того как вы поработаете с рекурсией, вы обнаружите, что она встречается
достаточно часто. Многие программисты-новички иногда чрезмерно увлекаются
рекурсией и начинают применять ее в ситуациях, где она не нужна и даже вредна.
В первых разделах этой главы рассматривается вычисление факториалов, чи-
сел Фибоначчи и наибольшего общего делителя. Приводятся примеры неправиль-
ного использования рекурсии (нерекурсивные версии более эффективны). Они
интересны и наглядны, поэтому имеет смысл поговорить о них.
Затем в главе рассматривается несколько примеров, в которых применение
рекурсии более уместно. Алгоритмы построения кривых Гильберта и Серпинско-
го используют рекурсию должным образом и очень эффективно.
В заключительных разделах этой главы объясняется, почему факториалы, чис-
ла Фибоначчи и наибольший общий делитель лучше вычислять без применения
рекурсии. Также говорится о том, когда не следует использовать рекурсию и при-
водятся способы ее устранения.

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

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