재귀 함수로 문자열 Palindrome 찾기

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과 동일, 그건 사실 반환하지 않습니다. 나는 이유를 알 수없는 것 같습니다. 재귀 함수가 작동하는 방식과 관련이 있습니까? 또는 디버깅을 언급하기 전에 줄의 길이를 어떻게 다시 조정합니까?

저는 C++에서 재능이 없기 때문에 제 프로그래밍이 좋지 않으면 실례합니다.

Answer 1

당신은 적어도 여기 return 문을 누락 : 길이가 1없는

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

경우, 반복적으로 palindrome 함수를 호출의 반환 값을 무시하고 항상 false을 반환한다. 내 수정 프로그램을 사용하면 첫 번째 및 마지막 문자를 제거한 후 단어로 호출 된 palindrome 함수의 결과를 반환합니다.

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