Factorial method - recursive or iterative? (Java)

Question

I was making my way through project Euler, and I came across a combination problem. Combination logic means working out factorials. So, I decided to create a factorial method. And then I hit upon a problem - since I could quite easily use both iteration and recursion to do this, which one should I go for? I quickly wrote 2 methods - iterative:

public static long factorial(int num) {
        long result = 1;
        if(num == 0) {
            return 1;
        }
        else {
            for(int i = 2; i <= num; i++) {
                result *= i;
            }
            return result;
        }

and recursive:

public static long factorial(int num) {
        if(num == 0) {
            return 1;
        }
        else {
            return num * factorial(num - 1);
        }
    }

If I am (obviously) talking about speed and functionality here, which one should I use? And, in general, is one of the techniques generally better than the other (so if I come across this choice later, what should I go for)?

Answer 1

Both are hopelessly naive. No serious application of factorial would use either one. I think both are inefficient for large n, and neither int nor long will suffice when the argument is large.

A better way would be to use a good gamma function implementation and memoization.

Here's an implementation from Robert Sedgewick.

Large values will require logarithms.

Answer 2

Whenever you get an option to chose between recursion and iteration, always go for iteration because

1.Recursion involves creating and destroying stack frames, which has high costs.

2.Your stack can blow-up if you are using significantly large values.

So go for recursion only if you have some really tempting reasons.

Answer 3

I was actually analyzing this problem by time factor. I've done 2 simple implementations:

Iterative:

private static BigInteger bigIterativeFactorial(int x) {
    BigInteger result = BigInteger.ONE;
    for (int i = x; i > 0; i--)
        result = result.multiply(BigInteger.valueOf(i));
    return result;
}

And Recursive:

public static BigInteger bigRecursiveFactorial(int x) {
    if (x == 0)
        return BigInteger.ONE;
    else
        return bigRecursiveFactorial(x - 1).multiply(BigInteger.valueOf(x));
}

Tests both running on single thread. It turns out that Iterative is slightly faster only with small arguments. When I put n bigger than 100 recursive solution was faster. My conclussion? You never can say that iterative solution is faster than recursive on JVM. (Still talking only about time)

If You're intrested, whole way I get this conclussion is HERE

If You're intrested in deeper understanding difference between this 2 approaches, I found really nice description on knowledge-cess.com