运行时异常,递归太深

Question

我转换的伪代码这里到C#,并让它递归地重复10000次.但是我StackOverflow Exception经历了一次C#运行时错误9217.我怎么能阻止这个？

编辑如果它对任何人有帮助,这里是代码:

    private double CalculatePi(int maxRecursion)
    {
        return 2 * CalculatePi(maxRecursion, 1);
    }

    private double CalculatePi(int maxRecursion, int i)
    {
        if (i >= maxRecursion)
            return 1;
        return 1 + i / (2.0 * i + 1) * CalculatePi(maxRecursion, i + 1);
    }

    double pi = CalculatePi(10000); // 10,000 recursions

EDIT2所以每个人似乎都同意我需要将其转换为迭代...任何人都可以提供一些代码吗？我似乎无法编写任何有效的迭代代码......

编辑感谢Paul Rieck的这个答案,我测试了它,它的工作原理如下:

    private static double CalculatePi(int maxRecursion)
    {
        double result = 1;
        for (int i = maxRecursion; i >= 1; i-- )
        {
            result = 1 + i / (2.0 * i + 1) * result;
        }
        return result * 2;
    }

Answer 1

所以每个人似乎都同意我需要将其转换为迭代...任何人都可以提供一些代码吗？我似乎无法编写任何有效的迭代代码......

您是在索鱼还是要求学会如何捕鱼？如果本练习的目的是学习如何将递归代码转换为迭代代码,那么只要得到答案就不能很好地服务.

要将递归代码转换为迭代代码,有很多可能的方法.在这种情况下最简单的方法是简单地计算出模式.代码做了什么？它计算:

(1 + 1 / (2.0 * 1 + 1)) * 
(1 + 2 / (2.0 * 2 + 1)) * 
(1 + 3 / (2.0 * 3 + 1)) * 
(1 + 4 / (2.0 * 4 + 1)) * 
(1 + 5 / (2.0 * 5 + 1)) * 
(1 + 6 / (2.0 * 6 + 1)) * 
(1 + 7 / (2.0 * 7 + 1)) * 
...
(1 + 9999/ (2.0 * 9999+ 1)) *
1

你现在可以写一个计算它的循环吗？当然.

double product = 1.0;
for (int i = 9999; i >= 0; --i)
    product *= (1 + i / (2.0 * i + 1));

这是最简单的方法.但是有很多方法可以解决这个问题.

您可以使用聚合器.考虑"总"操作; 这是聚合器的一个例子.你有一系列的东西,你保持它们的总和,将结果累积在累加器中.标准查询运算符为您提供了聚合操作:

double seed = 1.0;
Enumerable.Range(0, 10000).Aggregate(seed, 
    (product, i) => product * (1 + i / (2.0 * i + 1))

或者,您可以保持算法递归,但通过以下方式消除堆栈溢出:

• 在堆上构建自己的堆栈结构
• 定义虚拟机,以虚拟机语言编写程序,然后实现虚拟机以将其堆栈保留在堆上.
• 在Continuation Passing Style中重写你的程序; 沿途的每一步都会向调用者返回一个延续,调用者会调用下一个延续; 堆栈永远不会变深

解释这些技术需要很长时间才能得到答案.我有一个由六部分组成的博客系列,介绍如何使用这些技术将递归程序转换为不会消耗太多堆栈的程序; 在这里开始阅读:

http://blogs.msdn.com/b/ericlippert/archive/2005/07/25/recursion-part-zero.aspx

Answer 2

"c#编译器"将编译好.但是,在运行时,您最终可能会遇到StackOverflow异常(在我的机器上,10,000个工作正常,但稍后会死).

这不是"无限递归异常" - 堆栈溢出正是它所说的; 调用方法意味着将信息放在堆栈上并在调用返回时将其删除.您有10,000次调用而没有返回,因此堆栈已满并抛出异常.

通过删除递归并迭代运行,您可以在这种特定情况下轻松解决此问题.在一般情况下,有一些方法可以通过迭代,尾递归优化和连续传递来删除递归.

这是对迭代风格的快速直接转换:

private static double CalculatePi(int maxRecursion)
        {
            double result = 1;
            for (int i = maxRecursion -1; i >= 1; i-- )
            {
                result = 1 + i / (2.0 * i + 1) * result;
            }
            return result * 2;
        }