Le code donne java.lang.StackOverflowError pour 123456789 mais pas pour 99999999999999999999
Je fais donc cet exercice pour trouver le prochain palindrome avec seulement l'utilisation de la classe String.
Je l'ai un peu résolu, mais j'avais une question sur quelque chose.
Lorsque j'entre une chaîne comme 123456789, j'obtiens un java.lang.StackOverflowError. Alors que lorsque j'entre une chaîne plus grande comme 99999999999999999999, je n'obtiendrai pas l'erreur. J'ai fait quelques recherches sur ce site et je pense que cela a quelque chose à voir avec la méthode palindrome récursive que j'utilise.
Y a-t-il un moyen que je pourrais améliorer mon code pour qu'il gère de plus grands nombres? Et pourquoi 123456789 donnerait-il une erreur et 99999999999999999999? Ce dernier est plus grand.
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));}
}
}
3 answers
Parce que vous ne récursez que si la valeur entrée n'est pas un palindrome, et il faudrait plus de 10 000 récursions pour incrémenter 123456789 dans un palindrome.
Votre code est un peu bizarre, vous prenez une chaîne, que vous supposez être un nombre, et l'incrémentez en utilisant la manipulation de chaîne. La conversion en long (ou BigInteger si Long n'est pas assez grand) serait BEAUCOUP plus simple.
De plus, vous semblez incrémenter deux fois, une fois au début de la méthode palindroom, et à nouveau dans le else bloc.
MISE À JOUR D'après votre commentaire, je suppose que vous n'êtes peut-être pas clair sur ce qu'est une erreur de débordement de pile. La pile d'appels java est donc la pile (c'est-à-dire LIFO) des méthodes. Dans votre cas, votre pile d'appel serait principaux, palindroom, palindroom, palindroom, palindroom, palindroom, etc... Veuillez noter que java n'autorise qu'une taille maximale pour la pile d'appels, si cette taille est dépassée, vous obtenez une exception de débordement de pile. Java erreur de dépassement de pile - comment augmenter la taille de la pile dans Eclipse? a quelques détails sur les valeurs par défaut et la configuration de cela.
Je sais que vous aviez des questions sur la façon de remplacer votre méthode récursive par une boucle et j'avais codé cela pour la pratique afin que vous puissiez le vérifier:
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;
}
Une récursion qui ne se produit que comme la dernière étape d'une fonction-une soi-disant "récursion de queue" - est généralement une boucle déguisée; vous ne faites que répéter le corps de la fonction avec un nouvel ensemble de paramètres. Un bon optimiseur réécrira souvent les récursions de queue en boucles; apparemment, Java ne l'a pas fait dans votre cas.
Exemple de réécriture itérative triviale de cet exemple:
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
}
}
Cela ne résoudra pas vos problèmes logiques see voir d'autres réponses but mais il s'exécute entièrement dans un seul frame de pile.