线程"main"java.lang.StackOverflowError中的异常

Question

我有一段代码,我无法弄清楚它为什么在线程"main"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,我在线程"main"java.lang.StackOverflowError中得到了Exception.感谢你的帮助.:)

我差点忘了错误信息:

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.

请注意,根据维基百科上的Collat​​z猜想(大胆的矿井):

任何初始起始数小于1亿的最长进展是63,728,127,其中有949步.对于不到10亿的起始数字,它是670,617,279,有986步,而对于不到100亿的数字,它是9,780,657,630,有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