В прошлом уроке мы написали первые рекурсивные функции и разобрались с базовым случаем и рекурсивным вызовом. Но осталось ощущение, что что-то происходит «за кулисами». Функция вызывает себя, возвращает значения в обратном порядке, результаты приходят снизу вверх... Как это всё работает? Откуда программа знает, куда возвращаться после каждого вызова? Где хранятся все эти промежуточные значения, пока рекурсия «спускается» вниз?

Ответ — стек вызовов. Без понимания этой структуры поведение рекурсии сложно предсказать. С ним — всё встаёт на свои места. Представьте стопку тарелок. Вы кладёте тарелку сверху — она ложится первой. Потом ещё одну — поверх первой. Берёте тарелку — снимаете с верхушки, то есть ту, что положили последней. Положил последним — взял первым. По-другому не получится: физически до нижней тарелки не добраться, не сняв верхние. Это и есть принцип стека: Last In, First Out — LIFO.

Именно так работает память программы при вызовах функций.

Каждая такая запись называется фреймом стека (stack frame). В нём хранятся несколько вещей: параметры функции (например, значение n), её локальные переменные, а также адрес возврата — то есть место в коде, куда нужно вернуться, когда функция завершится. Именно благодаря адресу возврата программа не «теряется» — после завершения Factorial(2) она точно знает, что нужно продолжить выполнение в Factorial(3), в том месте, где был сделан вызов.

Когда программа запускается, стек пуст. Вызывается Main — добавляется первый фрейм. Main вызывает Factorial(3) — добавляется второй фрейм. Factorial(3) вызывает Factorial(2) — третий фрейм. И так далее. Когда функция заканчивается — её фрейм снимается со стека, и выполнение продолжается в предыдущем фрейме, с того места, где был сделан вызов.

Важный момент: фреймы рекурсивной функции абсолютно независимы. У Factorial(3) — своя переменная n со значением 3. У Factorial(2) — своя переменная n со значением 2. Они не мешают друг другу, не перезаписывают друг друга. Именно поэтому рекурсия вообще возможна: каждый вызов живёт в собственном фрейме с собственными данными. Проследим это пошагово на конкретном примере. Возьмём Factorial(3):

static int Factorial(int n)
{
    if (n == 0)
        return 1;
    return n * Factorial(n - 1);
}

Шаг 1 — Main вызывает Factorial(3). В стек добавляется фрейм: n=3. Программа выполняет проверку: n == 0? Нет. Выполняет return 3 * Factorial(2). Но чтобы вернуть результат, нужно сначала вычислить Factorial(2). Фрейм Factorial(3) приостанавливается и ждёт.

Шаг 2 — вызывается Factorial(2). В стек добавляется новый фрейм: n=2. Фрейм Factorial(3) при этом никуда не исчезает — он находится в стеке ниже. Проверяет: n == 0? Нет. Вызывает Factorial(1) и тоже приостанавливается.

Шаг 3 — вызывается Factorial(1). Ещё один фрейм: n=1. Фреймы Factorial(3) и Factorial(2) ждут в стеке. Вызывает Factorial(0).

Шаг 4 — вызывается Factorial(0). Фрейм: n=0. Проверяет: n == 0? Да! Возвращает 1. Фрейм Factorial(0) снимается со стека.

Теперь начинается обратный ход — «всплытие»:

Шаг 5 — управление возвращается в Factorial(1): она получила результат Factorial(0) = 1 и вычисляет return 1 * 1 = 1. Фрейм снимается.

Шаг 6 — возврат в Factorial(2): return 2 * 1 = 2. Фрейм снимается.

Шаг 7 — возврат в Factorial(3): return 3 * 2 = 6. Фрейм снимается. Управление возвращается в Main. Ответ: 6.

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

Теперь о том, что происходит, когда рекурсия идёт не по плану.

Стек вызовов не бесконечный. Каждый фрейм занимает память — обычно сотни байт. У стека есть фиксированный размер: по умолчанию в .NET это около 1 МБ для основного потока. Если рекурсия уходит слишком глубоко — стек переполняется.

Типичная ситуация — забытый базовый случай:

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

Эта функция будет вызывать себя бесконечно: BadFactorial(5) → BadFactorial(4) → ... → BadFactorial(-1000) → ... Каждый вызов добавляет новый фрейм в стек. Стек будет расти, пока не закончится отведённая память. Тогда .NET прервёт выполнение:

