18

我有以下class两种方法的示例：

进程.java：

public class Process {

    public Process() {
    }

    public static void countRecursive(int num) {
        System.out.println("countRecursive: " + num++);
        if (num <= 10) countRecursive(num);
        else return;
    }

    public static void countWhile(int num) {
        do System.out.println("countWhile: " + num++);
        while (num <= 10);
    }

}

主类：

public static void main(String[] args) {        

    Process.countRecursive(0);
    Process.countWhile(0);

}

输出：

countRecursive: 0
countRecursive: 1
countRecursive: 2
countRecursive: 3
countRecursive: 4
countRecursive: 5
countRecursive: 6
countRecursive: 7
countRecursive: 8
countRecursive: 9
countRecursive: 10

countWhile: 0
countWhile: 1
countWhile: 2
countWhile: 3
countWhile: 4
countWhile: 5
countWhile: 6
countWhile: 7
countWhile: 8
countWhile: 9
countWhile: 10

但我想知道推荐使用哪种“技术”以及为什么。

提前致谢。

4

8 回答 8

35

由于方法调用开销和调用堆栈的使用，递归会变慢。

Java 也没有执行尾调用优化，所以不要指望它。（虽然 JVM 上有一些语言确实有尾调用优化，包括 Clojure 和 Kotlin）

另一个缺点可能是StackOverflowError如果您填满堆栈的风险。

如果您这样做只是为了尝试一下，我建议您使用可以在 java JDK 中找到的 VisualVM。它是一个分析器，可用于对这种情况进行基准测试（或者，如果您正在使用 OSS，您可以要求开源 YourKit 许可证）。

请注意， 我不建议仅仅为了花哨而使用递归。如果您真的需要它（例如遍历树），请使用它。

于 2012-12-19T15:56:12.367 回答
11

您应该运行带有时间测量的代码。这里有 100 次递归/100 次 while 循环的输出：

Recursive time: 90941
While time: 5180

这清楚地表明，while 循环比递归更快。

您可以通过运行以下代码来检查我的测量结果：

public class Process {

    public Process() {
    }

    public static void countRecursive(int num) {
        num++;
        if (num <= 100) countRecursive(num);
        else return;
    }

    public static void countWhile(int num) {
        do
            num++;
        while (num <= 100);
    }

    public static void main(String[] args) {
        Long start = System.nanoTime();        
        Process.countRecursive(0);
        System.out.println("Recursive time: " + (System.nanoTime() - start));
        Long startWhile = System.nanoTime();
        Process.countWhile(0);
        System.out.println("While time: " + (System.nanoTime() - startWhile));

    }

}
于 2012-12-19T17:08:16.990 回答
10

我不建议使用递归，因为每个递归都存储在堆栈中。因此，您需要为每个递归调用存储方法参数、局部变量等，以维护该调用之前的方法状态。

此外，您显然不应该对此类问题进行递归。它应该留给一些特定的任务，只有当你真的无法避免使用它们时。

此外，您还可以对代码进行基准测试，以查看哪个运行得更快。你会有一个想法。

于 2012-12-19T15:57:51.990 回答
7

递归调用将堆栈帧添加到调用堆栈。循环没有。循环通常比递归快，除非递归是诸如分治之类的算法的一部分（您的示例不是）。

您应该能够对每个方法的执行进行计时，并找出一个比另一个快多少。

于 2012-12-19T15:57:42.553 回答
6

一般来说，我更喜欢迭代（例如，while 或 for 循环）而不是递归，因为：

  • 迭代更简单
  • 如果递归太深，可能会得到 stackoverflow 异常。迭代不会发生这种情况。
于 2012-12-19T15:58:22.477 回答
6

通常，如果可能，递归会针对循环进行优化，这意味着由于各种原因，包括堆栈帧分配和堆栈帧溢出，如果两个解决方案在其他方面相等，则迭代优于递归。请参阅尾递归
因此忽略 Java 没有优化尾递归的事实，循环应该更快。

也看看这个

于 2012-12-19T15:59:27.363 回答
5

在 java 中，与 while 循环相比，递归的开销很小，因为它需要分配一个新的堆栈帧。在替代方案是显式管理堆栈的情况下，递归可能会更快

于 2012-12-19T15:57:08.090 回答
3

其他人说的都是真的。我想再补充一件事：对于您发布的问题，从 1 数到 10，使用递归或迭代都可以，因为它们运行的​​时间都可以忽略不计。一般来说，在现代计算机系统上，您无需过多担心完成一个进程需要多长时间（除非您正在处理大型数据集），因为内存非常便宜，而 CPU 非常强大。

通常，您首先使用良好的编程实践编写您感觉最舒服的程序。如果在那之后运行时间太长，那么你优化它。

并不是说在这个级别上比较迭代和递归是一件坏事。同样，迭代通常比递归更可取。我的观点是要吸取的教训是，虽然有一些方法可以让你的代码快速运行，但当你处理小型数据集时，你通常不需要担心它们 :)

于 2012-12-19T23:44:05.733 回答