Recursion vs For循环 - Factorials,Java

Question

获得因子(循环与递归)的这两种方法中的哪一种更有效/更快？如果那个可以改进,怎么样？

语言:Java

private static long factrecur(int n) {
    if (n == 0) {
        return 1;
    }
    else {
        return n * factrecur(n-1);
    }

}

private static long factloop(int a) {
    long total = 1;
    for (int b=a;b>=1;b--) {
        total *= b;
    }
    return total;
}

Answer 1

for循环将更有效,因为方法调用没有开销.(作为一般规则,循环几乎总是比递归更有效)

解释为什么你必须深入了解调用方法和调用堆栈时会发生什么的细节.

基本上当你调用一个方法时,它需要一些空间来处理它(比如它的局部变量等),它还需要空间来传递给它的传入参数,以及一个存储它应该去的地方的返回地址的地方.它完成了执行.通过将值"推"到堆栈来动态提供此空间.该堆栈空间保持被占用,直到该方法返回,此时它被"弹出".

因此,请考虑在此上下文中的递归:每次从内部调用方法时,您都会将更多数据推送到堆栈中,而无需从您所处的方法返回(因此不会释放调用方法占用的堆栈空间).随着递归越来越深,内存量也会增加.

相比之下,您编写的for循环只使用一个堆栈帧推送提供的固定内存量.