阶乘方法-递归还是迭代？（Java）

Question

我正在完成欧拉计划中的一个项目，遇到了一个组合问题。 组合逻辑意味着计算阶乘。 因此，我决定创建一个阶乘方法。 随后我遇到了一个问题-既可以使用迭代也可以使用递归来完成，那么我应该选择哪个？我很快写了两种方法-迭代：

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;
        }

并且递归:

public static long factorial(int num) {
        if(num == 0) {
            return 1;
        }
        else {
            return num * factorial(num - 1);
        }
    }

如果我（显然）在谈论速度和功能，那么我应该使用哪种技术？并且，一般来说，这两种技术中有一种更好吗？（所以如果我以后遇到这个选择，应该选择哪个？）

- Bluefire

---

可能是递归是否比循环更快？的重复问题。 - Kazekage Gaara

@luketorjussen - 因为我处理的数字很少，而且我只调用该方法一两次，所以我不会注意到差异。我所说的是如果我使用这个方法很多很多次，或者更复杂的方法可以使用两种技术。 - Bluefire

为什么不试试两种方法，看看哪个更快？此外，如果 num == 1，则无需再检查 num == 0，你可以直接返回1，这样就不需要额外的迭代/函数调用了。 - luketorjussen

@Bluefire，那为什么不试着用大数并多次调用它呢？ - luketorjussen

迭代版本似乎过于复杂。它可以简化为 int res = 1; for (int i = 2; i <= num; ++i) res *= i; return res;。 - Niklas B.

在Java中，迭代比递归更快 - 但这可能并不重要（递归具有方法调用开销，可能无法优化 - 而且据我所知，Java还不是Scheme）。更多信息请参见：http://chaosinmotion.com/blog/?p=622 - esej

Answer 1

这两种方法都太简单而不实用。对于阶乘的严肃应用，没有一种方法是高效的。我认为对于大的n值，这两种方法都不够高效，并且当参数很大时，既不能使用int也不能使用long。

更好的方法是使用优秀的伽玛函数实现和记忆化。

这里提供了一个由Robert Sedgewick实现的示例。

大的值需要使用对数。

- duffymo

---

我认为编辑后更好 :) 撤回我之前的评论。 - Niklas B.

Answer 2

每当你需要在递归和迭代之间做出选择时，总是选择迭代，因为：

1.递归涉及创建和销毁堆栈帧，这具有较高的成本。

2.如果使用的值非常大，你的堆栈可能会炸掉。

所以只有当你有一些非常诱人的理由时才选择递归。

- Ahmad

---

创建和销毁堆栈帧没有很高的代价。像此类的尾递归可以被语言处理器优化掉。递归通常是表达计算的更自然的方式，而且成本可以忽略不计。 - user207421

Answer 3

我是一名有用的助手，可以为您进行文本翻译。以下是需要翻译的内容：

实际上，我正在通过时间因素分析这个问题。 我已经完成了两个简单的实现：

迭代：

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;
}

并且是递归的：

public static BigInteger bigRecursiveFactorial(int x) {
    if (x == 0)
        return BigInteger.ONE;
    else
        return bigRecursiveFactorial(x - 1).multiply(BigInteger.valueOf(x));
}

测试单线程运行情况。结果表明，迭代方法只在参数较小的情况下略微更快。当我将n设为大于100时，递归解法更快。我的结论是？在JVM上永远无法说迭代解法比递归解法更快。（仅讨论时间方面）

如果您有兴趣，我得出这个结论的整个过程在这里。

如果您对这两种方法之间的区别有更深入的了解，我在knowledge-cess.com上找到了一个非常好的描述。

- Filip Kubala

Answer 4

对于这个问题，没有“这个更好，那个更差”的说法。因为现代计算机非常强大，在Java中使用哪种方法往往是个人偏好。在迭代版本中，您正在执行更多的检查和计算，但在递归版本中，您正在堆叠更多的方法。每种方法都有优缺点，所以必须具体情况具体分析。

就我个人而言，我坚持使用迭代算法来避免递归的逻辑。

- Odiefrom

---

在迭代版本中，您不需要进行更多的检查或计算。 - Niklas B.

@NiklasB。如果我没算错的话，他在迭代版本中进行了起始num == 0，i <= num，i++，result *= i的检查，而在递归版本中，他只有num == 0和num * factorial(num - 1)这两个条件，数量减半。 - Odiefrom

哦，你在谈论代码复杂度。在这种情况下，我同意。我以为你在谈论运行时复杂度（因为毕竟，在两个版本中将执行相同数量的乘法）。 - Niklas B.