Рекурсия
Рекурсия — это поведение функции, при котором она вызывает сама себя. Такие функции называются рекурсивными. В отличие от цикла, они не просто повторяются несколько раз, а работают «внутри» друг друга. Пока условие выхода не достигнуто, все вызванные экземпляры рекурсивной функции работают одновременно — один вкладывает другой в себя. Если не прописать условие выхода, рекурсия будет бесконечной.[1].
Область применения
Обычно рекурсию применяют при расчётах, которые подразумевают использование результата одного шага для подсчитывания другого. Например, расчёт фрактала и его рисование. Зачастую подобные задачи можно решить и без рекурсии, но её использование делает код проще, короче и быстрее, чем альтернативные варианты. Правда, рекурсия может слишком нагружать компьютер, поэтому такие решения применяют не всегда[1].
Рекурсия встречается и в других отраслях: физике, биологии, лингвистике и даже архитектуре. Самый наглядный вид рекурсии — два поставленных друг напротив друга зеркала.
Отличия от цикла
На интуитивном уровне рекурсивный вызов легко перепутать с циклом. И то, и другое понятие подразумевает, что функция выполняется несколько раз. Но есть принципиальное различие:
- в цикле новые функции не вызываются внутри вызванных ранее;
- рекурсия же — это функция, вызывающая сама себя с другими аргументами.
Циклами часто заменяют рекурсию, например в ситуациях, где рекурсивные алгоритмы оказываются слишком ресурсоёмкими. При этом для использования циклов в качестве замены рекурсии необходимы дополнительные действия[2].
Примеры применения
Вычисление факториала числа — последовательных умножений на предыдущее число. Например, 3! (факториал от трех) — это 1 * 2 * 3.
Обход ветвящихся структур данных, например графов и деревьев.
Компьютерный анализ естественного языка, фраз и предложений.
Вычисления с числовыми рядами, например те же числа Фибоначчи или поиск простых чисел.
Математические операции, требующие повторяющихся действий с разными значениями, к примеру возведение в степень больше 2, поиск максимума или минимума.
Операции с системами счисления, к примеру перевод чисел из одной в другую[2].
