C中的无限递归

Question

给定具有无限递归的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这是否会导致堆栈溢出？(已经得到了充分的回答)

Answer 1

无论何时调用函数,参数都会被压入堆栈,这意味着堆栈段上的数据被"分配".调用该函数时,返回地址也会被CPU压入堆栈,因此它知道返回的位置.

在你的示例中,这意味着没有使用任何参数,因此推送的唯一内容是返回地址,它相当小(x86-32 architexture上为4个字节),另外还调整了堆栈帧,需要另外四个字节在这个架构上.

由此得出结论,一旦堆栈段耗尽​​,该函数就不能被调用,并且异常被提升到OS.现在可能发生两件事.操作系统将异常转发回您的应用程序,您将看到堆栈溢出.或者操作系统可以尝试为堆栈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段).

Answer 2

程序是否无限递归是不可判定的.没有明智的标准会要求一个甚至可能无法验证合规程序的属性,因此没有C标准,当前或未来,对无限递归都没有任何说法(就像没有C标准最终要求合规程序一样)停).

Answer 3

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

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.211)

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

• 递归进入语句会创建局部变量的新实例(C.11§6.2.45,6,7)

声明标识符没有链接且没有存储类指定静态的对象具有自动存储持续时间,一些复合文字也是如此....

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

对于具有可变长度数组类型的此类对象,其生命周期从对象的声明扩展,直到程序的执行离开声明的范围.如果以递归方式输入范围,则每次都会创建该对象的新实例.

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