How can i avoid the java.lang.StackOverflowError:null?

Question

我正在努力自学 Java 通常我有足够的资源和像这样的好网站，但现在我只想知道我哪里错了。

所以问题被表述为：

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even) n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

我一直收到这些 java.lang.WhosebugError，有人可以帮助我吗？我的代码：

import java.util.HashMap;

public class Euler
{
    HashMap<Integer,Integer> check;
    int result;

    public Euler()
    {
        check = new HashMap<Integer,Integer>();     
    }

    public int search(int number)
    {

        int startingNumber = number;

        while (check.get(number)==null && number!=1){

            if (number%2==0){
                number = number / 2;
                result = search(number);
                result++;               
            }

            else {
                number = (3*number)+1;
                result = search(number);
                result++;
            }
        }

        if (check.get(startingNumber)!=null){
            result=result+check.get(number);
            check.put(startingNumber,result);

        }
        else{
            check.put(startingNumber,result);
        }

        return result;
    }

    public int test()
    {
        int temp = 0;
        int highest=0;
        int get = 0;
        for (int i=1000001;i>1;i--){
            result = 0;
            temp = search(i);
            if(temp>highest){
                highest=temp;
                get = i;
            }
            System.out.println(i);
        }

        return get;
    }


}

编辑：

public class Euler
{
   public Euler()
    {
    }

    public int quickSearch(int numb)
    {
        int steps = 0;
        while (numb != 1) {
            if (numb % 2 == 0) {
                numb /= 2;
            }
            else {
                numb = 3 * numb + 1;
            }
            steps++;
        }
        return steps;
    }


    public int test()
    {
        int temp = 0;
        int highest=0;
        int get = 0;
        for (int i=1;i<1000001;i=i+2){

            temp = quickSearch(i);
            if(temp>highest){
                highest=temp;
                get = i;
            }
            System.out.println(i);

        }

        return get;
    }
}

编辑2：所以在 EDIT 版本代码中，我从机器上冻结了，但是当我将 int 改为 long 时，它工作得很好，虽然我知道用一些 Map 来存储值，你可以更快地找到它。谢谢大家！！

Answer 1

问题出在这里：

public int search(int number)
{

    int startingNumber = number;

    while (check.get(number)==null && number!=1){

        if (number%2==0){
            number = number / 2;
            result = search(number);
            result++;               
        }

        else {
            number = (3*number)+1;
            result = search(number);
            result++;
        }
    }

    if (check.get(startingNumber)!=null){
        result=result+check.get(number);
        check.put(startingNumber,result);

    }
    else{
        check.put(startingNumber,result);
    }

    return result;
}

您递归调用 search(int) 并导致堆叠。

Answer 2

问题是你的递归调用太多了。对此的最佳解决方案是使代码迭代。只需修改您的 while 循环以首先检查是否已经找到该数字，如果是 return 您到达该数字所花费的步骤总和以及从该数字到 1。否则只需更新下一步的数字，运行再次通过循环。同时，您只需要跟踪获得已知数字所花费的步骤。

就我个人而言，我会完全删除 HashMap，只使用一个简单的 while 循环：

int steps = 0;
while (number != 1) {
    if (number % 2 == 0) number /= 2;
    else number = 3 * number + 1
    steps++;
}

编辑：如果你想添加一个 HashMap 来存储找到的值，你可以这样做（我假设你之前定义了一个名为 foundNumbers 的 HashMap<Long, Integer>）：

public int search(long number) {

    int steps = 0;
    long initialNumber = number;
    while (number != 1) {
        if (number % 2 == 0) number /= 2;
        else number = 3 * number + 1
        steps++;

        if (foundNumbers.containsKey(number)) {
            steps += foundNumbers.get(number)
            foundNumbers.put(initialNumber, steps);
            return steps;
        }
    }

    foundNumbers.put(initialNumber, steps);
    return steps;

}

Answer 3

虽然递归代码在很多情况下很简单紧凑，但也有堆栈溢出的可能，尤其是在递归链长度未知的情况下。

您的案例很简单，可以通过迭代轻松解决。所以，尝试使用迭代模型而不是递归模型。

How can i avoid the java.lang.StackOverflowError:null?

How can i avoid the java.lang.StackOverflowError:null?

java

collatz