"Exception in thread "main" java.lang.StackOverflowError" 在主线程中出现异常：java.lang.StackOverflowError

Question

"Exception in thread "main" java.lang.StackOverflowError" 在主线程中出现异常：java.lang.StackOverflowError

7

我有一段代码，但无法确定为什么它会报错 Exception in thread "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，我会收到“Exception in thread "main" 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)

- Ray.R.Chua

我这里实际上没有看到递归？？你是在隐藏什么吗？你的 printSyra(i,1) 方法在哪里？ - Rohit Jain

@RohitJain的printSyra调用了printSyra。 - Pshemo

啊，抱歉.. 滚动条没有出现.. 需要刷新窗口.. :( - Rohit Jain

抱歉各位。我正在更新帖子以添加更多信息。感谢您的查看。我认为递归没问题？我仍然不确定为什么会出现错误。 - Ray.R.Chua

看起来是整数溢出的问题，根据算法的结果导致堆栈溢出。 - Mukul Goel

显示剩余5条评论

3个回答

1

一种解决方案是允许JVM使用java -Xss参数来为堆栈递归分配更多的空间。默认值少于1MB，如果我没记错的话，这可能会限制最多只能进行几百次递归。

更好的解决方案是在不使用递归的情况下重写练习：

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

- GeertPt

我的递归实现可以运行在 N = 104899295810901231 这个长度为2254的数上（http://www.ericr.nl/wondrous/delrecs.html）。虽然我同意递归可能会成为一个问题，但是在递归问题出现之前，中间数字可能已经超出了整数范围。 - nhahtdh

1

你的版本仍然无法计算小至113383的数字 - 但是不会抛出StackOverflowException，而是进入无限循环。此外，增加堆栈大小对于错误算法（错误的变量类型）也没有帮助。 - Tomasz Nurkiewicz

1

这是递归算法固有的问题。如果递归次数足够多，除非语言可以保证尾调用优化（Java和大多数类C语言不支持），否则你无法避免堆栈溢出。唯一真正解决它的方法是“展开”递归，通过迭代地重写算法或使用辅助函数来模拟递归调用的状态传递，而不实际嵌套调用。

- jonvuri

不确定为什么被踩了..我错过了什么吗？如果您踩了，请评论说明原因。 - jonvuri

递归在这里没问题。真正的问题是整数溢出。 - nhahtdh

1

嗯，你确定吗？java.lang.StackOverflowError文档：当应用程序递归太深时，会发生堆栈溢出，从而抛出此异常。 - jonvuri

我很确定，因为我知道 printSyra 中的 OP 在做什么。应该有足够的堆栈来支持几百个级别。 - nhahtdh

1

@Ray.R.Chua 最好的解决方案是不使用递归实现（这样可以避免 StackOverflow 错误）。另外，由于您无法知道在计算 3x+1 时会生成的最大数字，因此请避免使用整数并使用更大的数据类型，如 long 或者 BigInteger。 - Pshemo

显示剩余2条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tomasz Nurkiewicz · Accepted Answer

你的算法很好。然而，对于你的计算来说，int 太小了，它在这个输入上失败了：

printSyra(113383, 1);

在某个时候，整数溢出为负值，导致你的实现失控，无限递归。将 int num 更改为 long num，那么你可能会好一些——至少一段时间内是这样的。之后你会需要BigInteger。

请注意维基百科上Collatz conjecture（我加粗）所说的：

“任何小于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