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

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

Ключевые компоненты рекурсивной функции:

1. Базовый случай (Base Case): Простейший случай, который решается напрямую без рекурсивного вызова. Обязателен для остановки рекурсии и предотвращения бесконечного цикла и переполнения стека (StackOverflowException).
2. Рекурсивный случай (Recursive Case): Шаг, на котором функция вызывает саму себя с изменёнными (обычно упрощёнными) аргументами, приближаясь к базовому случаю.

Пример: Вычисление факториала (n!) на C#

// Рекурсивная реализация
public static int Factorial(int n)
{
    // 1. Базовый случай
    if (n <= 1)
        return 1;

    // 2. Рекурсивный случай: n! = n * (n-1)!
    return n * Factorial(n - 1);
}

// Вызов: Factorial(5)
// Стек вызовов:
// Factorial(5) = 5 * Factorial(4)
// Factorial(4) = 4 * Factorial(3)
// Factorial(3) = 3 * Factorial(2)
// Factorial(2) = 2 * Factorial(1)
// Factorial(1) -> Базовый случай! Возвращает 1
// Затем происходит возврат по стеку: 2*1=2 -> 3*2=6 -> 4*6=24 -> 5*24=120

Когда использовать рекурсию?

• Задачи, определяемые рекурсивно: Обход древовидных (файловая система, DOM, AST) или графовых структур.
• Алгоритмы «разделяй и властвуй»: Быстрая сортировка (QuickSort), сортировка слиянием (MergeSort), бинарный поиск.
• Задачи с вложенностью: Генерация комбинаций, парсинг вложенных выражений.

Хвостовая рекурсия (Tail Recursion) — это частный случай, когда рекурсивный вызов является последней операцией в функции. Некоторые компиляторы/интерпретаторы (например, для F#, Scala) могут оптимизировать хвостовую рекурсию, преобразуя её в итерацию, чтобы избежать роста стека.