How to correct my java recursive method so that I can use it to compute big value number?

Question

It started from I want to compute 1+2+3+...+n, and

It is easy for me to figure out an recursive method to deal with repeat-plus-operation, and the code as follow:

public long toAccumulate(long num)
{
    return num == 1 ? 1 : num + toAccumulate(num-1);
}

This method works just fine when use in a range of small number like 1 to 100, however, it fails to work when the parameter up to a big number like 1000000.

I wonder why?

And one leads to another, I write a repeat-times-operation method as follow:

public long toTimes(long num)
{
    return num == 1 ? 1 : num * toTimes(num-1);
}

And here comes some interesting result. If I pass 100 as parameter, I will get 0. So I decrease my parameter's value, and I finally got some number when the parameter passing 60, but the result was a very weird negative number -8718968878589280256.

This got me thinking, but it didn't too much time for me to rethink something I have learnt from C, which is long long big data value type. And I assumed that negative number showed off is because the result data too big to fit in the current data type. What amazed me was I realize that there's a BigInteger class in Java, and I remembered this class can operate the big value data, so I changed the first code as follow:

public BigInteger toAccumulate(BigInteger num)
{
    return num.equals(1) ? BigInteger.valueOf(1) : (num.add(toAccumulate(num.subtract(BigInteger.valueOf(1)))));
}

But it still didn't work... and this is driving me crazy...

A question I found in the stack overflow which similar to mine According to the people who answered the question, I guess it may be the same reason that cause the bug in my code.

But since the BigInteger class didn't work, I think this must be the solution to this kind of accumulation problem.

What will you people do when you need to accumulate some number and prevent it go out of the maximum of data type? But is this really the data type problem?

Factorial problem? `BigInteger` should be the right choice already — Ian, Apr 21 '16 at 01:54
"I tried...but it still comes Stack Overflow" Just how *BIG* your number is...? — Ian, Apr 21 '16 at 02:03
You cannot use recursion for what you are trying to accomplish. You will keep getting a java.lang.StackOverflowError. You need an iterative approach. — Michael Markidis, Apr 21 '16 at 02:04
The `StackOverflowError` exception is not caused by your `BigInteger`, it's caused by **stack frame**. Every time you called a method, JVM will allocate a stack frame to store your local variables, return address... etc, just familiar to C. So if you have a huge chain of the recursive call, JVM needs to maintain numerous stack frames, and when it run out of memory, it causes `StackOverflowError`. Your code has some logical errors which is pointed out by Louis Wasserman's answer, but even if you correct that, you still get `StackOverflowError` when you call it with a very big number. — Nier, Apr 21 '16 at 02:35

score 1 · Answer 1 · answered Apr 21 '16 at 01:59

1

return num.equals(1) 
    ? BigInteger.valueOf(1) 
    : (num.add(toAccumulate(num.subtract(BigInteger.valueOf(1)))));

should probably be

return num.equals(BigInteger.valueOf(1)) 
    ? BigInteger.valueOf(1) 
    : (num.add(toAccumulate(num.subtract(BigInteger.valueOf(1)))));

...though frankly I'd write it as a method accepting an int and returning a BigInteger.

answered Apr 21 '16 at 01:59

Louis Wasserman

191,574
25
345
413

Thanks for your correction, and honestly, I don't think this correction is where my problem's point is, which means to accumulate number but fail in the stack things. – Benjamin Apr 22 '16 at 01:30
A `StackOverflowError` is _inevitable_ when you call a recursive method with O(input) recursions, and input gets very large. – Louis Wasserman Apr 22 '16 at 02:24

Michael Markidis · Accepted Answer · 2016-04-22T18:25:48.560

0

What if you try this:

public static BigInteger toAccumulate (BigInteger num)
{       
    if (num.equals(BigInteger.valueOf(1)))
    {
        return BigInteger.valueOf(1) ;
    }
    else
    {
        // 1+2+...+(n-1)+n = (n)(n+1)/2
        BigInteger addOne = num.add(BigInteger.valueOf(1));
        return num.multiply(addOne).divide(BigInteger.valueOf(2));
    }
}

Here's how you can do the 1*2*3*....*(n-1)*n

public static BigInteger toTimes (BigInteger num)
{
    // Should check for negative input here

    BigInteger product = num;

    // while num is greater than 1
    while (num.compareTo(BigInteger.valueOf(1)) == 1)
    {
        BigInteger minusOne = num.subtract(BigInteger.valueOf(1));
        product = product.multiply(minusOne);

        num = minusOne; // num--;
    }
    return product;
}

Note: This is essentially the Factorial Function

edited Apr 22 '16 at 18:25

answered Apr 21 '16 at 02:14

Michael Markidis

4,163
1
14
21

This is great! And this solution makes me rethink the way I figure how to deal with a problem. Thank you:) But how to deal the `1*2*3*4*...*n`? What else can we use to deal with it beside the recursive solution? – Benjamin Apr 22 '16 at 00:50
I'm glad my answer was helpful. See the edits to my answer on how to deal with the multiplication.Also, using recursion as you did in your original answers in not necessarily a bad thing. They are actually elegant and useful in illustrating how to use recursion to solve such problems. However, sometimes you may need to switch from recursion to an iterative approach for the sake of memory - as was the case for your purposes. – Michael Markidis Apr 22 '16 at 18:36

How to correct my java recursive method so that I can use it to compute big value number?

2 Answers2