递归与For循环-阶乘，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循环仅使用一次堆栈帧推送提供的固定内存量。