8

我在完成 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;
        }

和递归：

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

如果我（显然）在这里谈论速度和功能，我应该使用哪一个？而且，一般来说，其中一种技术通常比另一种更好（所以如果我以后遇到这种选择，我应该选择什么）？

4

4 回答 4

15

两者都是无可救药的天真。任何一个严重的阶乘应用都不会使用。我认为两者对于大 n 来说都是低效的，当论点很大时，两者int都long不够。

更好的方法是使用良好的gamma 函数实现和记忆。

这是Robert Sedgewick 的一个实现。

较大的值将需要对数。

于 2012-06-23T17:55:30.667 回答
3

每当您可以在递归和迭代之间进行选择时，请始终进行迭代，因为

1.递归涉及创建和销毁栈帧，成本高。

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

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

于 2012-06-23T17:59:02.163 回答
1

我实际上是按时间因素分析这个问题。我做了两个简单的实现：

迭代：

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 上找到了非常好的描述

于 2016-07-09T10:30:05.547 回答
0

对于这个问题，没有“这更好，那更糟”。因为现代计算机非常强大，所以在 Java 中，它往往是您使用的个人偏好。您在迭代版本中进行了更多检查和计算，但是在递归版本中您将更多方法堆积到堆栈中。各有优劣，所以你必须逐案处理。

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

于 2012-06-23T17:59:11.643 回答