Как я могу избежать 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.StackOverflowError, кто-то может мне помочь, пожалуйста. Мой код:

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


} 

EDIT:

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

EDIT2: Так в коде EDIT версии, я получил замораживание от машины, но когда я изменил Int долго, она работала отлично, хотя я понимаю, что с некоторой Картой для хранения значений вы можете найти ее быстрее. Спасибо вам всем !!

Answer 1

Проблема в том, что у вас слишком много рекурсивных вызовов. Лучшим решением для этого было бы сделать итеративный код. Просто переработайте свой цикл while, чтобы сначала проверить, был ли номер уже найден, если да, верните сумму шагов, которые потребовались вам, чтобы добраться до этого номера, и потребуется от этого номера до 1. В противном случае просто обновите номер для следующего шага, повторите цикл. Между тем, вам просто нужно следить за шагами, которые потребовались вам, чтобы добраться до известного номера.

Лично я хотел бы удалить HashMap вообще и просто иметь простой while цикл:

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

Edit: Если вы хотите добавить HashMap сохранить найденные значения, вы могли бы сделать это, как это (I предположим, вы определили HashMap<Long, Integer> назвали foundNumbers ранее):

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 2

Проблема здесь:

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

Вы называете поиск (интермедиат) рекурсивно и его причиной укладки.

Answer 3

Хотя рекурсия код легко и компактно во многих случаях, но есть ПОСС вероятность переполнения стека, особенно если длина цепи рекурсии неизвестна.

Ваш случай прост и может быть легко разрешен путем итерации. Итак, попробуйте использовать итеративную модель вместо рекурсивной модели.