5

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

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

在我的电脑上，这个函数在大约 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);
}
4

8 回答 8

5

您很可能会溢出堆栈，此时您的程序将被立即终止。堆栈的深度总是会限制你可以递归的数量，如果你达到了这个限制，这意味着你的算法需要改变。

于 2011-05-18T14:03:02.317 回答
3

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

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

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

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

于 2011-05-18T14:12:06.440 回答
2

您正在导致堆栈溢出（堆栈空间不足），因为您没有提供退出条件。

void rek(double x){
   if(x > 10)
      return;
   std::cout << x << std::endl;
   rek(x + 1);
}
于 2011-05-18T14:04:38.480 回答
1

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

于 2011-05-18T14:06:34.117 回答
1

如果您想避免无限递归的堆栈溢出，不幸的是，您将不得不深入研究一些程序集以更改堆栈，以便新的激活记录不会不断地推入堆栈，在某些时候会导致溢出。因为您在函数的末尾进行递归调用，所以在递归流行的其他语言（即，Lisp、Scheme、Haskell 等）中调用它是一种跟踪调用优化。它通过基本上将尾调用转换为循环来防止堆栈溢出。在 C 中会是这样的（注意：我在 x86 上使用带有 gcc 的内联汇编，并且我将您的参数更改为intfromdouble为了简化组装。此外，我已从 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/等中的尾调用递归函数。不会溢出堆栈，因为当新函数调用作为现有函数的最后一条语句时，这种类型的堆栈操作是在后台为您完成的。

于 2011-05-18T15:37:01.423 回答
1

你期待这永远有效吗？

它不会。在某些时候，您将用完堆栈。

于 2011-05-18T14:03:36.317 回答
0

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

int main(...)
{
   double x = 1;
   while (true)
   {
       std:cout << x << std::endl;
       x += 1;
   }
 }
于 2011-05-18T14:07:31.317 回答
0

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

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

于 2011-05-18T14:11:43.070 回答