递归堆栈大小？

发布于 2024-12-06 08:34:36 字数 353 浏览 1 评论 0原文

class Program  
{
    static void Main(string[] args)
    {
        Test(0);
    }

    static void Test(int i)
    {
        if (i > 30000)
        {
            return;
        }
        Test(i + 1);
    }
}

为什么在调用上面的示例时获取递归函数并抛出 StackOverflowException。

（因为超过了默认的递归堆栈大小？）

但我想知道如何解决这个问题。

谢谢。

原文

class Program  
{
    static void Main(string[] args)
    {
        Test(0);
    }

    static void Test(int i)
    {
        if (i > 30000)
        {
            return;
        }
        Test(i + 1);
    }
}

Why getting recursive function and throwing StackOverflowException when calling this above sample.

(Because over the default recursive stack size ?)

but i wonder how to solve this problem .

Thanks.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

榕城若虚 2024-12-13 08:34:36

您会遇到异常，因为 30,000 个堆栈帧是一个相当大的数字:-)

您通过以更谨慎的方式使用递归来解决它。要递归解决的理想问题是那些快速减少“搜索空间”的问题^(a)。

例如，二叉树遍历，每次递归时搜索空间都会减半：

def find (searchkey, node):
    if node = NULL:
        return NULL
    if searchkey = node.key:
        return node
    if searchkey < node.key:
        return find (searchkey, node.left)
    return find (searchkey, node.right)

添加两个无符号整数（以及上面您自己的算法）不非常适合递归，因为您会耗尽堆栈在计算结果之前很久就进行分配。：

def add (a, b):
    if a = 0:
        return b
    return add (a-1, b+1)

^(a) 搜索空间可以定义为整个可能答案集。您想尽快减少它。

而且，顺便说一句，递归的理想问题与理论/数学意义上的堆栈空间无关，它们只是可以表示为的任何问题：

具有“更简单”参数的相同或相似问题。
带有“最简单”参数的终止条件。

（“简单”，在这个意义上，意味着接近终止条件）。

理论/数学方法不需要考虑堆栈空间，但我们作为计算机科学家必须考虑。现实设定了限制:-)

另请参阅我什么时候不使用递归？和将递归转换为迭代的情况。

You're getting an exception because 30,000 stack frames is a rather large number :-)

You solve it by using recursion in a more circumspect manner. The ideal problems to be solved recursively are those which reduce the "search space" quickly ^(a).

For example, binary tree traversal where your search space is halved each time you recur:

def find (searchkey, node):
    if node = NULL:
        return NULL
    if searchkey = node.key:
        return node
    if searchkey < node.key:
        return find (searchkey, node.left)
    return find (searchkey, node.right)

Adding two unsigned integers (and your own algorithm above) are not a good fit for recursion because you'll blow out your stack allocation long before the results are calculated.:

def add (a, b):
    if a = 0:
        return b
    return add (a-1, b+1)

^(a) Search space can be defined as your entire set of possible answers. You want to reduce it as quickly as possible.

And , as an aside, the ideal problems for recursion have nothing to do with stack space in a theoretical/mathematical sense, they're just any problem that can be expressed as:

the same or similar problem with a "simpler" argument.
a terminating condition with the "simplest" argument.

("simple" , in this sense, means approaching the terminating condition).

Theoretical/mathemeatical approaches wouldn't need to take stack space into account but we, as computer scientists, must. Reality sets limits :-)

回复收藏 0 原文

恋竹姑娘 2024-12-13 08:34:36

问题是你做了太多的递归。无论您在做什么，都会使用如此多的递归级别，都应该使用循环来解决。

与递归一起使用的算法不会对每个项目使用一级递归。通常，您会将每个级别的工作分成两半，因此 30000 个项目只需要 15 级递归。

回复收藏 0 原文

千と千尋 2024-12-13 08:34:36

您收到 StackOverflowException 是因为您的堆栈在对 Test 的 30k 次调用中的某处发生溢出。没有办法“解决”这个问题，堆栈大小是有限的（而且也很小）。您可以重新设计代码以迭代方式工作。

for( int i = 0; i <= 30000; ++i )
{
    Test( i );
}

但是，我认为您的实际用例比这更复杂；否则递归就没有任何好处。

You are getting a StackOverflowException because your stack overflows somewhere within those 30k calls to Test. There is no way to 'solve' the problem, the stack size is limited (and pretty small as well). You could redesign your code to work in an iterative fashion.

for( int i = 0; i <= 30000; ++i )
{
    Test( i );
}

However, I assume that your actual use case is more complicated than that; otherwise there is no gain from recursion.

回复收藏 0 原文

过气美图社 2024-12-13 08:34:36

虽然您可以手动指定新线程的堆栈大小，但我会使用 Stack或循环（这实际上是简化示例所需的全部内容）所以你根本不需要递归，即：

Stack<int> stack = new Stack<int>();
stack.Push(1);
while(stack.Count > 0)
{
    int someValue = stack.Pop();
    //some calculation based on someValue
    if(someValue < 30000)
        stack.Push(someValue +1);
}

While you could specify the stack size for a new thread manually, I'd use a Stack<T> or a loop (that's really all that's needed for your simplified example) so you don't need recursion at all, i.e.:

Stack<int> stack = new Stack<int>();
stack.Push(1);
while(stack.Count > 0)
{
    int someValue = stack.Pop();
    //some calculation based on someValue
    if(someValue < 30000)
        stack.Push(someValue +1);
}

回复收藏 0 原文