В чем причина исключения в стеке потока? - PullRequest
Новая
       0

В чем причина исключения в стеке потока?

2 голосов
/ 05 февраля 2012 
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;
    }
}

Исключение в потоке "main" java.lang.StackOverflowError at java.util.HashMap.get (Неизвестный источник)

Привет, Почему я получаю исключение stackoverflow для этой программы?

я знаю, что stackoverflow обычно означает, что у вас есть бесконечный цикл, но это прекрасно работает, когда я использую 10000 или другие меньшие числа, что становится внезапно бесконечным с большими числами?

Ответы [ 5 ]

5 голосов
/ 05 февраля 2012

A StackOverflowError происходит при переполнении стека вызовов.Это происходит, когда у вас слишком много вложенных вызовов (потому что каждый вызов требует места в стеке, и он имеет конечный размер).Полагаю, в вашем случае 20000 - это слишком много.

Размер стека JVM можно изменить с помощью флага -Xss.Но я бы посоветовал вам найти другой способ вычисления факториала.

2 голосов
/ 05 февраля 2012

При каждом вызове рекурсивной функции создается новый указатель в стеке, поэтому при большом количестве вызовов рекурсивной функции вы можете получить исключение StackOverflow ...

Совет : замените рекурсивную функцию на цикл для разрешения.

1 голос
/ 05 февраля 2012

Причина в том, что ваша факторная функция является рекурсивной, а это НЕ хвостовая рекурсия .

Это означает, что каждый раз, когда вы вызываете функцию "factorial", этот вызов помещается в стек.

Я понятия не имею, может ли компилятор Java вообще генерировать вызовы хвостовой рекурсии, но если это возможно, вы можете просто реорганизовать свою функцию в способ хвостового вызова. В противном случае просто избегайте рекурсии (хорошая практика в императивных языках в любом случае).

0 голосов
/ 18 марта 2014

Вы можете изменить размер среды исполнения стека Java по умолчанию с помощью -Xss switch 

eg: java -Xss2048k YourClass
0 голосов
/ 05 февраля 2012

Нерекурсивные версии (не столько, сколько скомпилированные - это переполнение стека).Будут более ясные способы написать это. 

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;
           }
        }
    }
}
...