c# - 运行时异常，递归太深

Question

我转换了伪代码here进入 C#，并让它递归重复 10,000 次。但是我在 9217 次后收到 C# 运行时错误，StackOverflow Exception。我怎样才能避免这种情况？

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

    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

So everybody seems to agree that i need to convert this to iterative... can anybody give some code? I can't seem to write any iterative code that works...

您是要鱼，还是要教人如何捕鱼？如果本练习的目的是学习如何将递归代码转换为迭代代码，那么仅仅获得答案并不能很好地满足您的需求。

要将递归代码转换为迭代代码，有很多可行的方法。在这种情况下，最简单的方法就是简单地计算出模式。代码有什么作用？它计算:

(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 风格重写您的程序；然后沿途的每一步都会向调用者返回一个延续，调用者调用下一个延续；堆栈永远不会变深

解释这些技巧需要花很长时间才能找到一个答案。我有一个由六部分组成的博客系列，介绍如何使用这些技术将递归程序变成不消耗太多堆栈的程序；从这里开始阅读:

Link