运行时exception,递归太深
我将伪代码转换为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; }
“c#编译器”将编译好。 但是,在运行时,您最终可能会遇到StackOverflowexception(在我的机器上,10,000个工作正常,但稍后会死)。
这不是“无限递归exception” – 堆栈溢出正是它所说的; 调用方法意味着将信息放在堆栈上并在调用返回时将其删除。 您有10,000个调用但没有返回,因此堆栈已满并抛出exception。
在这种特殊情况下,您可以通过删除递归并迭代运行来轻松解决此问题。 在一般情况下,有一些方法可以通过迭代,尾递归优化和连续传递来删除递归。
这是对迭代风格的快速直接转换:
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; }
所以每个人似乎都同意我需要将其转换为迭代…任何人都可以提供一些代码吗? 我似乎无法编写任何有效的迭代代码……
你是在索鱼还是要求学会如何捕鱼? 如果本练习的目的是学习如何将递归代码转换为迭代代码,那么只要得到答案就不能得到很好的服务。
要将递归代码转换为迭代代码,有很多可能的方法。 在这种情况下最简单的方法是简单地计算出模式。 代码做了什么? 它计算:
(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
不要使用递归。 这是一个很好的示例,当你不应该递归时,因为你会导致调用堆栈溢出。
您可以轻松地将其转换为非递归。
你不能阻止它,该函数调用自己太多次; 调用堆栈的深度有限,并且您的函数可以达到它。
要了解其他人在这里说的话 – 这是一个Stack Overflow(Woot!StackOverflow上的Stack Overflow问题。这可能导致堆栈……)
无论如何,每次调用递归方法时,它都会推送堆栈,也就是说它会将自身的引用放到堆栈上,这样当调用最后一次调用CalculatePi时,它可以解除所有其余的调用。
堆栈不是无限资源。 每次推送到堆栈都会占用一些内存,当你全部使用它时,会出现堆栈溢出。
递归调用不是尾递归的,即使它是,它也没有帮助,因为C#编译器当前不优化尾递归调用。 编辑:正如Eric Lippert和Gabe指出的那样,即使显式的尾调用指令不在发出的IL中,CLR也可以选择生成尾调用。
- 最好的方法是将这个递归解决方案变成迭代解决方案。
- 由于它几乎完成,快速破解可能是增加运行此方法的线程的堆栈大小。
请不要这样做。 仅限有趣:
static void Main() { Console.WriteLine(SafeCalculatePi(10000)); } // Calculates PI on a separate thread with enough stack-space // to complete the computation public static double SafeCalculatePi(int maxRecursion) { // We 'know' that you can reach a depth of 9217 for a 1MB stack. // This lets us calculate the required stack-size, with a safety factor double requiredStackSize = (maxRecursion / 9217D) * 1.5 * 1024 * 1024 ; double pi = 0; ThreadStart ts = delegate { pi = CalculatePi(maxRecursion); }; Thread t = new Thread(ts, (int)requiredStackSize); t.Start(); t.Join(); return pi; }
它不是无限递归,因为它在10,000级之后停止,但它仍然不是最好的主意。
一万个堆栈级别非常多 – 堆栈不是一个庞大的资源。 您应该将其转换为迭代解决方案。
由于您几乎能够运行该程序,因此您可以使用更少的堆栈空间。 只需在Release模式下运行而不是Debug,它应该可以工作。
执行此操作的迭代代码很简单:
private double CalculatePi(int iterations) { double pi = 1.0; for (int i = iterations - 1; i >= 1; i--) { pi = 1 + i / (2.0 * i + 1) * pi; } return pi * 2.0; }
用法:
double pi = CalculatePi(51);
这个woudl是非递归变体:
private double CalculatePi(int maxRecursion) { return 2 * CalculatePi2(maxRecursion, 1); } private double CalculatePi2(int maxRecursion, int i) { double product = 1; while (i < maxRecursion) { product = product * (1f + i / (2.0f * i + 1f)); i++; } return product; }
迭代版本:
public 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; }
递归函数调用几乎总是一种非常糟糕的做事方式。
我只是从头文件/数学库中获取pi的值。