18

我是 C++ 的初学者。昨天我读到了递归函数,所以我决定自己写。这是我写的:

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

当我这样做时:int zero1 = returnZero(4793);,它会导致堆栈溢出。但是,如果我将值 4792 作为参数传递,则不会发生溢出。

关于为什么的任何想法?

4

6 回答 6

41

每当您调用函数时,包括递归调用,返回地址和参数通常都会被压入调用堆栈。堆栈是有限的,所以如果递归太深,你最终会用完堆栈空间。

令我惊讶的是,你的机器上只需要 4793 次调用就可以溢出堆栈。这是一个很小的堆栈。相比之下,在我的计算机上运行相同的代码需要大约 100 倍的调用次数才能使程序崩溃。

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

鉴于该函数是tail-recursive,一些编译器可能能够通过将递归调用转换为跳转来优化递归调用。一些编译器可能会更进一步地采用您的示例:当被要求进行最大优化时,gcc 4.7.2将整个函数转换为:

int returnZero(int anyNumber) {
  return 0;
}

这需要两个汇编指令:

_returnZero:
        xorl    %eax, %eax
        ret

挺整洁的。

于 2013-04-12T16:24:36.643 回答
3

您刚刚达到了系统调用堆栈的大小限制,这就是正在发生的事情。由于某种原因,您系统中的堆栈很小,4793 个函数调用的深度相当小。

于 2013-04-12T16:24:13.263 回答
2

你的筹码量是有限的,所以当你跟注时,你只是在4793下注的时候就达到了上限4792。每个函数调用都将使用堆栈上的一些空间来进行管理和参数。

本页提供了一个递归函数调用期间堆栈的示例。

于 2013-04-12T16:24:37.507 回答
1

我的猜测是你的堆栈足够大,可以容纳 4792 个条目 - 今天。明天或下一个,这个数字可能会有所不同。递归编程可能很危险,这个例子说明了原因。我们尽量不让递归变得如此深或“坏”的事情可能发生。

于 2013-04-12T16:25:06.293 回答
1

任何“无限”递归,即自然不限于小(ish)数字的递归调用都会产生这种效果。限制的确切位置取决于操作系统、调用函数的环境(编译器、哪个函数调用递归函数等)。

如果您添加另一个变量,例如int x[10];调用您的递归函数的函数,则崩溃所需的数字将会改变(可能大约为 5 左右)。

用不同的编译器(甚至不同的编译器设置,例如打开优化)编译它,它可能会再次改变。

于 2013-04-12T16:29:07.830 回答
0

使用递归,可以实现 SuperDigit:

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;
    }
}
于 2016-09-28T17:18:52.133 回答