Recursive function to calculate combination and factorial

Question

I am using the following two functions to calculate factorials and combinations.

public static long Factorial(long n)
{
    if (n == 0)
        return 1;
    else
        return n * Factorial(n-1);

}

public static long combinations (long n, long k)
{       
    return Factorial(n)/(Factorial(k) * Factorial(n - k));      
}

I am testing it using:

long test = combinations((long)21, (long)13);

It seems to work for small numbers such as 5,2. But if I try 21,13, I get incorrect answers (negatives or 0).

Would anyone know what is happening here?

Your answer might be here: http://stackoverflow.com/questions/849813/large-numbers-in-java — Andrew Shepherd, Dec 12 '14 at 01:50
Not sure cause I don't feel like calculating it, but I'm pretty sure you're running into an overflow condition. Basically, long doesn't have enough capacity to hold the extremely large number that is 21 factorial and possibly 13 factorial. For large numbers like these, use BigInteger class. — Edward L., Dec 12 '14 at 01:51

score 1 · Accepted Answer · edited May 23 '17 at 11:50

1

The maximum value of long in java is 2^63.

That will safely take you up to the factorial of 20. However, factorial of 21 comes to around 2^65, so you are exceeding the maximum value that can be represented.

See this question for a discussion about what happens in java if you perform a multiplication that results in an overflow.

edited May 23 '17 at 11:50

Community

1
1

answered Dec 12 '14 at 01:53

Andrew Shepherd

44,254
30
139
205

nitishagar · Answer 2 · 2014-12-12T02:05:13.623

1

This is mainly because of overflow from long (64bit signed). You can look up BigDecimal or BigInteger for use in this case.

edited Dec 12 '14 at 02:05

answered Dec 12 '14 at 01:58

nitishagar

9,038
3
28
40

BigInteger would be more appropriate – etherous Dec 12 '14 at 02:00
You need division to happen. – nitishagar Dec 12 '14 at 02:01
1

I saw he was using using long division, so I figured that's what he wanted. You could use both as well: BigInteger for factorial, and BigDecimal for combinations. Extra credit for one that uses long, detects overflow, and upgrades when necessary – etherous Dec 12 '14 at 02:03

Seth S. · Answer 3 · 2014-12-12T02:41:46.157

As other users have said long can't hold Factorial(21). I rewrote your Factorial method using BigInteger and it seems to work, although you have to pass a BigInteger in as the parameter.

public static BigInteger Factorial(BigInteger n)
{

    if (n.equals(BigInteger.ZERO))
        return BigInteger.ONE;
    else
        return  n.multiply(Factorial(n.subtract(BigInteger.ONE)));
}

Then rewrite your combinations method using BigInteger:

public static BigInteger combinations (BigInteger n, BigInteger k)
{  
        return Factorial(n).divide(Factorial(k).multiply(Factorial(n.subtract(k))));

}

In the main method I called the combinations method like this

System.out.print(combinations(new BigInteger("21"), new BigInteger("13")));

Recursive function to calculate combination and factorial

3 Answers3