java程序中的StackOverFlowError

Question

我試圖解決一個問題，要求找到最小的主要回文，它在給定數字後出現，這意味着如果輸入是24，輸出將是101，因爲它是最小數字之後24既是素數也是迴文。

現在我的代碼完美適用於較小的值，但是當我插入類似於543212的輸入時，最後出現了第20行的StackOverFlowError，隨後是第24行的多個StackOverFlowErrors實例。下面是我的代碼：

package nisarg; 
import java.util.Scanner; 

public class Chef_prime_palindromes { 
    public static void main(String[] args) { 
     Scanner input = new Scanner(System.in); 
     long num = input.nextLong(); 
     isPalindrome(num + 1); 
    } 

    public static boolean isPrime(long num) { 
     long i; 
     for (i = 2; i < num; i++) { 
      if (num % i == 0) { 
       return false; 
      } 
     } 
     return true; 
    } 

    public static void isPalindrome(long num) { 
     String word = Long.toString(num); 
     int i; 
     for (i = 0; i < word.length()/2; i++) { 
      if (word.charAt(i) != word.charAt(word.length() - i - 1)) { 
       isPalindrome(num + 1); 
      } 
     } 
     if (i == word.length()/2) { 
      if (isPrime(num)) { 
       System.out.println(num); 
       System.exit(0); 
      } else { 
       isPalindrome(num + 1); 
      } 
     } 
    } 
} 

Answer 1

新String object在每次遞歸調用中創建和放置在堆棧（其中的方法創建的所有變量都保存，直到你離開這個方法的地方），這對於一個足夠深的遞歸使JVM達到分配結束堆棧空間。

我改變了String對象的局部性，把它放到一個單獨的方法中，從而減少了它的局部性並將其創建和銷燬（釋放棧空間）限制爲一次遞歸調用。

package com.company; 

import java.util.Scanner; 

public class Chef_prime_palindromes { 
    public static void main(String[] args) { 
     Scanner input = new Scanner(System.in); 
     long num = input.nextLong(); 
     isPalindrom(num + 1); 
    } 

    public static boolean isPrime(long num) { 
     long i; 
     for (i = 2; i < num; i++) { 
      if (num % i == 0) { 
       return false; 
      } 
     } 
     return true; 
    } 

    private static void isPalindrom(long num) { 
     for (; ;) { 
      if (isPalindrome(num)) { 
       if (isPrime(num)) { 
        System.out.println(num); 
        System.exit(0); 
       } else { 
        num++; 
       } 
      } else { 
       num++; 
      } 
     } 
    } 

    public static boolean isPalindrome(long num) { 
     String string = String.valueOf(num); 
     return string.equals(new StringBuilder(string).reverse().toString()); 
    } 
} 

Answer 2

你應該知道的第一件事是你的資源是有限的。即使你的實現是精確的，所有的遞歸調用都是正確的，你仍然可能會得到錯誤。該錯誤表明您的JVM堆棧空間不足。嘗試增加JVM堆棧的大小（有關詳細信息，請參閱here）。

另一個重要的事情是尋找素數和迴文數的分佈。您的代碼通過測試每個num+1對迴文屬性進行測試。這是不正確的。當數字爲素數時，您僅測試迴文。這將使計算更容易（並減少遞歸調用）。我相應地編輯了您的代碼，並在543212（1003001）後得到最接近的迴文編號。那就是：

public static void main(String[] args) { 

    Scanner input = new Scanner(System.in); 
    long num = input.nextLong(); 
    //isPalindrome(num+1); 
    nextPrimePalindrome(num+1); 
    } 

    public static void nextPrimePalindrome(long num) 
    { 
     boolean flag=true; 
     while(flag) 
     { 
      if(isPrime(num)) 
       if(isPalindrome(num)) 
       { 
        System.out.println(num); 
        flag=false; 
       } 
       num++;  
     } 
    } 

public static boolean isPrime(long num){ 
    long i; 
    for(i=2;i<num;i++){ 
     if(num%i == 0){ 
      return false; 
     } 
    } 
    return true; 
} 

public static boolean isPalindrome(long num) 
{ 
    String word=Long.toString(num); 
    for(int i=0;i<word.length()/2;i++) 
     if(word.charAt(i)!=word.charAt(word.length()-i-1)) 
      return false; 
    return true; 
} 
} 

Answer 3

全部顯示出來的解決方案使用遞歸和有問題，在某些時候，他們會達到其中StackOverflowException會發生點。 更好的解決方案也可以並行化，將其轉換爲循環。

這可能是這樣的：

package nisarg; 

import java.math.BigInteger; 
import java.util.Scanner; 
import java.util.concurrent.CopyOnWriteArrayList; 


public class Chef_prime_palindromes { 
    private static final CopyOnWriteArrayList<BigInteger> PRIMESCACHE 
     = new CopyOnWriteArrayList<>(); 


    public static void main(String[] args) { 
     try (Scanner input = new Scanner(System.in)) { 
      BigInteger num = new BigInteger(input.nextLine()); 

      initPrimes(num); 

      for (num = num.add(BigInteger.ONE); 
        !isPrimePalindrome(num); 
        num = num.add(BigInteger.ONE)); 

      System.out.println(num.toString()); 
      } 
    } 

    private static void initPrimes(BigInteger upTo) { 
     BigInteger i; 
     for (i = new BigInteger("2"); i.compareTo(upTo) <= 0 ; i = i.add(BigInteger.ONE)) { 
      isPrime(i); 
     } 
    } 


    public static boolean isPrimePalindrome(BigInteger num) { 
     return isPrime(num) && isPalindrome(num); 
    } 

    // could be optimized 
    public static boolean isPrime(BigInteger num) { 

     for (int idx = PRIMESCACHE.size() - 1; idx >= 0; --idx) { 
      if (num.mod(PRIMESCACHE.get(idx)).compareTo(BigInteger.ZERO) == 0) { 
       return false; 
      } 
     } 

     if (!PRIMESCACHE.contains(num)) { 
      PRIMESCACHE.add(num); 
     } 
     return true; 
    } 

    public static boolean isPalindrome(BigInteger num) { 
     String word = num.toString(); 
     int i; 
     for (i = 0; i < word.length()/2; i++) { 
      if (word.charAt(i) != word.charAt(word.length() - i - 1)) { 
       return false; 
      } 
     } 
     return true; 
    } 
}