c++递归在没有明显原因的情况下退出

Question

我用递归写了一个函数。在测试时发现，该函数在没有任何明显原因的情况下被终止，而递归仍在运行。

为了测试这一点，我编写了一个无限递归。

在我的电脑上，该函数在大约 2 秒后退出，最后的输出约为 327400。 最后一个数字并不总是相同。

我使用 Ubuntu Lucid Lynx、GCC 编译器和 Eclipse 作为 IDE。如果有人知道问题是什么以及我如何阻止程序退出，我会非常高兴。

#include <iostream>

void rek(double x){
    std::cout << x << std::endl;
    rek(x + 1);
}

int main(int argc, char **argv) {
    rek(1);
}

Answer 1

您很可能会溢出堆栈，此时您的程序将被立即终止。堆栈的深度始终会限制您可以递归的数量，如果达到该限制，则意味着您的算法需要更改。

Answer 2

我认为您期望代码永远运行是正确的，如

如何检查 gcc 是否正在执行尾递归优化？

如果 gcc 正在执行尾递归，您的代码应该能够永远运行。在我的机器上，看起来 -O3 实际上使 gcc 生成尾调用并实际上压平了堆栈。 :-)

我建议您将优化标志设置为 O2 或 O3。

Answer 3

由于您没有提供退出条件，因此导致堆栈溢出（堆栈空间不足）。

void rek(double x){
   if(x > 10)
      return;
   std::cout << x << std::endl;
   rek(x + 1);
}

Answer 4

你希望这永远有效吗？

不会的。在某些时候你会耗尽堆栈。

Answer 5

这很有趣，在 stackoverflow.com 上谈论堆栈溢出。 ;) 调用堆栈是有限的（您可以从项目设置中自定义它），但在某些时候，当您有无限循环调用时，它将超出并且您的程序终止。

Answer 6

如果您想避免无限递归的堆栈溢出，那么不幸的是，您将不得不深入研究某些程序集以更改堆栈，以便新的激活记录不会不断地推入堆栈，这在某些时候会导致溢出。因为您在函数末尾进行递归调用，所以在递归流行的其他语言（即 Lisp、Scheme、Haskell 等）中，这被称为跟踪调用优化。它基本上通过将尾部调用转换为循环来防止堆栈溢出。在 C 中它会是这样的（注意：我在 x86 上使用带有 gcc 的内联汇编，并且我将你的参数从 double 更改为 int 以简化另外，我已从 C++ 更改为 C，以避免函数名称的名称修改。最后，每个语句末尾的“\n\t”不是实际的汇编命令，而是内联汇编所需要的。 gcc）：

#include <stdio.h>

void rek(int x)
{
    printf("Value for x: %d\n", x);

    //we now duplicate the equvalent of `rek(x+1);` with tail-call optimization

    __asm("movl 8(%ebp), %eax\n\t"   //get the value of x off the stack
          "incl %eax\n\t"            //add 1 to the value of x
          "movl 4(%ebp), %ecx\n\t"   //save the return address on the stack
          "movl (%ebp), %edx\n\t"    //save the caller's activation record base pointer
          "addl $12, %ebp\n\t"       //erase the activation record
          "movl %ebp, %esp\n\t"      //reset the stack pointer
          "pushl %eax\n\t"           //push the new value of x on the stack for function call
          "pushl %ecx\n\t"           //push the return value back to the caller (i.e., main()) on the stack
          "movl %edx, %ebp\n\t"      //restore the old value of the caller's stack base pointer
          "jmp rek\n\t");            //jump to the start of rek()
}

int main()
{
    rek(1);
    printf("Finished call\n");  //<== we never get here

    return 0;
}

在 Ubuntu 10.04 上使用 gcc 4.4.3 编译，它在无限循环中几乎“永远”运行，没有堆栈溢出，而如果没有尾部调用优化，它很快就会因分段错误而崩溃。从__asm部分的注释中可以看到堆栈激活记录空间是如何被“回收”的，以便每次新的调用都不会耗尽堆栈上的空间。这涉及到将键值保存在旧的激活记录中（前一个调用者的激活记录基指针和返回地址），并恢复它们，但参数会更改以供下一次递归调用该函数。

同样，其他语言（主要是函数式语言）执行尾部调用优化作为该语言的基本功能。因此，Scheme/Lisp/etc 中的尾调用递归函数。不会溢出堆栈，因为当新函数调用作为现有函数的最后一个语句时，这种类型的堆栈操作是在幕后完成的。

Answer 7

好吧，您已经定义了无限递归和堆栈溢出，这会杀死您的应用程序。如果你真的想打印所有数字；然后使用循环。

int main(...)
{
   double x = 1;
   while (true)
   {
       std:cout << x << std::endl;
       x += 1;
   }
 }

Answer 8

每个递归方法都应该实现一个退出条件，否则将会出现堆栈溢出并且程序将终止。

在您的情况下，您传递给函数的参数没有条件，因此，它会永远运行并最终崩溃。