递归与For循环 - Factorial，Java [英] Recursion vs For loops - Factorials, Java

问题描述

获得阶乘（循环与递归）的这两种方法中哪一种更高效/更快？如果那一个可以改进的话，怎么样呢？

语言：Java

  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; 
} 
总回报; 
 
  

解决方案

<因为没有方法调用的开销，所以效率很高。 （作为一般规则，循环几乎总是比递归效率更高）

解释为什么你必须深入了解调用方法时发生的事情的细节，所谓的调用堆栈。

基本上，当你调用一个方法时，需要一点空间来处理（像局部变量等），传入的参数还需要一个空间来存放返回地址，它正在执行。这个空间是通过将值推送到一个栈来动态提供的。这个堆栈空间一直保持着被占用，直到方法返回时它被弹出。

所以在这种情况下，考虑递归：每次从内部调用方法你自己把更多的数据放到堆栈上，而不用从你所在的方法中返回（因此没有释放调用方法占用的堆栈空间）。当你的递归进行得更深的时候，内存的数量就会增加。

相比之下，你所写的for循环只是使用由一个栈帧提供的固定内存量。

Which of these two methods of getting a factorial (loop vs recursive) is more efficient/faster? and if that one can be improved, how so?

Language: 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;
}

解决方案

The for loop will be more efficient because there is no overhead of the method calls. (As a general rule loops are almost always more efficient than recursion)

To explain why you have to get into the nitty gritty details of what happens when you call a method and something called the call stack.

Basically when you call a method it needs a bit of space to work with (for things like its local variables etc) it also needs space for the incoming parameters being passed to it and a place to store the return address of where it should go when it is done executing. This space is dynamically provided by 'pushing' the values on to a stack. That stack space remains occupied until the method returns at which point it is 'popped off'.

So think about recursion in this context: every time you call the method from within itself you push more data onto the stack, without returning from the method you were in (and thus without freeing up the stack space the calling method was occupying). As your recursion goes deeper the amount of memory increases.

In contrast the for loop you wrote just uses the fixed amount of memory provided by one stack frame push.

这篇关于递归与For循环 - Factorial，Java的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！