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)?

possible duplicate of [Is recursion ever faster than looping?](http://stackoverflow.com/questions/2651112/is-recursion-ever-faster-than-looping) — Kazekage Gaara, Jun 23 '12 at 17:45
@luketorjussen - because with the low numbers I deal with and due to the fact that I only call the method once or twice, I wouldn't notice the difference. What I'm talking about is if I use this method loads and loads of times, or about more complicated methods that can use both techniques. — Bluefire, Jun 23 '12 at 17:48
Why don't you try both and see which is quicker? Also you don't need to go far as checking if `num == 0`, if `num == 1` then you can return 1, why do an extra iteration/function call — luketorjussen, Jun 23 '12 at 17:48
@Bluefire, then why not try it with big numbers and call it lots of times? — luketorjussen, Jun 23 '12 at 17:49
The iterative version seems overly complex. It could be reduced to `int res = 1; for (int i = 2; i <= num; ++i) res *= i; return res;` — Niklas B., Jun 23 '12 at 17:51
The iterative will be faster than the recursive in Java - but that might not matter (recursive have method call overhead that might not be optimized away - and Java isn't Scheme yet as far as I know). For further excursions: http://chaosinmotion.com/blog/?p=622 — esej, Jun 23 '12 at 18:03

duffymo · Accepted Answer · 2012-06-23T18:10:08.290

15

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.

edited Jun 23 '12 at 18:10

answered Jun 23 '12 at 17:55

duffymo

305,152
44
369
561

I think it's better after the edit :) Retracting my earlier comment – Niklas B. Jun 23 '12 at 18:01

Ahmad · Answer 2 · 2012-06-24T03:41:37.247

3

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.

edited Jun 24 '12 at 03:41

answered Jun 23 '12 at 17:59

Ahmad

2,110
5
26
36

Creating and destroying stack frames does not have a high cost. Tail recursion such as this can be optimised away by the language processor. Recursion is often a more natural way to express a computation and the costs can be insignificant. – user207421 Jul 09 '16 at 11:35

score 1 · Answer 3 · answered Jul 09 '16 at 10:30

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

score 0 · Answer 4 · answered Jun 23 '12 at 17:59

0

There's no "this is better, that is worse" for this question. Because modern computers are so strong, in Java it tends to be a personal preference as to which you use. You are doing many more checks and computations in the iterative version, however you are piling more methods onto the stack in the recursive version. Pros and cons to each, so you have to take it case by case.

Personally, I stick with iterative algorithms to avoid the logic of recursion.

answered Jun 23 '12 at 17:59

Odiefrom

40
5

You are not doing more checks or computations in the iterative version. – Niklas B. Jun 23 '12 at 18:01
@NiklasB. If my count is right, he is doing a check for the starting `num == 0`, `i <= num`, `i++`, `result *= i` in the iterative version, while in the recursive he has `num == 0` and `num * factorial(num - 1)`, half as many. – Odiefrom Jun 23 '12 at 18:08
Oh, so you are talking about code complexity. In that case I agree. I though you were talking about runtime complexity (because after all, the same number of multiplications will be performed in both versions). – Niklas B. Jun 23 '12 at 18:10

Factorial method - recursive or iterative? (Java)

4 Answers4