哪种更快的Java,还是使用递归方法？

Question

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

Process.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

但我想知道建议使用哪种"技术"以及原因.

提前致谢.

Answer 1

由于方法调用开销和调用堆栈使用,递归将变慢.

Java没有执行尾调用优化,所以不要指望它.(虽然JVM上有一些语言可以进行尾调用优化,包括Clojure和Kotlin)

另一个缺点可能是StackOverflowError,如果你正在填写堆栈的风险.

如果你这样做只是为了尝试,我建议使用VisualVM,它可以在java JDK中找到.它是一个分析器,可用于对这种情况进行基准测试.

请注意, 我不建议使用递归只是为了花哨.如果你真的需要它(例如遍历树),请使用它.

Answer 2

您应该使用时间测量运行代码.这里有100个递归/ 100个循环的输出:

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

    }

}

Answer 3

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

此外,显然你不应该使用这种问题进行递归.它应该留给某些特定的任务,只有当你真的无法避免使用它们时.

此外,您还可以对代码进行基准测试,以查看哪个代码运行得更快.你会明白的.

Answer 4

递归调用将堆栈帧添加到调用堆栈.循环没有.循环通常比递归更快,除非递归是像分而治之的算法的一部分(你的例子不是).

您应该能够计算每个方法的执行时间,并找出一个方法比另一个方法快多少.

Answer 5

一般来说,我赞成迭代(例如一段时间或for循环)而不是递归,因为:

• 迭代更简单
• 如果你递得太深,你可以得到一个stackoverflow异常.迭代时不会发生这种情况.

Answer 6

通常,如果可能,递归被优化为循环,这意味着由于各种原因,包括堆栈帧分配和堆栈帧溢出,如果两个解在其他方面相等,则迭代优于递归.请参阅Tail Recursion
因此忽略了Java不优化Tail Recursion的事实,循环应该更快.

另外看看这个

Answer 7

在java中,与while循环相比,递归的成本很低,因为它需要分配新的堆栈帧.如果替代方法是显式管理堆栈,则递归可能会更快