Рекурсия

Рекурсивное изображение экрана

Рекурсия — это поведение функции, при котором она вызывает сама себя. Такие функции называются рекурсивными. В отличие от цикла, они не просто повторяются несколько раз, а работают «внутри» друг друга. Пока условие выхода не достигнуто, все вызванные экземпляры рекурсивной функции работают одновременно — один вкладывает другой в себя. Если не прописать условие выхода, рекурсия будет бесконечной..

Область применения

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

Рекурсия встречается и в других отраслях: физике, биологии, лингвистике и даже архитектуре. Самый наглядный вид рекурсии — два поставленных друг напротив друга зеркала.

Отличия от цикла

Блок схема рекурсивного алгоритма решения Ханойской башни

На интуитивном уровне рекурсивный вызов легко перепутать с циклом. И то, и другое понятие подразумевает, что функция выполняется несколько раз. Но есть принципиальное различие:

• в цикле новые функции не вызываются внутри вызванных ранее;

• рекурсия же — это функция, вызывающая сама себя с другими аргументами.

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

Примеры применения

Вычисление факториала числа — последовательных умножений на предыдущее число. Например, 3! (факториал от трех) — это 1 * 2 * 3.

Обход ветвящихся структур данных, например графов и деревьев.

Компьютерный анализ естественного языка, фраз и предложений.

Вычисления с числовыми рядами, например те же числа Фибоначчи или поиск простых чисел.

Математические операции, требующие повторяющихся действий с разными значениями, к примеру возведение в степень больше 2, поиск максимума или минимума.

Операции с системами счисления, к примеру перевод чисел из одной в другую.