Рекурсия — это способ определения функции, процедуры или структуры данных через саму себя. Применительно к функции, рекурсия означает, что функция вызывает саму себя в процессе своего исполнения.
Основные компоненты рекурсивной функции:
- Базовый случай (base case): Условие, при выполнении которого рекурсия останавливается. Без базового случая рекурсия будет бесконечной.
- Рекурсивный переход (recursive step): Шаг, при котором функция делает рекурсивный вызов самой себя, но с измененными аргументами, которые приближают выполнение к базовому случаю.
Пример рекурсивного вычисления факториала:
cpp
Рекурсия часто используется для решения задач, которые легко выразить в терминах более простых подзадач того же типа, например, при обходе структуры данных (дерево, граф), сортировке (например, Merge Sort, Quick Sort) или вычислении математических функций (например, числа Фибоначчи, факториал).
Важные моменты:
- Каждый рекурсивный вызов создает новый кадр стека вызовов. Чрезмерное количество рекурсивных вызовов может привести к переполнению стека (Stack Overflow).
- Рекурсивное решение часто можно преобразовать в итеративное (с использованием циклов и явного стека), и наоборот. Итеративные решения, как правило, более эффективны по памяти, но могут быть менее явными и читаемыми для некоторых задач.
- Оптимизация хвостовой рекурсии (Tail Call Optimization), если она поддерживается компилятором, позволяет избежать роста стека при определенных типах рекурсивных вызовов.