Урок 8.12 — Рекурсия

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

Пример из жизни: чтобы положить матрёшку в матрёшку, ты открываешь самую большую, находишь внутри поменьше, открываешь её — и так до самой маленькой. Это рекурсия. Базовый случай — самая маленькая матрёшка, которая уже не открывается.

// Счёт от N до 1
static void CountDown(int n)
{
    if (n <= 0)        // базовый случай
        return;

    Console.WriteLine(n);
    CountDown(n - 1);  // рекурсивный вызов с уменьшенным n
}

CountDown(5);
// Вывод: 5 4 3 2 1

Два ключевых элемента любой рекурсии:

if (n == 0) return 1;     // факториал 0 = 1
if (n <= 1) return n;     // числа Фибоначчи
if (list.Count == 0) return;  // пустой список

return n * Factorial(n - 1);          // факториал
return Fibonacci(n - 1) + Fibonacci(n - 2);  // Фибоначчи

Факториал числа n (обозначается n!) — это произведение всех натуральных чисел от 1 до n. Например, 5! = 5 x 4 x 3 x 2 x 1 = 120.

Рекурсивное определение: n! = n * (n-1)!, где 0! = 1 (базовый случай).

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

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

Console.WriteLine(Factorial(5));   // → 120
Console.WriteLine(Factorial(0));   // → 1
Console.WriteLine(Factorial(10));  // → 3628800

// Как это работает для Factorial(3):
// Factorial(3) = 3 * Factorial(2)
// Factorial(2) = 2 * Factorial(1)
// Factorial(1) = 1           ← базовый случай
// Factorial(2) = 2 * 1 = 2
// Factorial(3) = 3 * 2 = 6

Последовательность Фибоначчи: 0, 1, 1, 2, 3, 5, 8, 13, 21... Каждое число равно сумме двух предыдущих. Рекурсивное определение: F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2).

static int Fibonacci(int n)
{
    // Базовые случаи
    if (n == 0) return 0;
    if (n == 1) return 1;

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

for (int i = 0; i <= 10; i++)
{
    Console.Write($"{Fibonacci(i)} ");
}
// → 0 1 1 2 3 5 8 13 21 34 55

Каждый вызов метода (включая рекурсивный) создаёт фрейм в стеке вызовов — область памяти, где хранятся локальные переменные и адрес возврата. Когда рекурсия слишком глубокая, стек переполняется и возникает StackOverflowException.

// ❌ Бесконечная рекурсия — StackOverflowException!
static void InfiniteRecursion()
{
    Console.WriteLine("Глубина...");
    InfiniteRecursion();  // нет базового случая!
}

// ❌ Слишком глубокая рекурсия
static void DeepRecursion(int depth)
{
    if (depth == 0) return;
    DeepRecursion(depth - 1);
}

DeepRecursion(100000);  // Скорее всего StackOverflowException

// Стек вызовов для Factorial(5):
// Call stack (сверху вниз):
// Factorial(1) → возвращает 1
// Factorial(2) → ждёт Factorial(1)
// Factorial(3) → ждёт Factorial(2)
// Factorial(4) → ждёт Factorial(3)
// Factorial(5) → ждёт Factorial(4)
// Main() → вызвал Factorial(5)

Мемоизация — это техника оптимизации, при которой результаты дорогих вызовов сохраняются в кэше (обычно Dictionary) и повторно используются при одинаковых входных данных. Это превращает экспоненциальную сложность Фибоначчи в линейную.

static Dictionary<int, long> cache = new();

static long FibonacciMemo(int n)
{
    // Базовые случаи
    if (n == 0) return 0;
    if (n == 1) return 1;

    // Если уже вычисляли — возвращаем из кэша
    if (cache.ContainsKey(n))
        return cache[n];

    // Вычисляем и сохраняем
    cache[n] = FibonacciMemo(n - 1) + FibonacciMemo(n - 2);
    return cache[n];
}

// Теперь миллион раз быстрее!
for (int i = 0; i <= 50; i++)
{
    Console.WriteLine($"F({i}) = {FibonacciMemo(i)}");
}
// F(50) = 12586269025 — мгновенно!

Сравни: обычный рекурсивный Fibonacci(40) делает ~330 миллионов вызовов. С мемоизацией — всего 41 вызов (по одному на каждое n).

Любую задачу, решаемую рекурсией, можно решить итеративно (циклом), и наоборот. Выбор зависит от ситуации.

// Рекурсия
static int FactorialRec(int n)
{
    if (n <= 1) return 1;
    return n * FactorialRec(n - 1);
}

// Итерация
static int FactorialIter(int n)
{
    int result = 1;
    for (int i = 2; i <= n; i++)
        result *= i;
    return result;
}

// Когда использовать рекурсию:
// - Обход деревьев и графов
// - Задачи типа "разделяй и властвуй" (quicksort, mergesort)
// - Задачи с естественной рекурсивной структурой

// Когда использовать итерацию:
// - Простые вычисления (факториал, Фибоначчи)
// - Когда глубина рекурсии может быть большой
// - Когда производительность критична