Recursion vs For loops - Factorials, Java

Which of these two methods of getting a factorial (loop vs recurs开发者_开发技巧ive) 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.

---

With 21 calls, your long will overrun, which is very early to measure a difference, which could get relevant.

You might need BigInteger to measure a significant difference, when measuring factorial (10*1000*1000) or something that large. If you don't have high numbers to calculate, but calculate low factorials often, a hashmap with precalculated values will be faster than recursion and looping.

---

The only problem with recursion is that every time that the function is called it's address is put on the top of the stack, concatenating a lot of call can cause a stack overflow exception if the number of recursion calls is high .