递归函数导致的堆栈溢出

Question

我是C++的初学者。昨天我读了关于递归函数的内容，所以我决定自己写一个。以下是我的代码：

int returnZero(int anyNumber) {
    if(anyNumber == 0)
        return 0;
    else  {
        anyNumber--;
        return returnZero(anyNumber);
    }
}

当我执行以下操作：int zero1 = returnZero(4793); 时，它会导致堆栈溢出。但是，如果我将值4792作为参数传递，则不会发生溢出。

有什么想法吗？

- charles

---

也许更大的值恰好是溢出堆栈所需的？ - Listing

尝试输入5000 - 很可能也会导致堆栈溢出。你的系统有多少内存？ - Silas

你是在问为什么你的堆栈有特定的大小？ - Drew Dormann

Answer 1

每当您调用一个函数（包括递归调用），返回地址和通常的参数都会被推入调用栈。栈是有限的，所以如果递归太深，您最终将耗尽栈空间。

令我惊讶的是，只需要在您的计算机上进行4793次调用就会溢出栈。这是一个相当小的栈。相比之下，在我的电脑上运行相同的代码需要大约多达100倍的调用才能导致程序崩溃。

栈的大小是可配置的。在Unix上，命令是ulimit -s。

考虑到这个函数是尾递归的，一些编译器可能可以通过将其转换为跳转来优化递归调用。一些编译器甚至可以进一步处理您的示例：当要求最大优化时，gcc 4.7.2将整个函数转换为：

int returnZero(int anyNumber) {
  return 0;
}

这需要精确地两个汇编指令：

_returnZero:
        xorl    %eax, %eax
        ret

相当不错。

- NPE

---

他说它适用于 i = 4793，那么 i = 4792 也应该适用……或者不适用？ - Fernando

我曾认为，一旦函数递归调用自身，由原始函数调用创建的堆栈帧将从堆栈中弹出。这不是这种情况吗？ 同时感谢您的回复。 - charles

@charles：一般情况下是不行的。一个足够好的编译器可以优化一些情况，例如尾递归：http://en.wikipedia.org/wiki/Tail_call - NPE

NPE - 哇，太棒了。我从来没有想到过。最后一个问题，每次递归调用时，新的调用是创建一个新的堆栈帧还是只使用已创建的原始堆栈帧？ - charles

@charles：新的堆栈帧。就像任何其他函数调用一样。 - NPE

能否将函数分配到堆上，而不是栈上？（以防止栈溢出） - Spade 000

Answer 2

你刚刚触及了系统的调用栈大小限制，这就是正在发生的事情。由于某种原因，你的系统中的调用栈非常小，4793个函数调用的深度相当小。

- Óscar López

Answer 3

您的栈大小有限，因此当您进行4793次调用时，会达到限制，而在4792次调用下仅会略微低于。每个函数调用都会使用一些空间在栈中进行 housekeeping 和可能的参数传递。

该页面提供了一个 示例，展示了递归函数调用期间栈的样子。

- Shafik Yaghmour

Answer 4

我猜你的堆栈大小恰好足够容纳4792个条目 - 今天。明天或后天，这个数字可能会有所不同。递归编程可能很危险，这个例子说明了为什么。我们尽量不让递归变得如此深入，否则可能会发生“坏事”。

- Michael Dorgan

Answer 5

任何“无限制”的递归，即递归调用不自然地限制在一个较小的数量上，都会产生这种效果。具体的限制取决于操作系统、调用递归函数的环境（编译器、哪个函数调用递归函数等等）。如果您在调用递归函数的函数中添加另一个变量，比如int x[10];，需要使其崩溃的数量将会改变（可能会增加约5个）。使用不同的编译器进行编译（甚至是不同的编译器设置，例如打开了优化），它可能会再次改变。

- Mats Petersson

Answer 6

使用递归，您可以实现超级数字：

public class SuperDigit
{
    static int sum = 0;

    int main()
    {
        int n = 8596854;
        cout<<getSum(n);
    }

    int getSum(int n){
        sum=0;
        while (n > 0) {
            int rem;
            rem = n % 10;
            sum = sum + rem;
            n = n / 10;
            getSum(n);
        }
        return sum;
    }
}

- Sufiyan Ansari