C中的递归深度是否有任何硬连线限制 [英] Is there any hard-wired limit on recursion depth in C

问题描述

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

The program under discussion attempts to compute sum-of-first-n-natural-numbers using recursion. I know this can be done using a simple formula n*(n+1)/2 but the idea here is to use 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 
", add(1000000));
    return 0;
}

该程序对于 n = 100,000 运行良好，但是当 n 的值增加到 1,000,000 时，它会导致 Segmentation故障(核心转储)

The program worked well for n = 100,000 but when the value of n was increased to 1,000,000 it resulted in a Segmentation fault (core dumped)

以下内容来自 gdb 消息.

The following was taken from the gdb message.

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

我的问题:

1. C 中的递归深度 是否有任何硬性限制?还是 recursion depth 取决于可用的堆栈内存?

1. Is there any hard-wired limit on recursion depth in C? or does the recursion depth depends on the available stack memory?

程序收到 reSIGSEGV 信号的可能原因有哪些?

What are the possible reasons why a program would receive a reSIGSEGV signal?

推荐答案

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

Generally the limit will be the size of the stack. Each time you call a function, a certain amount of stack is eaten (usually dependent on the function). The eaten amount is the stack frame, and it is recovered when the function returns. The stack size is almost almost fixed when the program starts, either from being specified by the operating system (and often adjustable there), or even being hardcoded in the program.

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

• Some implementations may have a technique where they can allocate new stack segments at run time. But in general, they don't.

一些函数会以稍微更不可预测的方式消耗堆栈，例如当它们在那里分配一个可变长度数组时.

Some functions will consume stack in slightly more unpredictable ways, such as when they allocate a variable-length array there.

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

Some functions may be compiled to use tail-calls in a way that will preserve stack space. Sometimes you can rewrite your function so that all calls (Such as to itself) happen as the last thing it does, and expect your compiler to optimise it.

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

It's not that easy to see exactly how much stack space is needed for each call to a function, and it will be subject to the optimisation level of the compiler. A cheap way to do that in your case would be to print &n each time its called; n will likely be on the stack (especially since the progam needs to take its address -- otherwise it could be in a register), and the distance between successive locations of it will indicate the size of the stack frame.

这篇关于C中的递归深度是否有任何硬连线限制的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！