java 阶乘方法 - 递归还是迭代？(爪哇)
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/11171648/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Factorial method - recursive or iterative? (Java)
提问by Bluefire
I was making my way through project Euler, and I came across a combination problem. Combination logic means working out factorials. So, I decided to create a factorial method. And then I hit upon a problem - since I could quite easily use both iteration and recursion to do this, which one should I go for? I quickly wrote 2 methods - iterative:
我正在通过 Euler 项目，遇到了一个组合问题。组合逻辑意味着计算阶乘。所以，我决定创建一个阶乘方法。然后我遇到了一个问题——因为我可以很容易地同时使用迭代和递归来做到这一点，我应该选择哪一个？我很快写了2个方法——迭代：
public static long factorial(int num) {
long result = 1;
if(num == 0) {
return 1;
}
else {
for(int i = 2; i <= num; i++) {
result *= i;
}
return result;
}
and recursive:
和递归：
public static long factorial(int num) {
if(num == 0) {
return 1;
}
else {
return num * factorial(num - 1);
}
}
If I am (obviously) talking about speed and functionality here, which one should I use? And, in general, is one of the techniques generally better than the other (so if I come across this choice later, what should I go for)?
如果我（显然）在这里谈论速度和功能，我应该使用哪一个？而且，一般来说，其中一种技术通常比另一种更好（所以如果我以后遇到这个选择，我应该怎么做）？
回答by duffymo
Both are hopelessly naive. No serious application of factorial would use either one. I think both are inefficient for large n, and neither intnor longwill suffice when the argument is large.
两者都是无可救药的天真。阶乘的认真应用不会使用任何一个。我认为无论是低效的大型N，既不int也不long时的说法是大就足够了。
A better way would be to use a good gamma functionimplementation and memoization.
更好的方法是使用良好的伽马函数实现和记忆。
Here'san implementation from Robert Sedgewick.
Large values will require logarithms.
大值将需要对数。
回答by Ahmad
Whenever you get an option to chose between recursion and iteration, always go for iteration because
每当您可以选择在递归和迭代之间进行选择时，请始终进行迭代，因为
1.Recursion involves creating and destroying stack frames, which has high costs.
1.递归涉及创建和销毁堆栈帧，成本较高。
2.Your stack can blow-up if you are using significantly large values.
2.如果您使用非常大的值，您的堆栈可能会爆炸。
So go for recursion only if you have some really tempting reasons.
所以只有当你有一些非常诱人的原因时才去递归。
回答by Odiefrom
There's no "this is better, that is worse" for this question. Because modern computers are so strong, in Java it tends to be a personal preference as to which you use. You are doing many more checks and computations in the iterative version, however you are piling more methods onto the stack in the recursive version. Pros and cons to each, so you have to take it case by case.
这个问题没有“这更好，那更糟”。因为现代计算机非常强大，所以在 Java 中它往往是您使用的个人偏好。您在迭代版本中进行了更多的检查和计算，但是在递归版本中您将更多的方法堆积到堆栈中。各有利弊，所以你必须逐案考虑。
Personally, I stick with iterative algorithms to avoid the logic of recursion.
就个人而言，我坚持使用迭代算法来避免递归逻辑。
回答by Filip Kubala
I was actually analyzing this problem by time factor. I've done 2 simple implementations:
我实际上是按时间因素分析这个问题的。我已经完成了 2 个简单的实现：
Iterative:
迭代：
private static BigInteger bigIterativeFactorial(int x) {
BigInteger result = BigInteger.ONE;
for (int i = x; i > 0; i--)
result = result.multiply(BigInteger.valueOf(i));
return result;
}
And Recursive:
和递归：
public static BigInteger bigRecursiveFactorial(int x) {
if (x == 0)
return BigInteger.ONE;
else
return bigRecursiveFactorial(x - 1).multiply(BigInteger.valueOf(x));
}
Tests both running on single thread. It turns out that Iterative is slightly faster only with small arguments. When I put n bigger than 100 recursive solution was faster. My conclussion? You never can say that iterative solution is faster than recursive on JVM. (Still talking only about time)
测试都在单线程上运行。事实证明，只有小参数时，迭代会稍微快一点。当我把 n 大于 100 时，递归解决方案会更快。我的结论？你永远不能说迭代解决方案比 JVM 上的递归解决方案更快。（仍然只谈时间）
If You're intrested, whole way I get this conclussion is HERE
如果你有兴趣，我得到这个结论的整个方式都在这里
If You're intrested in deeper understanding difference between this 2 approaches, I found really nice description on knowledge-cess.com
如果您有兴趣更深入地了解这两种方法之间的差异，我在knowledge-cess.com上找到了非常好的描述
