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

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; }

:-)