Использование стековой памяти при вызове арифметических и рекурсивных функций

Question

Меня беспокоит вопрос, что будет использовать стековую память в инструкции, включающей арифметику и рекурсивный вызов функции, такой как:

return 5 + f(a-1); //f is recursive

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

int f(int a) {
    if (a > 0) {
        return 5 + f(a-1);
    }
    else {
        return 0;
    }
}

Давайте сосредоточимся на строке return 5 + f(a-1); Что нам нужно будет хранить в памяти вокруг этой точки?

• У нас есть место в стеке для целого числа a, так как переменная является локальной для f
• будут ли сохранены значения 5 и 1?
• как насчет результата операции a-1, он будет помещен в стек?
• как насчет возвращаемого значения f?

Сценарий «наихудшего случая», касающийся объема используемой памяти, заключается в том, что в какой-то момент все они будут в стеке одновременно. В лучшем случае было бы распределение и освобождение в последовательности, так что не все хранится в памяти.

Как это произойдет? Это до компилятора?

Большое спасибо,

Answer 1

Если он остается рекурсивным, вам понадобится место в стеке как минимум для стекового фрейма (например, предыдущий указатель стека или эквивалентный регистр для поддержки фреймов стека, адреса возврата и пространства для возврата значение) и передаваемая переменная a-1. 5 и 1 почти наверняка не пойдут в стек, они, скорее всего, будут жестко закодированы в коде.

Это может показаться не таким уж большим, но, если вы позвоните f(999999999), вы убьете свой стек. Рекурсия не подходит для операций типа a-1.

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

int f(int a) {
    if (a <= 0) return 0;
    return 5 + f(a-1);
}

---

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

int f(int a) { return (a > 0) ? a * 5 : 0; }

: -)

Answer 2

В этом контексте «стек» также может быть внутренним регистром / кэшем ЦП, в зависимости от ЦП и компилятора.Я буду называть их все стеком, чтобы все было просто.

Вещи, которые хранятся в стеке для каждого вызова функции : - переменная a.- возвращаемое значение.- обратный адрес звонящего.- Возможен «регистр кода состояния» или эквивалентный базовый регистр ЦП в зависимости от архитектуры.Возможно, счетчик программ и т. Д.Т.е. статические издержки, которые вы получаете каждый раз при вызове функции.

Выражение

return 5 + f (a-1);

5 - это константа, которая будет храниться в памяти программ и не влияет на стек.Скорее всего, -1 будет преобразован в инструкцию ассемблера «уменьшить на единицу» и, таким образом, также окажется в памяти программ.

Результат выражения a-1 будет сохранен в стеке, арезультат станет «новым a» для следующей рекурсии.

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

Answer 3

Взгляните на этот сайт о Соглашениях о вызовах функций и стеке

Также, если вы беспокоитесь о переполнении стека и ваш компилятор не может оптимизировать хвостовую рекурсию , вы можете преобразовать свой код в нерекурсивную альтернативу, преобразовав tail в цикл while, в случае не хвостовых рекурсивных функций вы должны иметь возможность самостоятельно создавать и управлять структурой данных стека (см. Путь от рекурсии к итерации )

Боже, благослови!

Answer 4

Насколько я понимаю, так и будет:

• a должен быть помещен в стек, потому что это локальная переменная.
• Естественно, что параметр f должен быть помещен в стек.
• Значение 5 должно быть помещено в стек, поскольку его необходимо сохранить для последующей операции +.
• Если я правильно помню, возвращаемое значение обрабатывается как параметр, поэтому оно также будет помещено в стек.
• И, конечно, указатель инструкции.

Но, возможно, компилятор выполняет некоторые оптимизации, о которых я не знаю.