Рекурсия в информатике

Реку́рсия в информатике, описание процесса (например, алгоритма решения задачи) посредством обращения (отсылки) к самому описанию (как правило, при других исходных данных).

Использование рекурсии в программировании позволяет описать решения многих задач проще, чем при отказе от рекурсии, упрощает формальный анализ или даже доказательство правильности программного кода, однако часто рекурсивное решение не является наилучшим с точки зрения затрачиваемых вычислительных ресурсов и используемой памяти. Ярким примером ухудшения производительности и улучшения понятности программ при использовании рекурсии являются алгоритмы типа ««разделяй-и-властвуй» (в том числе рекурсивные реализации т. н. быстрого преобразования Фурье, сортировки слиянием или быстрой сортировки).

Корректное использование рекурсии требует рассмотрения т. н. базового случая: явного описания ситуации (условий) и последовательности действий, когда решение задачи может быть достигнуто без отсылки к нему же.

Математическую основу рекурсии составляет аппарат рекурсивных функций.