异常线程“main” java.lang.StackOverflowError的(Exception

我有一段代码，我无法弄清楚，为什么它给我在线程异常“主要” java.lang.StackOverflowError的。

这是一个问题：

Given a positive integer n, prints out the sum of the lengths of the Syracuse 
sequence starting in the range of 1 to n inclusive. So, for example, the call:
lengths(3)
will return the the combined length of the sequences:
1
2 1
3 10 5 16 8 4 2 1 
which is the value: 11. lengths must throw an IllegalArgumentException if 
its input value is less than one.

我的代码：

import java.util.HashMap;

public class Test {

HashMap<Integer,Integer> syraSumHashTable = new HashMap<Integer,Integer>();

public Test(){

}

public int lengths(int n)throws IllegalArgumentException{

    int sum =0;

    if(n < 1){
        throw new IllegalArgumentException("Error!! Invalid Input!");
    }   

    else{


        for(int i =1; i<=n;i++){

            if(syraSumHashTable.get(i)==null)
            {
                syraSumHashTable.put(i, printSyra(i,1));
                sum += (Integer)syraSumHashTable.get(i);

            }

            else{

                sum += (Integer)syraSumHashTable.get(i);
            }



        }

        return sum;

    }



}

private int printSyra(int num, int count){

    int n = num;

    if(n == 1){

        return count;
    }

    else{   
            if(n%2==0){

                return printSyra(n/2, ++count);
            }

            else{

                return printSyra((n*3)+1, ++count) ;

            }

    }


}
}

驱动程序的代码：

public static void main(String[] args) {
    // TODO Auto-generated method stub
    Test s1 = new Test();
    System.out.println(s1.lengths(90090249));
    //System.out.println(s1.lengths(5));
}

。我知道问题出在递归。 5.但是，当数量巨大，如90090249，我在线程异常“主要” java.lang.StackOverflowError的：如果输入的是一个很小的值，例如，不会发生错误。感谢你的帮助。 :)

我差点忘了错误信息：

Exception in thread "main" java.lang.StackOverflowError
at Test.printSyra(Test.java:60)
at Test.printSyra(Test.java:65)
at Test.printSyra(Test.java:60)
at Test.printSyra(Test.java:65)
at Test.printSyra(Test.java:60)
at Test.printSyra(Test.java:60)
at Test.printSyra(Test.java:60)
at Test.printSyra(Test.java:60)

Answer 1:

你的算法是罚款。然而int是你计算过小，它没有这个输入：

printSyra(113383, 1);

在一些点整数溢出到负值，您的实现都疯了，递归无限。更改int num到long num ，你会没事的-有一段时间了。后来你需要BigInteger 。

需要注意的是，根据维基百科上的考拉兹猜想（粗体矿）：

对于任何初始起动数小于100亿最长进展是63728127，其具有949层的步骤 。为了启动数字小于1十亿它是670617279，第986个步骤，和用于数字小于10十亿它是9780657630，具有1132层的步骤 。

总步数相当于最大嵌套级别（堆栈深度），你可以期望。所以，即使是比较大的数字StackOverflowError不应该发生的。看一看使用该实现BigInteger ：

private static int printSyra(BigInteger num, int count) {
    if (num.equals(BigInteger.ONE)) {
        return count;
    }
    if (num.mod(BigInteger.valueOf(2)).equals(BigInteger.ZERO)) {
        return printSyra(num.divide(BigInteger.valueOf(2)), count + 1);
    } else {
        return printSyra(num.multiply(BigInteger.valueOf(3)).add(BigInteger.ONE), count + 1);
    }
}

它的工作原理即使是非常大的值：

printSyra(new BigInteger("9780657630"), 0)  //1132
printSyra(new BigInteger("104899295810901231"), 0)  //2254

Answer 2:

这是递归算法的固有问题。让递归足够大的数量，你真的不能避免堆栈溢出，除非该语言可以保证尾调用优化（Java和大多数类似C语言没有）。要真正解决这个问题的唯一办法就是“展开”递归，重写算法迭代或一个辅助函数来模拟递归调用的状态，通过没有实际嵌套调用。

Answer 3:

一种解决方案是允许JVM采取更多的空间用于堆递归，使用java -Xss参数。它的默认值是小于一兆字节，IIRC，这可能会限制到几百递归最大。

更好的解决方案是重写锻炼无递归：

private int printSyra(int num){
    int count = 1;    
    int n = num;    
    while(n != 1){

            if(n%2==0){    
                n = n/2;
                ++count;
            }    
            else{    
                n=(n*3)+1;
                ++count;    
            }    
    }
    return count;
}

文章来源: Exception in thread “main” java.lang.StackOverflowError