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

问题描述

正在讨论该计划试图计算加总先正自然数使用递归。我知道这可以用一个简单的公式 N *进行（N + 1）/ 2 但这里的想法是使用递归。

程序如下：

 的#include＆LT;＆stdio.h中GT;unsigned long int类型的add（unsigned long int类型N）
{
    返程（N == 0）？ 0：N +新增（N-1）;
}诠释的main（）
{
    的printf（结果：吕％\\ n，加（1000000））;
    返回0;
}
 

该计划运作良好，对 N = 100,000 ，但当值 N 增加至<$ C $ ç> 1,000,000 它导致了分割故障（核心转储）

以下是从 GDB 消息服用。

 计划接收信号SIGSEGV，分割过错。
0x00000000004004cc在添加（N =无法访问地址0x7fffff7feff8内存
）在k.c：4
 

我的问题（S）：

1. 是否有 C 在递归深度任何硬连线的限制？还是在递归深度取决于可用的堆栈存储器？




2. 什么是为什么一个方案将得到一个reSIGSEGV信号可能的原因是什么？

解决方案

一般情况下，限制将是堆栈的大小。每次调用函数时，堆栈的一定量的食用（通常依赖于功能）。的食用量是堆栈帧，并且当该函数返回它被回收。堆栈大小几乎差不多固定在程序启动时，无论是从操作系统所指定的（而且通常有可调），甚至是在节目中硬codeD。

• 一些实现可能有一种技术，他们可以在运行时分配新的堆栈段。但在一般情况下，他们没有。




• 有些功能会消耗堆在稍微未predictable的方式，例如，当他们分配一个可变长度的数组那里。




• 某些功能可能编译的方式，将preserve堆栈空间使用尾部调用。有时你可以重写你的功能，使所有的呼叫（如以本身）发生，因为它做的最后一件事，并期望你的编译器优化它。

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

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.

The program is as follows:

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

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)

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

My question(s):

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

2. 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.

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屋！