是否有使用C递归深度任何硬连线的限制(Is there any hard-wired limit o

所讨论的程序试图以计算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它导致了Segmentation fault (core dumped)

以下是从所拍摄gdb消息。

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

我的问题（S）：

是否有任何硬连线的限制recursion depth在C ？抑或是recursion depth取决于可用的堆栈内存？
什么是为什么一个方案将得到一个reSIGSEGV信号可能的原因是什么？

Answer 1:

一般来说，极限将是堆栈的大小。每个调用一个功能时，堆叠的一定量的食用（通常依赖于功能）。的食用量是堆栈帧，并且当该函数返回它被回收。堆栈大小的程序启动时，无论是从由操作系统（并经常可调那里）被指定时，或在程序即使被硬编码几乎几乎固定的。

一些实施方式可以具有技术，其中它们可以在运行时分配新的堆栈段。但在一般情况下，他们没有。
一些功能将消耗在堆叠稍微更不可预知的方式，例如，当他们分配一个可变长度数组那里。
某些功能可能被编译的方式，将保留堆栈空间使用尾部调用。有时候，你可以重写你的功能，使所有的呼叫（如自身）发生，因为它做的最后一件事，并期待你的编译器优化。

这并不容易，看看到底有多少堆栈空间是需要每次调用一个函数，它会受到编译器的优化程度。一种廉价的方式做到这一点，你的情况是打印&n它的每一个所谓的时间; n将可能是在堆栈上（特别是自编程'需要采取其地址-否则它可能是在寄存器中），和它的连续位置之间的距离将指示堆栈帧的大小。

Answer 2:

没有理论上的限制递归深度C.唯一的限制是那些你的实现，一般限于堆栈空间。
（请注意，C标准实际上并不需要基于栈的实现。我不知道，不栈为基础的任何真实世界的实现，但记住这一点。）

一个SIGSEGV可以用任何数量的原因引起的，但超过你的堆栈限制是一种比较常见的一种。解引用一个坏的指针是另一回事。

Answer 3:

1）堆栈的消费预计会减小，并且写为尾递归优化。

GCC -O3 prog.c中

#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;
}