Bluefire - 3 months ago 9x

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

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.

Source (Stackoverflow)

Comments