5

我有这种计算一些统计数据的方法：

public void calculateAverage(int hour){

    if (hour != 20) {
        int data =0; 
        int times = 0;
        for (CallQueue cq : queues) {
            data += cq.getCallsByTime().get(hour);
            times++;
        }       
        averageData.add((double)data/times);
        calculateAverage(hour + 1);
    }
    
}

现在我很自豪我创建了一个递归方法，但我知道这可以通过循环来解决。

我的问题是：用递归还是循环解决这类问题更好？

4

5 回答 5

7

一般递归

通常，递归会更昂贵，因为每次函数递归时都必须使用变量副本修改堆栈。

需要保存一组地址和状态，以便递归过程可以在特定运行之后返回到正确的状态。

如果可能，迭代会更好。递归，当迭代只是不会削减它，或者会导致更复杂的代码。

代码维护

从维护的角度来看，调试迭代代码比递归过程容易得多，因为与考虑特定递归相比，理解任何特定迭代的状态相对容易。

你的代码

该过程调用自身，但每次运行与前一次运行的结果无关。每次运行都是独立的，通常是最大的损失，那里的递归可能没有必要。

在我看来，calculateAverage(hour + 1);应该将其移到函数之外，因为阅读您的代码的人也会更清楚。每个调用都是独立的。

于 2012-11-12T15:26:52.210 回答
2

在 Java、C 和 Python 中，与迭代（通常）相比，递归相当昂贵，因为它需要分配一个新的堆栈帧。在某些 C 编译器中，可以使用编译器标志来消除这种开销，它将某些类型的递归（实际上是某些类型的尾调用）转换为跳转而不是函数调用。（来源）

于 2012-11-12T15:29:03.847 回答
1

对于这个特殊问题，运行时差异不大。我个人更喜欢使用迭代，我认为它会更简单，更容易理解，但我想每个人都有自己的想法。

现在一些递归函数（例如递归斐波那契数）应该通过迭代来完成，因为它们可以有指数增长。

一般来说，我不使用递归，除非它会让我的问题更容易理解。

于 2012-11-12T15:27:11.070 回答
1

您应该调查周边情况。对于大递归堆栈可能会溢出，那就是 +1 for 循环。

我不确定哪一个跑得更快，但考虑到 JIT 和其他东西，这相对容易衡量。

代码维护方面：对于我们大多数人来说，理解和修复循环比递归要容易得多。开发人员的时间通常比细微的性能差异更重要。

于 2012-11-12T15:27:36.467 回答
1

这取决于上下文。例如，如果我有一个Composite对象树（在 SWT 中）并且您希望遍历它们，最简单的方法是使用这样的递归：

    private boolean checkControlParent(Composite comp) {
        boolean ret = false;
        if (comp != null) {
            if (this.equals(comp)) {
                ret = true;
            } else {
                ret = checkControlParent(comp.getParent());
            }
        }
        return ret;
    }

否则，如果性能很重要，请注意递归调用在大多数情况下比简单循环慢，因为函数/方法调用开销。

所以最重要的是，如果您需要遍历递归是自然解决方案的对象，并且您不必冒险StackOverflowError继续使用递归。否则，您可能会更好地使用循环。

还有一件事：递归方法有时往往更难阅读、理解和调试。

于 2012-11-12T15:28:12.793 回答