Factorial for big number in java

Question

I've been working around with this recursive function but couldn't find myself which led me to overflow error and it keeps coming around. I've already tried casting to BigInteger also but nothing special is coming. I don't see any warning or syntax error in my Eclipse IDE. I had to submit an efficient algorithm for big numbers. thanks in advance. :-)

public static BigInteger factorial(int n)
{
    return n > 2 ? new BigInteger(n+"").multiply(factorial(n-1)) : new BigInteger(n+"");
}

@SarthakSrivastava yes, it seems so. the only one limitation to me was that i can't modify the recursive signature, in this case `int n`. — SoulOfSun, Nov 30 '16 at 05:02
Well A StackOverflowError means that you have too many function calls to fit their data on the stack. Usually it's an indication that you have infinite recursions — Sarthak Srivastava, Nov 30 '16 at 05:10
@SarthakSrivastava, `return n > 2 ? new BigInteger(n+"").multiply(factorial(--n)) : new BigInteger(n+"");` i just modified like that and it's still going way of `StackOverFlowError`. — SoulOfSun, Nov 30 '16 at 05:13
Resolving Stackoverflow error https://examples.javacodegeeks.com/java-basics/exceptions/java-lang-stackoverflowerror-how-to-solve-stackoverflowerror/ — Sarthak Srivastava, Nov 30 '16 at 05:17
Your code looks fine. What is the original `n` when you get an overflow error? — ajb, Nov 30 '16 at 05:19
I tried it... your code works fine when `n`=1000 but not when `n`=10000. That's an indication that there's just a limit to how much recursion Java can handle. If I use a loop instead of recursion, it works with `n`=10000, but it started taking too long with `n`=100000 and I killed it. — ajb, Nov 30 '16 at 05:24
This is why **dynamic programming** was introduced in the first place. Make use of dynamic programming principles. That will solve your problem. — Shyam Baitmangalkar, Nov 30 '16 at 06:26
@ShyamBaitmangalkar You'll have to explain that--I don't see how this is a good use case for dynamic programming. — ajb, Nov 30 '16 at 06:43
@ajb, While computing factorial using `recursive` algos, we tend to perform repeated calculations of sub-problems which consumes more time. So by using DP techniques like `memoization` along with recursion, we can reduce the no. of recursions. Create a memo `int[] memo`. Perform recursion only if `memo[n] == 0`, store that result in memo `memo[n] = result`. This is like performing a **careful brute force** — Shyam Baitmangalkar, Nov 30 '16 at 07:06
@ShyamBaitmangalkar (1) Where is the repeated calculation here? (2) If the problem is that too much memory is being used, how is memoization going to help? (3) Why does this have to be a recursive algorithm in the first place? You don't need recursion at all. Making this a loop automatically eliminates any stack overflows. Memoization/dynamic programming is useful for some recursive problems, but it's not appropriate for every problem (especially those that don't need recursion in the first place). — ajb, Nov 30 '16 at 07:11
@ajb, you are absolutely correct. The usage of `memoization` only arises when we tend to write a recursive algorithm. But like you mentioned, making this a loop will automatically eliminate the need for it. — Shyam Baitmangalkar, Nov 30 '16 at 07:24

Chai T. Rex · Accepted Answer · 2016-11-30T06:03:49.993

The problem

You're getting the error because the computer has to remember every method call you make (and other information) until that method call is finished, and there's only so much space on the "stack" set aside to remember all that.

You recurse so many times that you overflow the stack space set up to remember method calls that are in progress. That's called a stack overflow.

A possible solution

A reasonably-efficient algorithm is to use a simple loop. This has the side benefit of not causing stack overflows, since you don't create more method calls over and over again, you just do stuff inside the first method call.

You should also use BigInteger.valueOf(n) instead of new BigInteger(n+""):

public static BigInteger factorial(int n) {
    BigInteger result = BigInteger.ONE;
    for (; n > 1; n--) {
        result = result.multiply(BigInteger.valueOf(n));
    }
    return result;
}

This takes my computer about 6 seconds to compute 100,000!

Factorial for big number in java

1 Answers1

The problem

A possible solution

More efficient solutions