代碼爲123456789提供java.lang.StackOverflowError，但不爲9999999999999999999

Question

因此，我正在做這個練習，找到只使用String類的下一個迴文。

我有點解決它，但有一個問題。

當我輸入像123456789這樣的字符串時，我得到一個java.lang.StackOverflowError。 雖然當我輸入像9999999999999999999這樣的較大字符串時，我不會收到錯誤。 我在這個網站做了一些研究，我認爲它與我使用的遞歸回文方法有關。

有沒有什麼辦法可以改進我的代碼，以便處理更大的數字？ 123456789爲什麼會給出錯誤而且9999999999999999999不是？後者更大。

import java.io.*; 

public class mainclass { 

public static void main(String[] args) throws IOException { 
    InputStreamReader isr = new InputStreamReader(System.in); 
    BufferedReader in = new BufferedReader(isr); 
    System.out.println(palindroom(in.readLine())); 
    } 

public static String increment(String str){ 
    String incre=""; 
    if(str.equals("9")){incre = "10";} 
    else{ 
     switch(str.charAt(str.length()-1)){ 
     case '0': incre = str.substring(0, str.length()-1)+"1";break; 
     case '1': incre = str.substring(0, str.length()-1)+"2";break; 
     case '2': incre = str.substring(0, str.length()-1)+"3";break; 
     case '3': incre = str.substring(0, str.length()-1)+"4";break; 
     case '4': incre = str.substring(0, str.length()-1)+"5";break; 
     case '5': incre = str.substring(0, str.length()-1)+"6";break; 
     case '6': incre = str.substring(0, str.length()-1)+"7";break; 
     case '7': incre = str.substring(0, str.length()-1)+"8";break; 
     case '8': incre = str.substring(0, str.length()-1)+"9";break; 
     case '9': incre = increment(str.substring(0, str.length()-1))+"0";break; 
     }; 
     } 
    return incre; 
    } 

public static String palindroom(String str){ 
    String palin=increment(str); 
    boolean isPalindroom=true; 
    for(int i=0;i<palin.length();i++){ 
     if(palin.charAt(i)==palin.charAt(palin.length()-i-1)){} 
     else{isPalindroom=false;} 
    } 
    if(isPalindroom){return palin;} 
    else{return palindroom(increment(str));} 
} 
} 

Answer 1

因爲你只遞歸如果輸入的值不是一個迴文，它會採取超過10,000遞歸遞增123456789爲迴文。

你的代碼有點奇怪，你需要一個字符串，你認爲它是一個數字，並使用字符串操作來增加它。如果Long不夠大，則轉換爲long（或BigInteger）會更簡單。

此外，您似乎增加了兩次，一次在palindroom方法的開始處，並且再次在else塊中增加。

UPDATE 從你的評論，我認爲你可能不清楚堆棧溢出錯誤是什麼。所以java調用堆棧是方法的堆棧（即LIFO）。在你的情況下，你的調用棧可能是main，palindroom，palindroom，palindroom，palindroom，palindroom等......請注意java只允許調用堆棧的最大大小，如果超過這個大小，你會得到一個堆棧溢出異常。 Java stack overflow error - how to increase the stack size in Eclipse?有一些關於默認值和配置的細節。

Answer 2

我知道你對如何與循環替換您的遞歸方法問題，我已經編碼這種彌補實踐經驗，這樣可以檢查出來：

public static void main(String[] args) throws IOException { 
    InputStreamReader isr = new InputStreamReader(System.in); 
    BufferedReader in = new BufferedReader(isr); 

    String numString = in.readLine(); 
    BigInteger num = new BigInteger(numString); 
    do { 
     num = num.add(new BigInteger("1")); 
    } while(pal(num)); 

    System.out.println(num); 
    } 

    public static boolean pal(BigInteger num){ 
    String isPal = num.toString(); 
    boolean isPalindroom=false; 

    for(int ii=0; ii<isPal.length(); ii++){ 
     if(isPal.charAt(ii) != isPal.charAt(isPal.length()-ii-1)) 
     isPalindroom = true; 
    } 

    return isPalindroom; 
    } 

Answer 3

只出現在最後一步遞歸一個函數 - 所謂的「尾遞歸」 - 通常是一個變相的循環;你只需用一組新的參數重複該函數的主體。一個好的優化器通常會將尾部遞歸重寫爲循環;顯然Java沒有在你的情況下。本實施例的一個簡單的迭代重寫的

實施例：

public static String palindroom(String str){ 
    while(true) 
    { 
    String palin=increment(str); 
    boolean isPalindroom=true; 
    for(int i=0;i<palin.length();i++){ 
     if(palin.charAt(i)==palin.charAt(palin.length()-i-1)){} 
     else{isPalindroom=false;} 
    } 
    if(isPalindroom){return palin;} 
    else{str=palin;} //increment str, and try again 
    } 
} 

這不會解決你的邏輯問題 - 參見其他響應 - 但它在單個堆棧幀中完全運行。