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

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

Основные компоненты рекурсии

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

Пример рекурсивной функции

int Factorial(int n)
{
    // Базовый случай
    if (n == 0 || n == 1)
        return 1;

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

Типы рекурсии

1. Прямая рекурсия — функция вызывает себя напрямую (как в примере выше).
2. Косвенная рекурсия — функция A вызывает функцию B, которая вызывает A.
3. Хвостовая рекурсия — рекурсивный вызов является последней операцией (может быть оптимизирована компилятором).

Плюсы и минусы

✔ Плюсы:

• Упрощает код для задач с естественной рекурсивной структурой (деревья, графы).
• Позволяет элегантно решать задачи типа "разделяй и властвуй".

✖ Минусы:

• Риск переполнения стека (Stack Overflow) при глубокой рекурсии.
• Может быть менее эффективна по памяти и времени, чем итеративное решение.

Пример опасности

void InfiniteRecursion()
{
    InfiniteRecursion(); // Упадёт с StackOverflowException
}

Когда использовать?

• Обработка вложенных структур (XML, JSON, деревья).
• Алгоритмы типа "разделяй и властвуй" (быстрая сортировка, обход деревьев).
• Задачи, где рекурсия делает код понятнее (но без злоупотребления!).

Резюмируем:

рекурсия — мощный инструмент, но требует аккуратного применения с обязательным базовым случаем и оценкой производительности.