Объявление статической переменной внутри рекурсивной функции.Переполнение стека

Question

Этот код как раз о концепции, он не имеет никакого смысла.

void recur(int num)
{   
    static float tmp = num * num;
    if (num == 0)
    {
        return;
    }
    else
    {
        recur(num - 1);
    }
}

int main()
{
    recur(1000000);
}

Я думал, что статические переменные просто используют одну позицию в памяти, но вызов функции recur в mainвызывая ошибку переполнения стека. Что имеет смысл, если переменная tmp была объявлена ​​в стеке, но, будучи статичной, она не находится в стеке, верно?

Каково поведение переменной tmp ??

Спасибо

Answer 1

Я наблюдал за сборкой основных компиляторов, с максимальной оптимизацией у вас не должно быть переполнения стека:

• GCC : упростить функцию до 0, рекурсии нет.
• Clang : как GCC
• MSVC : выполнить рекурсивный вызов с внутренним переходом (вид хвостового вызова), только аргументпервый нерекурсивный вызов помещается в стек.

Так что я думаю, у вас не будет переполнения стека, если вы включите оптимизацию для этого тривиального случая.

Но я предполагаю, что ваш случайболее сложный.

Если у вас была функция, которая не вызывала переполнения стека без какой-либо статической переменной, а затем вызывала переполнение стека, если вы добавили эту статическую переменную, причина, вероятно, является побочным эффектом при генерации кода статической переменной.инициализация.

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

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

Answer 2

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

Есть хорошая диаграмма в WiKi.

Как указывалось в предыдущих ответах и ​​комментариях, каждый раз, когда вы называете recur местом для обратного адреса и, возможно, (в зависимости от платформы, я предполагаю, что вы тестируете на x86)для параметра num выделяются в стеке.

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

#include <iostream>

int x;

void recur(int num)
{   
    static float tmp = num * num;

    std::cout << "tmp: " << &tmp << " num: " << &num << std::endl;
    if (num == 0)
    {
        return;
    }
    else
    {
        recur(num - 1);
    }
}

int main()
{
    int z;
    int *p = new int;
    std::cout << "p: " << p << " x: " << &x << " z: " << &z << std::endl;
    recur(10);

    delete p;
    return 0;
}

Пример выходных данных будет выглядеть следующим образом:

p: 0x1c12c20 x: 0x6011b8 z: 0x7ffc0b6dd914
tmp: 0x6011c8 num: 0x7ffc0b6dd8fc
tmp: 0ff0 0d0 0 0 0 0 0 0 6 0 0 6 0 0 6 0 0 6 6 0 0 6 6 0 0 6 6tmp: 0x6011c8 num: 0x7ffc0b6dd8bc
tmp: 0x6011c8 num: 0x7ffc0b6dd89c
tmp: 0x6011c8 num: 0x7ffc0b6dd87c
tmp: 0x6016 0x0 0x0 0c0 0x8 0c0 0x0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 0 8 0 0 8 0 0 8 0 0 8 0 0 8 0 0 8 0 0 8 8 0 0 8 0 0 8 8 0 8 0 0 8 0 0 8 0 0 8 0 0 8 0 8 87ffc0b6dd83c
TMP: 0x6011c8 Num: 0x7ffc0b6dd81c * 1 026 * TMP: 0x6011c8 Num: 0x7ffc0b6dd7fc
TMP: 0x6011c8 Num: 0x7ffc0b6dd7dc
TMP: 0x6011c8 Num: 0x7ffc0b6dd7bc * * * тысячу двадцать-девять 1030 *

Answer 3

Я думал, что статические переменные используют только одну позицию в памяти

Вы правильно подумали.

Каково поведение переменной tmp ??

Существует ровно один объект для переменной tmp.Все вызовы recur используют один и тот же объект.Он инициализируется при первом вызове функции и уничтожается после возврата main.

---

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

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

Answer 4

Статическая переменная отсутствует в стеке.Вы можете рассматривать это как глобальную переменную.Переполнение стека возникает потому, что каждый вызов помещает аргумент «num» в стек.Кроме того, адрес возврата помещается в стек, поэтому даже «пустая» функция вызовет переполнение (изображение из https://en.wikipedia.org/wiki/Call_stack)

Answer 5

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