尋找一個遞歸函數的字符串迴文

Question

我想寫一個遞歸函數來確定一個字符串是否是迴文。以下是我迄今爲止：

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

出於某種原因，當遞歸函數得到足夠深，word.length（）小於或等於1，它不返回true。我似乎無法弄清楚爲什麼。是否與遞歸函數的工作方式有關，或者在我評論DEBUGGING之前如何重新調整行中單詞的長度？

我不像C++那麼有天賦，所以請原諒我的編程看起來很差。

Answer 1

你至少在這裏缺少一個return語句：

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

如果長度不爲1您呼叫的遞歸功能palindrome，忽略它的返回值，然後在返回總是false。通過我的修復，在刪除第一個和最後一個字母后，您將返回使用word調用的迴文函數的結果。

Answer 2

answer by hivert確定了您的問題，但如果您對性能感興趣，請考慮使用迭代器或索引，而不是製作大量字符串副本。也許是這樣的：

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

但是，如果你想檢查一個很長的字符串，你可以得到一個堆棧溢出。如果幸運的話，編譯器可能會執行tail call optimization。當然，在這種情況下，很容易去除遞歸和使用，而不是一個循環：

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

Answer 3

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