Почему удаление этого оператора возврата влияет на результат всей рекурсивной функции?

Question

Я пишу палиндромную проверку с использованием рекурсии. Я не понимаю, почему удаление оператора

return true

в конце функции влияет на возвращаемое значение.

int firstChar = 0;
int lastChar = 0;
// These two variables are used to transverse the string from both ends 
// eventually meeting

Код # 1:

bool palindromeCheck (string text, int firstChar, int lastChar)
{
    string tempCleanText = text;

    // Removes all punctation and space
    if (firstChar == 0)
    {
        // Cleans text, ignore.
        tempCleanText = cleanString(tempCleanText);

        // Sets this variable to the end of the string
        lastChar = tempCleanText.size() - 1;
    }

    // Base Case
    if (firstChar >= lastChar)
    {
        return true;
    }

    if (tempCleanText.at(firstChar) == tempCleanText.at(lastChar))
    {
        palindromeCheck(tempCleanText, ++firstChar, --lastChar);
    }
    else
    {
        return false;
    }

    return true;    // Keeping this in works
}

Это возвращает true, как это должно быть для всех палиндромов, и false для всех непалиндромов.

Код # 2:

bool palindromeCheck (string text, int firstChar, int lastChar)
{
    string tempCleanText = text;

    // Removes all punctation and space.
    if (firstChar == 0)
    {
        // Cleans text, ignore.
        tempCleanText = cleanString(tempCleanText);

        // Sets this variable to the end of the string
        lastChar = tempCleanText.size() - 1;
    }

    // Base Case
    if (firstChar >= lastChar)
    {
        return true;
    }

    if (tempCleanText.at(firstChar) == tempCleanText.at(lastChar))
    {
        palindromeCheck(tempCleanText, ++firstChar, --lastChar);
    }
    else
    {
        return false;
    }

    // there is no return true here, and so the output is no longer correct
}

Это возвращает true только для некоторых из палиндромов, и false для всех непалиндромов.

Палиндромы, такие как,

amanaplanacanalpanama <- длина размера 21 </p>

Возвращает false, когда должно возвращаться true.

В ходе тестирования показано, что базовый случай вводится с использованием последнего палиндрома, а это означает, что функция видит его как действительный палиндром. Но я предполагаю, что программа затем раскручивает стек вызовов и, когда он проходит через все предыдущие вызовы функций, что-то заставляет функцию возвращать значение false.

Answer 1

Для начинающих функция в любом случае некорректна. Например, для строки "1231" функция возвращает true. Я надеюсь, что вы можете проверить это сами.

Эта часть функции

if (tempCleanText.at(firstChar) == tempCleanText.at(lastChar))
{
    palindromeCheck(tempCleanText, ++firstChar, --lastChar);
}
else
{
    return false;
}

return true;    // Keeping this in works

должна быть по крайней мере заменена следующим фрагментом кода

if (tempCleanText.at(firstChar) == tempCleanText.at(lastChar))
{
    return palindromeCheck(tempCleanText, ++firstChar, --lastChar);
}
else
{
    return false;
}

То есть это оператор return

return true;    // Keeping this in works

должен быть полностью удален.

Что касается вашего вопроса, то без последнего оператора return у функции будет неопределенное поведение, потому что она ничего не возвращает после оператора if. То есть оператор if

if (tempCleanText.at(firstChar) == tempCleanText.at(lastChar))
{
    palindromeCheck(tempCleanText, ++firstChar, --lastChar);
}
else
{
    return false;
}

был успешно выполнен при условии, что

tempCleanText.at(firstChar) == tempCleanText.at(lastChar))

, и что возвращает функция после выполнения подоператора оператора if? Ничего! :)

Также не имеет смысла объявлять два дополнительных параметра (индекса) помимо самой строки, потому что в любом случае строка передается по значению, и вы всегда можете получить ее размер, вызвав функцию-член size().

Я могу предложить следующую реализацию функции Аналогично вашей функции эта реализация функции возвращает true в случае пропуска пустой строки.

#include <iostream>
#include <iomanip>
#include <string>
#include <cctype>

bool palindromeCheck( std::string s )
{
    if ( s.size() < 2 )
    {
        return true;
    }
    else if ( ispunct( ( unsigned char )s.front() ) || isspace( ( unsigned char )s.front() ) )
    {
        return palindromeCheck( s.substr( 1 ) );
    }
    else if ( ispunct( ( unsigned char )s.back() ) || isspace( ( unsigned char )s.back() ) )
    {
        return palindromeCheck( s.substr( 0, s.size() - 1 ) );
    }
    else if ( s.front() == s.back() )
    {
        return s.size() == 2 ? true : palindromeCheck( s.substr( 1, s.size() - 2) ); 
    }
    else
    {
        return false;
    }
}

int main() 
{
    std::cout << std::boolalpha << palindromeCheck( "" ) << '\n';
    std::cout << std::boolalpha << palindromeCheck( "1" ) << '\n';
    std::cout << std::boolalpha << palindromeCheck( "1 1" ) << '\n';
    std::cout << std::boolalpha << palindromeCheck( "1,2,2,1" ) << '\n';
    std::cout << std::boolalpha << palindromeCheck( "1 2 3 2 1" ) << '\n';
    std::cout << std::boolalpha << palindromeCheck( "12341" ) << '\n';

    return 0;
}

Вывод программы:

true
true
true
true
true
false

Answer 2

При возврате из функции, не являющейся пустым, без явного возврата значения через ключевое слово return вызывает неопределенное поведение . Согласно C ++ spe c, программа, которая вызывает неопределенное поведение, может делать буквально все что угодно, и вся вина за все возникающие странности будет лежать у ног программиста, который написал код, вызвавший неопределенное поведение.

В этом случае, скорее всего, действительно происходит то, что когда ваша функция возвращается, опуская конец функции (и не выполняет return false), место, в котором возвращаемое значение функции было сохранено, просто никогда записывается в - это означает, что для вызывающего кода значение, возвращаемое вашей функцией, будет равно значению, которое было в этом месте, когда ваша функция вернется. Предварительно существующее значение в этом месте будет произвольным и трудно предсказуемым, поскольку оно является результатом различных деталей, касающихся выполнения программы, и, следовательно, поведение программы будет произвольным и трудно предсказуемым, а также .

Решение состоит в том, чтобы всегда возвращать значение явно; Включение предупреждений в вашем компиляторе позволит ему помочь вам в этой задаче, предупредив вас, если вы когда-нибудь забудете вернуть значение в каком-нибудь пути кода.

Answer 3

может быть

// ...

if (tempCleanText.at(firstChar) == tempCleanText.at(lastChar))

{
   return palindromeCheck(tempCleanText, ++firstChar, --lastChar); 
}

else
    return false;
// ...