C中的无限递归
给定C程序无限递归：
int main() { main(); return 0; } 为什么会导致堆栈溢出。 我知道这导致C ++中来自以下线程的未定义行为这是无限递归UB吗？ （并且作为侧节点，不能在C ++中调用main() ）。 但是，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这是否会导致堆栈溢出？ （已得到充分回答）
无论何时调用函数，参数都会被压入堆栈，这意味着堆栈段上的数据被“分配”。 调用该函数时，返回地址也会被CPU压入堆栈，因此它知道返回的位置。
在你的示例中，这意味着没有使用任何参数，因此推送的唯一内容是返回地址，它相当小（x86-32 architexture上为4个字节），另外还调整了堆栈帧，需要另外四个字节在这个架构上。
由此得出结论，一旦堆栈段耗尽，该函数就不能被称为aynmore，并且exception被提升到OS。 现在可能发生两件事。 操作系统会将exception转发回您的应用程序，您将看到堆栈溢出。 或者操作系统可以尝试为堆栈segemnt分配额外的空间，直到达到定义的限制，之后应用程序将看到堆栈溢出。
所以这段代码（我把它重命名为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
UPDATE
关于定义递归的标准C99，到目前为止我发现的最好的是第6.5.2.2节第11段：
应允许递归函数调用，直接或间接通过任何其他函数链。
当然，这并不能回答它是否定义了堆栈溢出时会发生什么。 但是至少它允许以递归方式调用main，而在C ++中明确禁止它（第3.6.1节第3段和第5.2.2节第9段）。
程序是否无限递归是不可判定的。 没有合理的标准会要求一个甚至不能validation合规程序的属性，因此没有C标准，当前或未来，对无限递归都没有任何说法（就像没有C标准最终要求合规程序一样）停）。
递归是一种迭代，在移动到下一次迭代之前隐式保留本地状态。 通过考虑只是一个接一个地相互调用的常规函数来解释这一点很容易：
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_#()基本上彼此相同，但是每个iteration_#()都有自己的x ，并且每个iteration_#()都记得哪个函数调用了它，因此当它调用的函数完成时它可以正确地返回给调用者。 当程序转换为递归版本时，此概念不会更改：
void iteration (int x) { if (x > 0) return; iteration(x + 1); }
如果删除了停止条件（ if检查从函数return ），则迭代变为无限。 递归没有返回。 因此，为每个连续的函数调用（本地x和调用者的地址）记住的信息不断堆积，直到OS耗尽内存来存储该信息。
可以实现一个不会溢出“堆栈”的无限递归函数。 在足够的优化级别，许多编译器可以应用优化来移除记忆尾递归调用所需的内存。 例如，考虑该计划：
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）
声明标识符没有链接且没有存储类指定静态的对象具有自动存储持续时间，一些复合文字也是如此。 …
对于没有可变长度数组类型的此类对象，其生命周期从entry进入与其关联的块，直到该块的执行以任何方式结束。 （输入一个封闭的块或调用一个函数会暂停，但不会结束当前块的执行。）如果以递归方式输入该块，则每次都会创建一个新的对象实例。 …
对于具有可变长度数组类型的此类对象，其生命周期从对象的声明扩展，直到程序的执行离开声明的范围。 如果以递归方式输入范围，则每次都会创建该对象的新实例。
该标准涉及许多地方的内存分配失败，但从不在具有自动存储持续时间的对象的上下文中。 未在标准中明确定义的任何内容都是未定义的，因此无法分配具有自动存储持续时间的对象的程序具有未定义的行为。 这同样适用于只有很长的函数调用链或太多递归调用的程序。
无论何时进行函数调用（包括main（）），函数调用“info”（例如参数）都会被推到堆栈顶部。 函数返回时，此信息将从堆栈中弹出。 但正如您在代码中看到的那样， 在返回之前对main进行递归调用，因此堆栈会一直在增长，直到达到其限制并因此导致分段错误。
堆栈的大小通常是有限的，并在运行之前决定（例如通过您的操作系统）。
这意味着堆栈溢出不仅限于main（），而是任何其他递归函数，没有适当的方法来终止它的树（即基本情况）。
即使函数不使用堆栈空间用于局部变量或参数传递，它仍然需要存储返回地址和（可能）帧的基指针（使用gcc，这可以通过-fomit-frame-pointer禁用）。
在足够高的优化级别上，如果适用的尾调用优化 ，编译器可能能够将递归重写为循环，这将避免堆栈溢出。
解决问题1 ：
我想知道C中是否允许无限递归？
本文由John Regehr Compilers and Termination Revisited John Regehr Compilers and Termination Revisited是关于C standard是否允许无限递归的答案，在梳理完标准后，对我来说结论是模糊的并不太令人惊讶。 本文的主要内容是关于无限循环以及是否支持各种语言（包括C和C++ ）的标准来进行非终止执行。 据我所知，讨论同样适用于无限递归，当然假设我们可以避免堆栈溢出。
与第1.10 Multi-threaded executions and data races节中所述的C++不同， 1.10 Multi-threaded executions and data races第24段：
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节6.5.2.2 Function calls第11段中说明：
应允许递归函数调用，直接或间接通过任何其他函数链。
它没有对递归设置任何限制，并在第5.1.2.3 Program execution节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一样明确是否允许这种行为。
由于似乎对第二个条件存在两种合理但相互矛盾的解释，因此标准是有缺陷的，应明确定义是否允许这种行为。
主存储器的堆栈部分不是无限的，因此如果以递归方式无限次地调用函数，则堆栈将填充有关每个单个函数调用的信息。 当没有更多空间用于任何其他函数调用时，这会导致堆栈溢出 。
理解C中调用函数堆栈的方式非常重要：
C中是否允许无限递归？ 简单的答案是肯定的。 编译器允许您无限地调用函数，直到用完堆栈空间为止; 它不会阻止你这样做。
无限递归是否可能 ？ 不。如前所述，每次调用函数都需要在程序堆栈上推送返回地址，以及函数运行所需的任何参数。 您的程序只有有限的堆栈大小，一旦您用完堆栈，您的应用程序将失败。
假的无限递归是否可能？ 是。 可以设计一个函数，它自己调用1000次然后允许自己从1000个函数调用中退出，这样堆栈只有堆栈上的原始函数调用…然后重复整个过程无限循环。 我不认为这是真正的无限递归。
在C中允许无限递归。在编译时，编译器将允许这样做，但是这样做可能会出现运行时错误。
这是允许的，因为标准说 – >
应允许递归函数调用，直接或间接通过任何其他函数链。
在6.5.2.2 – > 11
并且Stackoverflow只是简单地发生，因为调用范围的每个状态都必须存储，所以如果必须存储无限的范围状态，那么你的内存耗尽，因为你没有无限的内存空间。 这是定义的行为，因为它发生在运行时，如果递归被破坏，编译器不需要检查标准。
原因堆栈是有限的，无论何时调用一个函数，它都会保存被调用者（通过将基指针推入堆栈并将当前堆栈指针复制为新的基本指针值）因此消耗堆栈将溢出无限次调用。 请参阅调用约定以及堆栈在此处的反应（ http://www.csee.umbc.edu/~chang/cs313.s02/stack.shtml ）
我只是看了复制最近的草案c标准文档 ，没有一个递归引用谈论无限递归。
如果标准文档不要求编译器支持某些东西并且不禁止它，那么编译器开发人员将考虑这种未定义的行为。