Stack overflow.
Process is terminated.

Другая коварная ошибка — когда базовый случай есть, но рекурсивный вызов к нему не приближается:

static int StuckFactorial(int n)
{
    if (n == 0)
        return 1;
    return n * StuckFactorial(n);  // передаём то же n, не n-1!
}

Здесь базовый случай есть, но StuckFactorial(5) вызывает StuckFactorial(5), который вызывает StuckFactorial(5)... Тот же результат — переполнение стека. Базовый случай никогда не будет достигнут, потому что n не изменяется.

Правило простое: каждый рекурсивный вызов должен делать задачу меньше — то есть передавать аргумент, который ближе к базовому случаю. Если вы вызываете f(n) из f(n) — это бесконечный цикл. Если вы вызываете f(n-1) или f(n/2) — рекурсия идёт к базовому случаю. Теперь взгляните на стек вызовов с другой стороны — он помогает понять, почему порядок кода в рекурсии так важен.

Возьмём функцию, которая печатает числа от n до 0:

static void CountDown(int n)
{
    if (n < 0)
        return;
    Console.Write(n + " ");   // вывод ДО рекурсивного вызова
    CountDown(n - 1);
}

// CountDown(3) выведет: 3 2 1 0

Console.Write стоит до рекурсивного вызова. Это значит: при «погружении» в стек сразу печатаем текущее значение, потом идём глубже. Числа выводятся от большего к меньшему — по мере накопления фреймов.

Теперь поменяем порядок:

static void CountUp(int n)
{
    if (n < 0)
        return;
    CountUp(n - 1);           // сначала рекурсия
    Console.Write(n + " ");   // потом вывод
}

// CountUp(3) выведет: 0 1 2 3

Числа идут по возрастанию! Почему? Потому что Console.Write вызывается при возврате из рекурсии — когда стек начинает «всплывать». Сначала выполняются все рекурсивные вызовы и стек заполняется до базового случая. Потом фреймы начинают сниматься: фрейм CountUp(0) завершается и печатает 0, затем фрейм CountUp(1) печатает 1, и так далее до фрейма CountUp(3), который печатает 3.

Это очень мощная техника. Если нужно обработать элементы в обратном порядке — делайте работу после рекурсивного вызова, а не до. Например, развернуть строку, вывести список в обратном порядке, обойти дерево снизу вверх — всё это делается именно так. Посмотрим ещё на один практичный пример — функцию, которая разворачивает строку рекурсивно. Это хорошо иллюстрирует, как «всплытие» стека используется для работы.

static void PrintReversed(string s, int index)
{
    if (index >= s.Length)
        return;                           // базовый случай: вышли за пределы строки
    PrintReversed(s, index + 1);          // сначала рекурсия — идём до конца строки
    Console.Write(s[index]);              // потом вывод — при «всплытии»
}

// PrintReversed("hello", 0) выведет: olleh

Что происходит? Функция «проваливается» до конца строки, не печатая ничего. Когда достигает базового случая — начинает «всплывать». При каждом возврате печатает символ по текущему индексу. Поскольку возвращаемся мы в обратном порядке — последний символ выводится первым, первый — последним. Строка развёрнута.

Тот же результат можно получить и итеративно, с обычным циклом от конца к началу. Но рекурсивная версия наглядно демонстрирует механику: «погружение» — накопление контекста в стеке, «всплытие» — использование этого контекста в обратном порядке.

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

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

Стек вызовов (call stack) — структура памяти, где хранятся фреймы текущих вызовов функций. Каждый вызов добавляет фрейм, возврат — убирает его. Работает по принципу LIFO: последний вошёл — первый вышел.

Stack frame (фрейм стека) — запись в стеке вызовов для одной функции: параметры, локальные переменные и адрес возврата. Именно адрес возврата позволяет программе «не потеряться» и знать, куда вернуться после завершения функции.

Рекурсия работает в два этапа: сначала «вниз» — фреймы накапливаются в стеке при каждом вызове. Потом «вверх» — фреймы снимаются и результаты вычисляются при возврате.

StackOverflowException возникает, когда стек переполняется из-за слишком глубокой рекурсии (нет базового случая или он не достигается). Нельзя поймать через try-catch — процесс завершается принудительно.

Порядок операций в рекурсии важен: если вызвать действие до рекурсивного вызова — оно выполнится при «погружении» (по убыванию). Если после — при «всплытии», то есть в обратном порядке (по возрастанию).