C中的递归深度是否有任何硬连线限制

Question

正在讨论的程序试图计算sum-of-first-n-natural-numbers使用recursion.我知道这可以使用一个简单的公式来完成,n*(n+1)/2但这里的想法是使用recursion.

该计划如下:

#include <stdio.h>

unsigned long int add(unsigned long int n)
{
    return (n == 0) ? 0 : n + add(n-1); 
}

int main()
{
    printf("result : %lu \n", add(1000000));
    return 0;
}

该计划运作良好,n = 100,000但当价值n增加到1,000,000它导致aSegmentation fault (core dumped)

以下内容取自该gdb消息.

Program received signal SIGSEGV, Segmentation fault.
0x00000000004004cc in add (n=Cannot access memory at address 0x7fffff7feff8
) at k.c:4

我的问题:

1. 是否有任何硬连接限制recursion depth的C？或者recursion depth取决于可用的堆栈内存？

2. 程序收到reSIGSEGV信号的可能原因是什么？

Answer 1

通常,限制将是堆栈的大小.每次调用函数时,都会吃掉一定量的堆栈(通常取决于函数).吃掉的数量是堆栈帧,并在函数返回时恢复.程序启动时,堆栈大小几乎几乎是固定的,要么是由操作系统指定的(通常可在那里调整),要么甚至在程序中进行硬编码.

• 某些实现可能具有一种技术,可以在运行时分配新的堆栈段.但总的来说,他们没有.

• 有些函数会以稍微不可预测的方式使用堆栈,例如当它们在那里分配可变长度数组时.

• 可以编译某些函数以便以保留堆栈空间的方式使用尾调用.有时您可以重写您的函数,以便所有调用(例如它自己)作为它做的最后一件事发生,并期望您的编译器优化它.

要确切地看到每次调用函数需要多少堆栈空间并不容易,并且它将受制于编译器的优化级别.在你的情况下,一个廉价的方法是&n每次打电话打印; n可能会在堆栈上(特别是因为程序需要获取其地址 - 否则它可能在寄存器中),并且它的连续位置之间的距离将指示堆栈帧的大小.

Answer 2

C 中的递归深度没有理论上的限制。唯一的限制是您的实现，通常是有限的堆栈空间。
（请注意，C 标准实际上并不需要基于堆栈的实现。我不知道任何非基于堆栈的实际实现，但请记住这一点。）

SIGSEGV 可能由多种原因引起，但超出堆栈限制是一种相对常见的情况。取消引用坏指针是另一回事。

Answer 3

1）可以减少堆栈的消耗，并将其写为尾递归优化。

gcc -O3程序

#include <stdio.h>

unsigned long long int add(unsigned long int n, unsigned long long int sum){
    return (n == 0) ? sum : add(n-1, n+sum); //tail recursion form
}

int main(){
    printf("result : %llu \n", add(1000000, 0));//OK
    return 0;
}