Suche nach einem String Palindrom mit einer rekursiven Funktion

Bin ich zu schreiben versucht, eine rekursive Funktion, die ermittelt, ob ein string ein Palindrom ist. Hier ist was ich habe, so weit:

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

Aus irgendeinem Grund, wenn die rekursive Funktion geht tief genug und word.length() ist weniger als oder gleich 1 ist, ist Es nicht true zurückgibt. Ich kann nicht scheinen, um herauszufinden, warum. Ist es etwas zu tun, wie rekursive Funktionen arbeiten, oder wie ich bin Nachjustierung der Länge des Wortes in der Zeile, bevor ich kommentiert DEBUGGEN?

Ich bin nicht so talentiert in C++ wie ich es sein sollte, so bitte entschuldigen Sie mich, wenn meine Programmierung arm erscheint.

word.substr((0 + 1) Ist das nicht immer 1?

InformationsquelleAutor Blue | 2014-04-06

  1. 3

    Du zumindest fehlt eine return-Anweisung hier:

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

    Wenn die Länge nicht 1 Sie ruft rekursiv die palindrome Funktion, das ignorieren seiner Rückkehr Wert und dann wieder immer false. Mit meinem fix, Sie gibt das Ergebnis der Palindrom-Funktion aufgerufen, mit Wort, nach dem entfernen der ersten und letzten Buchstaben.

    InformationsquelleAutor hivert

  2. 1

    Den Antwort von hivert identifiziert Ihr problem, aber in Fall, dass Sie bei allen beteiligten mit der Leistung überlegen mit Iteratoren oder Indizes, anstatt viele string kopiert. Vielleicht etwas wie:

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

    Aber wenn Sie wollen, um zu überprüfen, die eine sehr lange Zeichenfolge, die Sie bekommen konnte, einen stack-überlauf. Wenn Sie Glück haben ist der compiler durchführen kann tail-call-Optimierung. Natürlich ist es in diesem Fall leicht zu entfernen, die Rekursion und eine Schleife verwenden, stattdessen:

    #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";
  }
    Erläutern Sie Ihre Antwort so, dass es einfach zu verstehen, für den zukünftigen Benutzer.
    Interessant, aber sehr teuer. Du bist wahrscheinlich besser dran Vorbeigehen ein paar von Indizes und der Rückkehr, wenn gleich-oder pass.
    Teuer ist untertrieben, dieser code kann eine übermäßige Anzahl von temporären strings. Es werfen auch ein std::out_of_range Ausnahme, wenn der zweite parameter ist ein leerer string. Endlich eine vernünftige Umsetzung würde zurück bool.

    InformationsquelleAutor Aman

Schreibe einen Kommentar