Стек вызовов и рекурсия

This lesson is not translated yet – the Russian original is below.

Стек – самая используемая область памяти в C++ и при этом самая незаметная: вы никогда не пишете код, который с ним работает, всё делает компилятор. Понимать его устройство нужно ровно по трём причинам: висячие указатели, переполнение стека и чтение стектрейса в отладчике.

Зачем вообще стек

Функция вызывает функцию, та – ещё одну. У каждой свои параметры и локальные переменные, и каждой нужно знать, куда вернуться. Порядок здесь всегда один: последняя вызванная завершается первой. Такая дисциплина называется LIFO и идеально ложится на структуру «стек» – достаточно одного указателя на вершину.

void C() { /* здесь на стеке кадры A, B, C */ }
void B() { C(); }
void A() { B(); }

int main() { A(); }

Кадр вызова

При каждом вызове на стек кладётся кадр (stack frame) – блок, в котором лежит всё, что нужно одному конкретному вызову:

Внутри кадра, в разных сочетаниях в зависимости от платформы:

• аргументы, не поместившиеся в регистры;
• адрес возврата – куда передать управление после return;
• сохранённое значение регистра базы кадра предыдущей функции;
• локальные переменные.

Выделение кадра – это сдвиг одного регистра на нужное число байт. Поэтому локальная переменная в C++ практически бесплатна, и поэтому же размер кадра должен быть известен на этапе компиляции: массив int a[n] с переменным n стандартом не предусмотрен.

Стектрейс в отладчике или в дампе – это просто перечисление кадров от вершины к дну. Первая строка – где упало, последняя – main. Читать его снизу вверх обычно понятнее: видно путь, которым программа туда пришла.

Кадр умирает вместе с вызовом

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

int* Broken() {
    int x = 42;
    return &x;             // адрес есть, объекта уже нет
}

const std::string& AlsoBroken() {
    std::string s = "hello";
    return s;              // то же самое, только со ссылкой
}

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

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

Рекурсия

Рекурсивная функция вызывает сама себя – напрямую или через другие функции. Никакой особой поддержки для этого не требуется: кадры просто складываются один на другой.

int Factorial(int n) {
    if (n == 0) {
        return 1;          // база: рекурсия заканчивается
    }

    return Factorial(n - 1) * n;
}

Вызовы могут образовывать не цепочку, а дерево:

int Fibonacci(int n) {
    if (n < 2) {
        return n;
    }

    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

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

Цена рекурсии в C++

Здесь C++ отличается от функциональных языков, где рекурсия – основной способ выражать циклы.

Глубина рекурсии ограничена размером стека. Миллион вложенных вызовов – это миллион кадров, и программа упадёт с переполнением стека задолго до результата. Хвостовую рекурсию (когда рекурсивный вызов – последнее действие функции) компилятор умеет превращать в цикл, но стандарт этого не гарантирует: с -O2 превратит, в отладочной сборке – нет.

int SumTo(int n, int acc = 0) {
    if (n == 0) return acc;
    return SumTo(n - 1, acc + n);   // хвостовой вызов: может стать циклом, а может и не стать
}

У наивного Fibonacci выше экспоненциальное число вызовов: Fibonacci(45) считается секундами. Проблема не в рекурсии как таковой, а в том, что одни и те же значения пересчитываются заново. Кэш посчитанного или обычный цикл превращают её в линейную.