16

给定具有无限递归的 C 程序：

int main() {

    main();

    return 0;
}

为什么会导致堆栈溢出。我从以下线程知道这会导致 C++ 中未定义的行为这是无限递归 UB 吗？（并且作为侧节点，不能main()在 C++ 中调用）。但是，valgrind 告诉我这会导致堆栈溢出：

Stack overflow in thread 1: can't grow stack to 0x7fe801ff8

最后程序由于分段错误而结束：

==2907== Process terminating with default action of signal 11 (SIGSEGV)
==2907==  Access not within mapped region at address 0x7FE801FF0

这是否也是 C 中未定义的行为，或者这是否真的会导致堆栈溢出，然后为什么会导致堆栈溢出？

编辑

1 我想知道C中是否允许无限递归？
2 这会导致堆栈溢出吗？（已充分回答）

4

15 回答 15

16

每当您调用函数时，参数都会被压入堆栈，这意味着堆栈段上的数据是“分配的”。当函数被调用时，返回地址也被 CPU 压入堆栈，因此它知道返回到哪里。

在您的示例情况下，这意味着不使用任何参数，因此唯一推送的是返回地址，该地址相当小（x86-32 架构上为 4 个字节），此外还调整了堆栈帧，需要另外四个字节在这个架构上。

由此可见，一旦堆栈段用完，就不能再调用该函数，并且向操作系统引发异常。现在可能会发生两件事。操作系统将异常转发回您的应用程序，您将看到堆栈溢出。或者操作系统可以尝试为堆栈段分配额外的空间，直到定义的限制，之后应用程序将看到堆栈溢出。

所以这段代码（我把它重命名为infinite_recursion（）因为main（）不能被调用）......

int inifinite_recursion(void)
{
    inifinite_recursion();
    return 0;
}

...看起来像这样：

_inifinite_recursion:
    push    ebp                    ; 4 bytes on the stack
    mov ebp, esp

    call    _inifinite_recursion   ; another 4 bytes on the stack
    mov eax, 0                 ; this will never be executed.

    pop ebp
    ret

更新

关于定义递归的标准 C99，到目前为止我发现的最好的是第 6.5.2.2 节第 11 段：

应允许通过任何其他函数链直接或间接调用递归函数。

当然，这并不能回答是否定义了堆栈溢出时会发生什么。但是至少它允许main递归调用，而这在 C++ 中是明确禁止的（第 3.6.1 节第 3 节和第 5.2.2 节第 9 节）。

于 2013-08-14T09:30:54.460 回答
10

程序是否无限递归是不可判定的。任何明智的标准都不会要求即使对于符合标准的程序也可能无法验证的属性，因此当前或未来的任何 C 标准都不会对无限递归有任何说法（就像没有 C 标准最终要求符合标准的程序一样）停）。

于 2013-08-20T11:41:47.017 回答
6

递归是一种在移动到下一次迭代之前隐式保留本地状态的迭代。通过考虑一个接一个地相互调用的常规函数​​，很容易理解这一点：

void iteration_2 (int x) {
    /* ... */
}

void iteration_1 (int x) {
    if (x > 0) return;
    iteration_2(x + 1);
}

void iteration_0 (int x) {
    if (x > 0) return;
    iteration_1(x + 1);
}

每个iteration_#()基本上都是相同的，但是每个都有它自己的x，并且每个都记住哪个函数调用了它，所以它可以在它调用的函数完成时正确地返回给调用者。当程序转换为递归版本时，这个概念不会改变：

void iteration (int x) {
    if (x > 0) return;
    iteration(x + 1);
}

如果停止条件（对函数的if检查return）被移除，则迭代变为无限。递归没有返回。因此，为每个连续的函数调用（本地x和调用者的地址）记住的信息会不断堆积，直到操作系统用完内存来存储该信息。

可以实现一个不会溢出“堆栈”的无限递归函数。在足够的优化级别上，许多编译器可以应用优化来删除为尾递归调用记住任何内容所需的内存。例如，考虑以下程序：

int iteration () {
    return iteration();
}

当用 编译时gcc -O0，它变成：

iteration:
.LFB2:
        pushq   %rbp
.LCFI0:
        movq    %rsp, %rbp
.LCFI1:
        movl    $0, %eax
        call    iteration
        leave
        ret

但是，当用 编译时gcc -O2，递归调用被删除：

iteration:
.LFB2:
        .p2align 4,,7
.L3:
        jmp     .L3

这种无限递归的结果是一个简单的无限循环，不会出现“堆栈”溢出。因此，由于允许无限循环，因此允许无限递归。

