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

Основные компоненты рекурсивной функции:

Базовый случай (base case): Условие, при выполнении которого рекурсия останавливается. Без базового случая рекурсия будет бесконечной.
Рекурсивный переход (recursive step): Шаг, при котором функция делает рекурсивный вызов самой себя, но с измененными аргументами, которые приближают выполнение к базовому случаю.

Пример рекурсивного вычисления факториала:

#include <iostream>

long long factorial(int n) {
    // Базовый случай: факториал 0 или 1 равен 1
    if (n <= 1) {
        return 1;
    }
    // Рекурсивный переход: n! = n * (n-1)!
    return n * factorial(n - 1);
}

int main() {
    int num = 5;
    std::cout << "Factorial of " << num << " is " << factorial(num) << std::endl;
    return 0;
}

Рекурсия часто используется для решения задач, которые легко выразить в терминах более простых подзадач того же типа, например, при обходе структуры данных (дерево, граф), сортировке (например, Merge Sort, Quick Sort) или вычислении математических функций (например, числа Фибоначчи, факториал).

Важные моменты:

Каждый рекурсивный вызов создает новый кадр стека вызовов. Чрезмерное количество рекурсивных вызовов может привести к переполнению стека (Stack Overflow).
Рекурсивное решение часто можно преобразовать в итеративное (с использованием циклов и явного стека), и наоборот. Итеративные решения, как правило, более эффективны по памяти, но могут быть менее явными и читаемыми для некоторых задач.
Оптимизация хвостовой рекурсии (Tail Call Optimization), если она поддерживается компилятором, позволяет избежать роста стека при определенных типах рекурсивных вызовов.

Что такое рекурсия?