StackOverflowError with BigInteger for calculating C(n,r)

Question

I implemented the recursive algorithm to calculate N choose r. C(n,r) = C(n-1,r-1) + C(n-1,r). I wanted to calculate C(100000, 50000), which is throwing stackoverflow. Appreciate any help.

Error:

java Solution 1 1 10000 5000 Exception in thread "main" java.lang.StackOverflowError at java.lang.System.arraycopy(Native Method) at java.util.Arrays.copyOfRange(Arrays.java:3210) at java.lang.String.(String.java:215) at java.lang.StringBuilder.toString(StringBuilder.java:430) at Solution.findNcr(Solution.java:31) at Solution.findNcr(Solution.java:35)

Code:

private static HashMap<String,BigInteger> hm =
    new HashMap<String,BigInteger>(10000000,0.9f); 
private static BigInteger findNcr(int n, int r) {
    BigInteger topLVal = BigInteger.valueOf(0);
    BigInteger topRVal = BigInteger.valueOf(0);
    int parentN = 0, parentR = 0;

    if( r >= n-r)  //ncr = nc(n-r)
       r = n-r;

    if (r == 0 || r == n)
        return BigInteger.valueOf(1L);
    else if (r == 1 || r == n-1)
        return BigInteger.valueOf(n);
    else if (hm.containsKey(""+n+""+r)) { //line 31
        return hm.get(""+n+""+r);
    } else{
        parentN = n-1; parentR = r-1;
        topLVal = findNcr(parentN, parentR);
        topRVal = findNcr(parentN, r);
        hm.put(""+parentN+""+parentR,topLVal);
        hm.put(""+parentN+""+r, topRVal);
        return topLVal.add(topRVal);      //line 35
    }
}

Answer 1

Well what you did is what you got. Every recursive call you make saves the caller state on the stack and since you are calculating C(100000, 50000) which will make multi million recursive calls will end up with all stack space getting exhausted. You may want to look into a better algorithm like i mentioned here Write a faster combinatorics algorithm

Answer 2

You could try increasing your stack size.

Use -Xss to your JVM.

I guess 1 GB should do the trick for you. You can calculate it to get more accurate value.