但是，您的程序不是尾调用优化的候选对象，因为递归调用不是您的函数所做的最后一件事。您的函数仍然有一个return跟随递归调用的语句。由于递归调用返回后仍有代码需要执行，优化器无法去除递归调用的开销。它必须允许调用正常返回，以便它之后的代码可以执行。因此，您的程序将始终为存储调用代码的返回地址而付出代价。

该标准没有以任何特定术语谈论“无限递归”。我收集了我认为与您的问题相关的内容。

  • 允许递归调用函数（C.11 §6.5.2.2 ¶11）

应允许通过任何其他函数链直接或间接调用递归函数。

  • 递归进入语句会创建局部变量的新实例（C.11 §6.2.4 ¶5,6,7）

其标识符声明为没有链接且没有存储类说明符 static 的对象具有自动存储持续时间，某些复合文字也是如此。...

对于这样一个没有可变长度数组类型的对象，它的生命周期从进入与其关联的块开始，直到该块的执行以任何方式结束。（进入封闭的块或调用函数会暂停，但不会结束当前块的执行。）如果递归地进入块，则每次都会创建对象的新实例。...

对于这种具有可变长度数组类型的对象，它的生命周期从对象的声明开始，直到程序的执行离开声明的范围。如果递归输入范围，则每次都会创建一个新的对象实例。

该标准在许多地方都谈到了内存分配失败，但从来没有在具有自动存储持续时间的对象的上下文中。标准中未明确定义的任何内容都是未定义的，因此无法分配具有自动存储持续时间的对象的程序具有未定义的行为。这同样适用于具有非常长的函数调用链或太多递归调用的程序。

于 2013-08-17T03:35:27.733 回答
3

解决问题1：

我想知道C中是否允许无限递归？

这篇文章Compilers and Termination Revisited是John Regehr关于是否C standard允许无限递归的答案，在梳理标准之后，我认为结论是模棱两可的，这并不奇怪。这篇文章的主旨是关于无限循环以及它是否被各种语言（包括C和C++）的标准支持以具有非终止执行。据我所知，讨论也适用于无限递归，当然假设我们可以避免堆栈溢出。

与段落段落C++中所说的不同：1.10 Multi-threaded executions and data races24

The implementation may assume that any thread will eventually do one of the
following:
  — terminate,
  [...]

这似乎排除了C++. draft C99 standard部分6.5.2.2 Function calls段落中说11：

应允许通过任何其他函数链直接或间接调用递归函数。

它没有对递归施加任何限制，并在段落5.1.2.3 Program execution段落中说明了这一点5：

The least requirements on a conforming implementation are:
— At sequence points, volatile objects are stable in the sense that previous 
  accesses are complete and subsequent accesses have not yet occurred.
— At program termination, all data written into files shall be identical to the
  result that execution of the program according to the abstract semantics would
  have  produced.
— The input and output dynamics of interactive devices shall take place as
  specified in 7.19.3. The intent of these requirements is that unbuffered or     
  line-buffered output appear as soon as possible, to ensure that prompting
  messages actually appear prior to a program waiting for input.

正如文章所说，第一个条件应该直接满足，文章中的第三个条件并没有真正涵盖终止。所以我们要处理第二个条件。根据文章是模棱两可的，文章的引用如下：

如果说的是在抽象机上运行的程序的终止，那么它是空谈的，因为我们的程序没有终止。如果它谈论终止编译器生成的实际程序，那么 C 实现是错误的，因为写入文件（stdout 是文件）的数据与抽象机写入的数据不同。（此读数应归功于 Hans Boehm；我未能从标准中挑出这种微妙之处。）

所以你有它：编译器供应商正在以一种方式阅读标准，而其他人（如我）以另一种方式阅读它。很明显，该标准存在缺陷：它应该像 C++ 或 Java 一样，明确说明是否允许这种行为。

由于似乎对第二个条件有两种合理但相互矛盾的解释，该标准是有缺陷的，应该明确定义是否允许这种行为。

于 2013-08-17T18:37:58.500 回答
3

每当您进行函数调用（包括 main()）时，函数调用“信息”（例如参数）就会被压入堆栈顶部。当函数返回时，此信息会从堆栈中弹出。但是正如您在代码中看到的那样，您在返回之前对 main 进行了递归调用，因此堆栈会继续增长，直到达到其限制并因此出现分段错误。

堆栈的大小通常在运行时之前受到限制和决定（例如，由您的操作系统决定）。

