递归与for循环——阶乘，Java

Question

这两种获取阶乘的方法（循环 vs 递归），哪一种更高效/更快？如果其中一种可以改进，如何改进？

语言：Java

private static long factrecur(int n) {
    if (n == 0) {
        return 1;
    }
    else {
        return n * factrecur(n-1);
    }

}

private static long factloop(int a) {
    long total = 1;
    for (int b=a;b>=1;b--) {
        total *= b;
    }
    return total;
}

- Deley

---

total *= hi; - hi是什么？ - Pangolin

你有进行基准测试吗？测试结果告诉了你什么？ - Mat

哦，抱歉nideo，我正在文本编辑器上重命名变量，忘记改了。我不确定如何进行基准测试，但我会查一下。 - Deley

与其说 b>=1，不如说 b>0，因为通常有低级指令与0进行比较，这将使代码更快。 - luketorjussen

对于循环和递归，循环肯定比递归更好，而且在n非常大的情况下，后者可能会导致堆栈溢出（无恶意意图 :)）。 - Rajeev Sreedharan

在循环中，您不需要乘以1。使用;b>1;就足够了。 - Peter Lawrey

Answer 1

由于没有方法调用的开销，for循环将更有效率。(通常情况下，循环比递归更加高效)

要解释为什么需要深入了解调用方法和所谓的调用堆栈发生的细节。

基本上，当您调用方法时，它需要一些空间来使用(例如其本地变量等)，还需要空间来存储传递给它的输入参数以及一个存储其执行完毕后应该去哪里的返回地址的位置。这个空间是通过将值“推”到堆栈上动态提供的。该堆栈空间保持占用状态，直到该方法返回，此时它被“弹出”。

因此，在这种情况下考虑递归：每次从自身内部调用该方法时，都会将更多数据推入堆栈中，而不从调用方方法返回(因此也不会释放占用调用方方法的堆栈空间)。随着递归越来越深入，内存的使用量也会增加。

相比之下，您编写的for循环只是使用由一个堆栈帧推送提供的固定内存量。

- Matthew

---

当然，除非您使用一些函数式语言并从尾递归中获益。 - Rostislav Matl

一个对于 long 的调用会因为 factorial(21) 而溢出，这是一个很小的数字，但却会导致性能问题。对于更大的数字，代码将会失败 - 对于非常频繁的调用，使用哈希表比重复循环更快。多次调用 BigInteger 可能仍然可以通过哈希表在后台更快地执行。不要忘记：过早地优化是万恶之源。 - user unknown

是的，你们都提出了非常有价值的观点，但我认为你们有点过度设计。我怀疑Deley并不是真的想找到计算阶乘的最佳方法，而只是想在作业上得到一些帮助... - Matthew

哦，看来我忘记了这篇帖子。这个问题不是作业，我是自学Java的。 - Deley

Answer 2

使用21次调用，您的长整型将会溢出，这样很早就能测量差异，这可能是相关的。

当测量factorial(10*1000*1000) 或者类似大小的数值时，您可能需要使用BigInteger来衡量显著的差异。如果您没有高数字需要计算，但经常计算低阶乘，那么使用预先计算过的哈希表值会比递归和循环更快。

- user unknown

---

+1：我会说，在担心性能之前，请确保它很重要。 - Peter Lawrey

Answer 3

递归的唯一问题在于每次调用函数时，它的地址都会被放置在堆栈顶部，如果递归调用次数很高，则连接大量调用可能会导致堆栈溢出异常。

- aleroot