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

我关心的是在涉及算术和递归函数调用的指令中将使用堆栈内存，例如：

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

🙂

在这种情况下，“堆栈”也可以是内部CPU寄存器/缓存，具体取决于CPU和编译器。我会把它们称为堆叠以保持简单。

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

表达方式

返回5 + f（a-1）;

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

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

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

看一下这个关于C函数调用约定和堆栈的站点

此外，如果您担心堆栈溢出并且您的编译器无法优化尾递归，您可以通过将tail转换为while循环将代码转换为非递归替代，或者在非尾递归函数的情况下应该能够自己创建和管理堆栈数据结构（请参阅从递归到迭代的方法）

上帝保佑！

据我了解，这将是会发生的事情：

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