这意味着堆栈溢出不仅限于 main()，而是任何其他没有适当方法终止其树的递归函数（即基本情况）。

于 2013-08-14T09:08:54.280 回答
2

即使函数不为局部变量或参数传递使用堆栈空间，它仍然需要存储返回地址和（可能）帧的基指针（使用 gcc，这可以通过 禁用-fomit-frame-pointer）。

在足够高的优化级别上，如果尾部调用优化适用，编译器可能能够将递归重新写入循环，这将避免堆栈溢出。

于 2013-08-14T08:59:27.777 回答
1

C中允许无限递归吗？简单的答案是肯定的。编译器将允许您无限调用函数，直到堆栈空间用完为止；它不会阻止您这样做。

无限递归可能吗？不，正如已经指出的那样，对函数的每次调用都需要将返回地址以及函数运行所需的任何参数压入程序堆栈。您的程序只有有限的堆栈大小，一旦您用完堆栈，您的应用程序就会失败。

假的无限递归可能吗？是的。可以设计一个函数，调用自己1000次，然后让自己从这1000次函数调用中退出，这样栈就只有原来的函数调用在栈上……然后再重复整个过程一个无限循环。不过，我不考虑这种真正的无限递归。

于 2013-08-22T22:00:08.857 回答
1

了解 C 中函数调用堆栈的样子很重要：

函数栈

于 2013-08-17T17:55:50.807 回答
1

它在 c 中是允许的，因为标准说 ->

应允许通过任何其他函数链直接或间接调用递归函数。

在 6.5.2.2 -> 11

Stackoverflow 的发生很简单，因为调用作用域的每个状态都必须存储，所以如果必须存储无限的作用域状态，你的任何时候都会耗尽内存，因为你没有无限的内存空间。这是定义的行为，因为它发生在运行时，如果递归被破坏，编译器不需要检查标准。

于 2013-08-23T10:49:19.720 回答
1

C 中允许无限递归。在编译时，编译器会允许这样做，但这样做时可能会出现运行时错误。

于 2013-08-23T03:21:40.923 回答
1

主存的堆栈部分不是无限的，因此如果您无限次递归调用一个函数，堆栈将充满有关每个单个函数调用的信息。当没有更多空间可用于任何其他函数调用时，这会导致Stack Overflow 。

于 2013-08-14T08:57:08.120 回答
0

我只是查看了最近的c 标准文档草案的副本，并且没有任何递归引用谈论无限递归。

如果标准文档不要求编译器支持某些东西并且没有禁止它，那么编译器开发人员会考虑这种未定义的行为。

于 2013-08-23T01:42:56.470 回答
0

因为堆栈是有限的，每当你调用一个函数时，它都会保存被调用者（通过将基指针推入堆栈并将当前堆栈指针复制为新的基指针值）因此消耗堆栈将因无限次数的调用而溢出。在此处查看调用约定以及堆栈的反应方式（http://www.csee.umbc.edu/~chang/cs313.s02/stack.shtml）

于 2013-08-14T09:06:42.067 回答
0 
==2907== Process terminating with default action of signal 11 (SIGSEGV)
==2907==  Access not within mapped region at address 0x7FE801FF0

这意味着堆栈由于递归调用和增量而增长了很多，rsp以至于它访问了进程为线程堆栈映射的虚拟内存之外的内存地址。页面错误处理程序将注意到该进程尚未分配此虚拟内存区域，并将通过调用内核异常和堆栈展开过程将异常传播给程序。在 Windows 上，顶级 SEH 处理程序将从 kernel32.dll .pdata 部分调用，该部分将调用UnhandledExceptionFilter可以使用SetUnhandledExceptionFilter. 应用程序指定的这个例程可以调用GetExceptionCode来切换异常常量并显示相关的模态错误对话框。

于 2020-04-19T16:23:33.880 回答
0 
#include<iostream>
using namespace std;

int a();
int b();


int a()
{
    cout<<"Hello World\n";
    b();
    return 0;
}
int b()
{
    cout<<"Hello World\n";
    a();
    return 0;
}
void print(int b)
{
   cout << b << endl;
}
int main()
{
   int b = a();
   print(b);
   return 0;
}

此代码在 DevC++ 中返回此输出：

进程在 14.04 秒后退出，返回值 3221225725

您可以在此处查看此值的含义Dev C++ Process exited with return value 3221225725

因此，C++ 中的函数调用绑定了调用堆栈中的每个函数。你也知道，这是有限的大小，每个函数调用都会提高这个大小。

于 2020-04-21T11:42:01.473 回答