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

Question

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

程序如下:

#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 时，它会导致 分段故障(核心转储)

以下内容摘自 gdb 消息。

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

我的问题:

1. C 中的递归深度 是否有任何硬连线限制？或者 递归深度 是否取决于可用的堆栈内存？

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

Answer 1

通常，限制将是堆栈的大小。每次调用函数时，都会吃掉一定量的堆栈(通常取决于函数)。吃掉的量是栈帧，函数返回时收回。堆栈大小在程序启动时几乎是固定的，或者由操作系统指定(并且通常在那里可以调整)，或者甚至在程序中被硬编码。

• 一些实现可能有一种技术，可以在运行时分配新的堆栈段。但总的来说，他们不会。

• 有些函数会以更难以预测的方式使用堆栈，例如当它们在那里分配一个可变长度数组时。

• 一些函数可能被编译为以保留堆栈空间的方式使用尾调用。有时您可以重写您的函数，以便所有调用(例如对其自身的调用)在它最后执行的操作中发生，并期望您的编译器对其进行优化。

函数的每次调用到底需要多少栈空间并不是那么容易看出来的，这要看编译器的优化程度。在您的情况下，一种便宜的方法是每次调用时打印 &n ； n 可能在堆栈上(特别是因为程序需要获取它的地址——否则它可能在寄存器中)，并且它的连续位置之间的距离将指示堆栈的大小框架。