递归堆栈大小？

Question

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

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

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

(因为超过默认的递归堆栈大小？)

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

谢谢.

Answer 1

问题是你做了太多的递归.无论你正在做什么,将使用如此多的递归级别,应该使用循环来解决.

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

Answer 2

你得到一个例外,因为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)搜索空间可以定义为整套可能的答案.您希望尽快减少它.

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

• 与"更简单"的论点相同或类似的问题.
• 具有"最简单"参数的终止条件.

(在这个意义上,"简单"意味着接近终止条件).

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

另请参见何时不使用递归？和将递归转换为迭代的情况.