Trouver une Chaîne Palindrome avec une fonction récursive

Je suis en train d'écrire une fonction récursive qui permettra de déterminer si une chaîne est un palindrome. Voici ce que j'ai à ce jour:

int main()
{
    string word = "madam";

    if (palindrome(word) == true)
        cout << "word is a palindrome!" << endl;
    else
        cout << "word is not a palindrome..." << endl;

    return 0;
}

bool palindrome(string word)
{
    int length = word.length();

    string first = word.substr(0,1);
    string last = word.substr((length - 1), 1);

    if (first == last)
    {
        word = word.substr((0 + 1), (length - 2));
        cout << word << " " << word.length() << endl;  //DEBUGGING
        if (word.length() <= 1) return true;  //Problem line?
        palindrome(word);
    }
    else
        return false;
}

Pour une raison quelconque, quand la fonction récursive obtient assez profond, et word.longueur() est inférieur ou égal à 1, Il ne renvoie pas true. Je n'arrive pas à comprendre pourquoi. Est-il quelque chose à voir avec la façon récursive les fonctions de travail, ou comment je suis réajuster la longueur de mot dans la ligne avant j'ai commenté le DÉBOGAGE?

Je ne suis pas aussi douée en C++ que je devrais être, donc veuillez m'excuser si ma programmation semble pauvres.

  • word.substr((0 + 1) N'est pas toujours le 1?
InformationsquelleAutor Blue | 2014-04-06
  1. 3

    Vous êtes au moins manque une instruction de retour ici:

        if (word.length() <= 1) return true;  //Problem line?
    return palindrome(word);    //###### HERE !
}
else
    return false;

    Si la longueur n'est pas 1, vous êtes appelant récursivement la palindrome fonction, en ignorant sa valeur de retour, puis revenant toujours false. Avec mon fix, vous devrez renvoyer le résultat de l'palindrome fonction appelée avec word après la suppression de la première et de la dernière lettre.

    InformationsquelleAutor hivert
  2. 1

    La réponse par hivert identifié votre problème mais dans le cas où vous êtes à tous les intéressés à la performance envisager d'utiliser des itérateurs ou des indices plutôt que de faire de nombreux chaîne de copies. Peut-être quelque chose comme:

    #include <iostream>

template <typename T>
bool palindrome(T begin, T end){
  if (end - begin <= 1 )
    return true;

  --end;
  if (*begin != *end)
    return false;

  ++begin;
  return palindrome(begin, end);
}

int main() {
  std::string word(10000,'a');

  if (palindrome(word.cbegin(), word.cend()) == true)
    std::cout << "word is a palindrome" << std::endl;
  else
    std::cout << "word is not a palindrome" << std::endl;
}

    Mais si vous voulez vérifier si une chaîne très longue, vous pourriez obtenir un débordement de pile. Si vous êtes chanceux, le compilateur peut effectuer la queue d'appel d'optimisation. Bien sûr, dans ce cas il est facile de supprimer la récursivité et l'utilisation d'une boucle à la place:

    #include <iostream>

template <typename T>
bool palindrome(T begin, T end){
  while(end - begin > 1) {
    --end;  
   if (*begin != *end)
      return false;
    ++begin;
  }
  return true;
}

int main() {
  std::string word(1000000000,'a');

  if (palindrome(word.cbegin(), word.cend()) == true)
    std::cout << "word is a palindrome" << std::endl;
  else
    std::cout << "word is not a palindrome" << std::endl;
}
    InformationsquelleAutor Chris Drew
  3. -1
     string palindrome(string a, string b)
  {
    if (a.length() == 1 && a == b)
    return "true";
    else if (a.substr(0, 1) == b.substr(b.length() - 1, b.length() - 1)) return palindrome(a.substr(1), b.substr(0, b.length() - 1));
    else return "false";
  }
    • Expliquez votre réponse afin qu'elle soit facile à comprendre pour les futurs utilisateurs.
    • Intéressant, mais très cher. Vous êtes probablement mieux de passer une paire d'indices et de revenir quand égal ou passer.
    • Cher est un euphémisme, ce code permet de créer un nombre excessif de chaînes temporaires. Il permettra également de jeter un std::out_of_range exception si le deuxième paramètre est une chaîne vide. Enfin, une saine mise en œuvre serait de retour bool.
    InformationsquelleAutor Aman