[解決済み] スレッド "main "での例外 java.lang.StackOverflowError

質問

あるコードがあるのですが、なぜスレッド "main" java.lang.StackOverflowError で Exception が発生するのかが分かりませんでした。

これが質問です。

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)

解決方法は？

アルゴリズムは正常です。しかし int が小さすぎて、この入力では計算が失敗します。

printSyra(113383, 1);

ある時点で整数がオーバーフローして負の値になり、実装がおかしくなり、無限に再帰するようになります。変更 int num を long num で、しばらくは大丈夫でしょう。後で必要になるのは BigInteger .

なお、ウィキペディアによると コラッツ予想 (太字は私)。

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