算术和递归函数调用堆栈内存使用 [英] Stack memory use with arithmetic and recursive function call

问题描述

我关心的是什么将在涉及算术和递归函数调用，如指令使用堆栈存储器：

My concern is about what will use stack memory in an instruction involving arithmetics and a recursive function call such as:

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

我想了解什么是放在堆栈上，而当，让我知道什么可以或不可以在一个很深的递归的情况下会引起内存问题。下面是一个更完整的例子：

I'd like to understand what is put on the stack, and when, so that I know what could or couldn't cause memory issues in case of a deep recursion. Here is a more complete example:

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

让我们把重点放在行返回5 + F（A-1）; 我们将在围绕该点的内存来存储

Let's focus on the line return 5 + f(a-1); What will we have to store in memory around that point?

• 我们确实有在堆栈中为整数的地方，因为变量是本地到f


• 将值5和1储存在哪里？


• 怎么样操作的-1的结果，将它在堆栈上放？


• 有关F'的返回值是什么

对于所使用的内存将是在某些时候所有这些将是堆栈，同时在数量上的最坏情况。更好的情况是会有顺序的分配和释放，使得并不是所有都被保存在内存中。

The "worst case" scenario regarding the amount of memory used would be that at some point all of these will be on the stack at the same time. A better case would be that there will be allocations and deallocations in sequence such that not everything is kept in memory.

怎么会发生？是不是到编译器？

How will it happen? Is it up to the compiler?

非常感谢，

推荐答案

如果它的停留的递归的，你必须有在堆栈上的空间至少有一个堆栈帧（如previous栈指针或类似的寄存器保持栈帧，返回地址和空间的返回值）和传递在A-1 变量。在 5 和 1 几乎肯定不会在堆栈中去，他们会是code内硬codeD最有可能的。

If it stays recursive, you'll have to have space on the stack for at least a stack frame (eg, previous stack pointer or equivalent register for maintaining stack frames, return address and space for return value) and the a-1 variable being passed in. The 5 and the 1 almost certainly wouldn't go on the stack, they'd be hard-coded within the code most likely.

这可能看起来并不多，但是，如果你调用 F（999999999），你会杀了你的筹码。递归不是那么适合 A-1 型的操作。

That may not seem like much but, if you call f(999999999), you're going to kill your stack. Recursion's not that suited for a-1-type operations.

不过，你的编译器可能会聪明到足以做这样的事情尾端递归优化：

However, your compiler may be smart enough to do tail-end recursion optimisation on something like this:

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

---

当然，我假设，即code，你只是一个样本，因为我认为它很可能被替换的非递归甚至非迭代：

---

Of course, I'm assuming that that code you is just a sample since I think it could probably be replaced with the non-recursive and even non-iterative:

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

： - ）

这篇关于算术和递归函数调用堆栈内存使用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！