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

Question

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

Тип вопроса: Алгоритмы и структуры данных Вероятность: 28% Категория: C# Разработчик

Ответ

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

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

Базовый случай (Base Case): Простейший случай, который решается напрямую без рекурсивного вызова. Обязателен для остановки рекурсии и предотвращения бесконечного цикла и переполнения стека (StackOverflowException).
Рекурсивный случай (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), бинарный поиск.
Задачи с вложенностью: Генерация комбинаций, парсинг вложенных выражений.

Рекурсия vs Итерация:	Критерий	Рекурсия
Читаемость	Часто более лаконична и понятна для рекурсивных по природе задач.	Может быть менее интуитивной для таких задач.
Производительность	Накладные расходы на вызов функции и использование стека. Может привести к `StackOverflowException` при большой глубине.	Обычно эффективнее по памяти и скорости, нет накладных расходов на вызовы.
Управление состоянием	Состояние передается через параметры и сохраняется в стеке вызовов.	Состояние управляется явно через переменные в циклах.

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

Ответ 18+ 🔞

Смотри, вот тебе рекурсия на пальцах, без всей этой академической пиздобратии.

Представь, что у тебя есть матрёшка. Ты её открываешь — внутри ещё одна, поменьше. Открываешь ту — там ещё. Это и есть рекурсия, пока не докопаешься до самой маленькой, которую уже не раскроешь. Эта последняя — и есть базовый случай, стоп-кран, чтобы твоя функция не ушла в бесконечный цикл и не накрылась медным тазом с StackOverflowException.

Любая рекурсивная функция — это две вещи:

Базовый случай — когда надо прекратить это шаманство и дать ответ. Без него ты просто упрёшься лбом в стенку.
Рекурсивный шаг — где функция, такая вся из себя умная, вызывает саму себя, но уже с чуть более простой задачей. Как будто говоришь: «Слушай, я тут застрял, реши-ка ты эту же хуйню, но чуть попроще, а я потом из твоего результата свой соберу».

Вот, смотри, классика жанра — факториал. n! — это все числа от 1 до n, перемноженные. А по-нашему, рекурсивно, это n * (n-1)!. И так до тех пор, пока не дойдёшь до единицы, потому что 1! — это просто 1, приехали.

public static int Factorial(int n)
{
    // Вот он, стоп-кран, базовый случай! Если n <= 1, дальше не идём.
    if (n <= 1)
        return 1;

    // А вот и рекурсивный шаг: "Я не знаю, чей факториал равен n!, но знаю, что он равен n * факториалу от (n-1). Эй, функция, проснись, посчитай мне (n-1)!"
    return n * Factorial(n - 1);
}

Как это работает на примере Factorial(5)? Давай по стеку вызовов, это важно:

Factorial(5) говорит: «Мне надо 5 * Factorial(4). Эй, Factorial(4), работай!»
Factorial(4) говорит: «Окей, но мне для этого надо 4 * Factorial(3). Эй, Factorial(3), не зевай!»
Factorial(3) заныл: «Да без 3 * Factorial(2) я никуда...`
Factorial(2) скрипит: «2 * Factorial(1)...»
Factorial(1) наконец-то: «О, базовый случай! n <= 1. Возвращаю 1 и пошёл нахуй, всем спасибо».

И тут всё начинает схлопываться обратно:

Factorial(2) получает от Factorial(1) единицу, умножает на свои 2 и возвращает 2.
Factorial(3) ловит эту двойку, умножает на свои 3, возвращает 6.
Factorial(4) хватает шестёрку, накидывает сверху свою четвёрку — получается 24.
Factorial(5) довольный берёт 24, умножает на 5 и выдаёт тебе итоговые 120.

Когда эту штуку вообще юзать?

Когда данные — как матрёшка: дерево файлов, HTML-документ, граф. Тут итеративно-то можно, но рекурсия получается в разы понятнее, ей богу.
Задачи «разделяй и властвуй»: быстрая сортировка, бинарный поиск. Сама суть — разбить на подзадачи.
Всякие комбинаторные заморочки, где одно действие порождает кучу таких же, но чуть проще.

А теперь про больную тему: рекурсия или циклы?

Что сравниваем	Рекурсия	Циклы (Итерация)
Понятность	Для задач «матрёшечного» типа — просто песня, читается как учебник.	Может превратиться в ад из индексов и флагов, в котором черт ногу сломит.
Производительность	Тут тебе и вызов функции (накладные расходы), и стек жрёт. Если глубина большая — гарантированный `StackOverflowException`, пиздец и сессия отладки до утра.	Обычно быстрее и память не жрёт так беспощадно. Просто бегает по кругу, как белка.
Управление	Состояние тащится за собой в аргументах и в стеке. Иногда это удобно.	Состояние — в отдельных переменных, всё на виду, но и под ногами путается.

Есть ещё одна хитрая штука — хвостовая рекурсия. Это когда рекурсивный вызов — самое последнее, что делает функция, и ей больше не нужно ничего с результатом делать. В теории, умные компиляторы (как в F#) могут это превратить в обычный цикл под капотом, чтобы стек не гробить. Но в C#, дружище, на это особо не надейся, компилятор тут обычно руки разводит. Так что имей в виду.

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