算术和递归函数调用中堆栈内存的使用

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

在这种情况下，“堆栈”也可以是内部 CPU 寄存器/高速缓存，具体取决于 CPU 和编译器。为了简单起见，我将它们全部称为堆栈。

每次函数调用时存储在堆栈上的内容是：
- 变量a。
- 返回值。
- 调用者的返回地址。
- 可能是“条件代码寄存器”或等效的基本 CPU 寄存器，具体取决于架构。可能还有程序计数器等。即每次调用函数时获得的静态开销。

表达式

返回 5 + f(a-1);

5 是一个常量，将存储在程序存储器中并且不影响堆栈。 -1很可能会被转换为汇编指令“减一”，因此最终也会进入程序存储器。

表达式a-1的结果将被存储在堆栈中，并且该结果将成为下一次递归的“新a”。

总而言之，这种情况下的罪魁祸首实际上并不是您在堆栈上来回显示的变量，而是函数调用开销本身所需的堆栈空间。

Answer 3

查看此网站，了解C 函数调用约定和堆栈< /a>

另外，如果您担心堆栈溢出并且编译器无法优化尾递归< /a>，您可以通过将 tail 转换为 while 循环来将代码转换为非递归替代方案，或者在非尾递归函数的情况下，您应该能够自己创建和管理堆栈数据结构（请参阅< a href="https://stackoverflow.com/questions/159590/way-to-go-from-recursion-to-iteration">从递归到迭代的方法）

上帝保佑！

Answer 4

据我了解，将会发生以下情况：

• a 必须放置在堆栈上，因为它是局部变量。
• 当然，f 的参数必须放置在堆栈上。
• 值 5 应该放在堆栈上，因为需要保存它以供后面的 + 操作使用。
• 如果我没记错的话，返回值被视为参数，因此它也会被放置在堆栈上。
• 当然还有指令指针。

但也许编译器做了一些我不知道的优化。