В прошлом блоке мы изучали алгоритмы сортировки — и там уже встречались с рекурсией. Быстрая сортировка вызывает сама себя для левой и правой части. Сортировка слиянием — тоже. Принцип «разделяй и властвуй» вообще построен на рекурсии. Мы использовали её как инструмент, особо не задумываясь о механике. Теперь пришло время разобраться, что именно происходит внутри.

Рекурсия — одна из тех тем, которые поначалу кажутся странными. Функция, которая вызывает сама себя? Это же бесконечный цикл! Многие студенты именно так и думают, пока не разберутся в деталях. На самом деле рекурсия — это мощнейший инструмент, который позволяет решать задачи компактно и выразительно. И главное в ней — не сам факт самовызова, а то, как именно этот вызов организован. Начнём с аналогии, которая сразу расставит всё по местам.

Представьте, что вы стоите в длинной очереди в кассу и хотите узнать, сколько человек перед вами. Вы можете пройти от начала до конца и пересчитать всех. Это итеративный подход — обычный цикл. Но есть другой способ: спросите человека перед вами: «Сколько людей перед тобой?» Он спросит человека перед собой. Тот — следующего. И так до самого первого человека в очереди, который скажет: «Передо мной никого нет, я первый.» Это базовый случай — момент, когда ответ известен без дальнейших вопросов. Дальше ответы начинают возвращаться обратно: первый говорит «0», второй слышит это и отвечает «1», третий — «2»... и так до вас.

Вот и вся рекурсия. Задача разбивается на меньшую версию самой себя, и так продолжается до тех пор, пока не достигается точка, где ответ очевиден.

Любая рекурсивная функция состоит из двух обязательных частей:

Базовый случай (base case) — условие, при котором функция перестаёт вызывать себя и возвращает конкретный результат. Это «дно» рекурсии, точка остановки.

Рекурсивный вызов (recursive call) — вызов функции самой себя, но с аргументом, который ближе к базовому случаю, чем текущий. Это ключевой момент: каждый вызов должен делать задачу меньше.

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

Факториал числа n (пишется n!) — это произведение всех целых чисел от 1 до n. Например, 5! = 5 × 4 × 3 × 2 × 1 = 120. Математики записывают это красиво: n! = n × (n−1)! И это уже рекурсивное определение: факториал числа — это само число, умноженное на факториал числа на единицу меньше.

Базовый случай очевиден: 0! = 1 (или 1! = 1) — это математическое соглашение, и здесь рекурсия останавливается.

Запишем это на C#:

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

    return n * Factorial(n - 1);  // рекурсивный вызов
}

Разберём каждую строку.

if (n == 0) return 1 — это наш базовый случай. Когда n равно нулю, мы просто возвращаем 1. Никаких дальнейших вызовов.

return n * Factorial(n - 1) — рекурсивный вызов. Мы вычисляем n-1 и передаём его в ту же функцию. Обратите внимание: аргумент уменьшается на единицу с каждым вызовом, значит, мы неизбежно придём к нулю.

Проследим вызов Factorial(4) шаг за шагом:

Factorial(4)
  = 4 * Factorial(3)
  = 4 * (3 * Factorial(2))
  = 4 * (3 * (2 * Factorial(1)))
  = 4 * (3 * (2 * (1 * Factorial(0))))
  = 4 * (3 * (2 * (1 * 1)))    // базовый случай!
  = 4 * (3 * (2 * 1))
  = 4 * (3 * 2)
  = 4 * 6
  = 24

Видите две фазы? Сначала цепочка вызовов идёт вглубь — до базового случая. Потом результаты начинают возвращаться обратно, перемножаясь на каждом уровне. Именно так работает любая рекурсия: спуск до базового случая, подъём с результатом. Разберём ещё один пример — чуть сложнее. Посчитаем сумму элементов массива рекурсивно.

Идея та же: сумма массива — это первый элемент плюс сумма оставшегося массива. Базовый случай — пустой массив (его сумма равна нулю).

static int SumArray(int[] prices, int index)
{
    if (index == prices.Length)  // базовый случай: вышли за пределы
        return 0;

    return prices[index] + SumArray(prices, index + 1);  // текущий + сумма остальных
}

// Вызов:
int[] prices = { 150, 200, 350, 100 };
int total = SumArray(prices, 0);
Console.WriteLine(total);  // 800

Здесь index — указатель на текущий элемент. Каждый рекурсивный вызов передаёт index + 1, продвигаясь к концу массива. Когда index достигает prices.Length — все элементы обработаны, возвращаем 0.

Проследим вызов для массива { 150, 200, 350, 100 }:

SumArray(prices, 0)
  = 150 + SumArray(prices, 1)
  = 150 + (200 + SumArray(prices, 2))
  = 150 + (200 + (350 + SumArray(prices, 3)))
  = 150 + (200 + (350 + (100 + SumArray(prices, 4))))
  = 150 + (200 + (350 + (100 + 0)))   // базовый случай
  = 800

Теперь о самой частой ошибке. Что произойдёт, если убрать базовый случай из нашей функции?

static int FactorialBroken(int n)
{
    return n * FactorialBroken(n - 1);  // нет базового случая!
}

Вызовите FactorialBroken(5) — и программа будет вызывать FactorialBroken(4), потом FactorialBroken(3), FactorialBroken(2), FactorialBroken(1), FactorialBroken(0), FactorialBroken(-1), FactorialBroken(-2)... и никогда не остановится. Каждый вызов занимает память, и рано или поздно вы получите StackOverflowException.

Аналогичная ошибка — когда базовый случай есть, но до него никогда не доходит:

static int CountDown(int n)
{
    if (n == 0)
        return 0;

    return CountDown(n + 1);  // идём в противоположную сторону от базового случая!
}

Здесь базовый случай — n == 0, но рекурсивный вызов передаёт n + 1. Если вызвать CountDown(5), n будет расти: 6, 7, 8... бесконечно. То же StackOverflowException.

Правило простое: нарисуйте в голове «путь к базовому случаю». Если при каждом вызове аргумент делает шаг в нужную сторону — всё хорошо. Если нет — что-то не так.

В следующем уроке мы заглянем под капот и разберём, как именно компьютер управляет всеми этими вложенными вызовами — это называется стек вызовов, и понимание этого механизма поможет вам предсказывать поведение рекурсивных программ и избегать ошибок.

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

Базовый случай (base case) — условие, при котором функция прекращает вызывать себя и возвращает конкретный результат. Без него — бесконечная рекурсия и StackOverflowException.

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

Рекурсия работает в две фазы: спуск (до базового случая) и подъём (возврат результатов обратно по цепочке).

StackOverflowException — ошибка, возникающая при бесконечной рекурсии. Означает, что базовый случай не достигается.