what's the reason for stackoverflow exception in this?

Question

import java.math.BigInteger;
import java.util.HashMap;

/**
 *
 * @author cypronmaya
 */
public class test {
    static HashMap<Integer, BigInteger> cache = new HashMap<Integer, BigInteger>();
    public static void main(String[] args) {
     System.out.println(factorial(20000));
  }

    public static BigInteger factorial(int n) {
        BigInteger ret;
        if (n == 0) {
            return BigInteger.ONE;
        }
        if (null != (ret = cache.get(n))) {
            return ret;
        }
        ret = BigInteger.valueOf(n).multiply(factorial(n - 1));
        cache.put(n, ret);
        return ret;
    }
}

Exception in thread "main" java.lang.StackOverflowError at java.util.HashMap.get(Unknown Source)

Hi, Why am i getting stackoverflow exception to this program?

i know that stackoverflow usually means you have an infinite loop, but this works fine when i'm using 10000 or some other numbers lesser, wht becomes suddenly infinite with big numbers?

You could calculate `factorial(10000)` then `factorial(20000)`. ;) (This code is thread-hostile, btw. And goes a bit odd for negative `n`.) — Tom Hawtin - tackline, Feb 05 '12 at 12:36

score 5 · Accepted Answer · edited May 23 '17 at 12:34

5

A StackOverflowError occurs when the call stack overflows. This happens when you have too many nested calls (because each call requires space to be reserved on the stack, and it's a finite size). I guess in your case, 20000 is too many.

You can modify the stack size of the JVM with the -Xss flag. But I'd suggest that you find a different way to compute a factorial.

edited May 23 '17 at 12:34

Community

1
1

answered Feb 05 '12 at 12:02

Oliver Charlesworth

267,707
33
569
680

Agree with this. Modifying the stack size is something you can do but not for this type of problems. @cypronmaya you should look for another way to program factorial. – Jose Garrido Feb 05 '12 at 12:29
i thought that using cache would speed things up for further calls of factorial – cypronmaya Feb 05 '12 at 12:48
@oli charlesworth can u suggest a factorial program which would compute higher numbers and also has cache (for making things faster for further factorial calls) – cypronmaya Feb 05 '12 at 12:51
1

@cypronmaya: The cache has nothing to do with stack overflows. An iterative algorithm would be equally nice on the instruction cache. – Oliver Charlesworth Feb 05 '12 at 13:03
@OliCharlesworth any suggestion how to write a non-recursive,memoized kinda factorial algorithm? – cypronmaya Feb 05 '12 at 14:24
@cypronmaya: `y = 1; for (i = 2; i <= n; i++) { y *= i; }`. – Oliver Charlesworth Feb 05 '12 at 14:27
@OliCharlesworth MEMOIZED kinda? if possible – cypronmaya Feb 05 '12 at 14:33
1

@cypronmaya: It is possible, and it involves maintaining a list of previously-computed results. I'm not going to just give you the code though. – Oliver Charlesworth Feb 05 '12 at 14:57

score 2 · Answer 2 · answered Feb 05 '12 at 12:02

2

The recursive function each time that is called create a new pointer in the stack, so with an high number of calls of a recursive function you can get a StackOverflow Exception ...

Tip : replace the recursive function with a loop to resolve.

answered Feb 05 '12 at 12:02

aleroot

71,077
30
176
213

score 1 · Answer 3 · edited May 23 '17 at 11:47

1

The reason is that your factorial function is recursive and this is NOT tail recursion.

It means that every time you call the "factorial" function this call is put to the stack.

I have no idea if Java compiler can generate tail recursion calls at all, but if it can, you can simply refactor your function to a tail-call way. Otherwise just avoid recursion (a good practice in imperative languages anyway).

edited May 23 '17 at 11:47

Community

1
1

answered Feb 05 '12 at 12:08

Alexey Raga

7,457
1
31
40

2

The Java compiler or JVM (JIT compiler) do not (yet) optimize tail calls. Maybe in a future version. – Jesper Feb 05 '12 at 12:44

score 0 · Answer 4 · edited Mar 18 '14 at 02:18

0

You can resize the Java default stack size runtime with the -Xss switch

eg: java -Xss2048k YourClass

edited Mar 18 '14 at 02:18

Rico

58,485
12
111
141

answered Mar 18 '14 at 01:54

Kampau Ocu

1,131
1
7
4

score 0 · Answer 5 · answered Feb 05 '12 at 14:10

Non-recursive versions (not so much as compiled - this is Stack Overflow). There will be clearer ways to write this.

public class Test {
    private static final Object lock = new Object();
    private static final List<BigInteger> cache = new ArrayList<>(
        Arrays.asList(BigInteger.ONE)
    );
    public static void main(String[] args) {
        System.out.println(factorial(20000));
    }

    public static BigInteger factorial(int n) {
        if (n < 0) {
            throw new IllegalArgumentException();
        }
        synchronized (lock) {
           int r = cache.size();
           if (n < r) {
               return cache.get(n);
           }
           BigInteger current = cache.get(r-1);
           for (;;) {
               current = BigInteger.valueOf(r).multiply(current);
               cache.add(current);
               if (n == r) {
                   return current;
               }
               ++r;
           }
        }
    }
}

what's the reason for stackoverflow exception in this?

5 Answers5