Это правильный способ использования рекурсии? - PullRequest
Новая
       6

Это правильный способ использования рекурсии?

0 голосов
/ 06 декабря 2011

Данные строки s и t вычисляются рекурсивно, если t содержится в s return true.

Пример: bool find("Names Richard", "Richard") == true;

Я написал код ниже, но я не уверен, правильно ли это использовать рекурсию в C ++; Я только что изучил рекурсию сегодня в классе. 

#include <iostream>

using namespace std;

bool find(string s, string t)
{
    if (s.empty() || t.empty())
        return false;
    int find = static_cast<int>(s.find(t));
    if (find > 0)
        return true;
}

int main()
{
    bool b = find("Mississippi", "sip");
    string s;
    if (b == 1) s = "true";
    else 
        s = "false";
    cout << s;
}

Если кто-то обнаружит ошибку в моем коде, пожалуйста, скажите мне, чтобы я мог ее исправить, или где я могу узнать / прочитать больше об этой теме. Мне нужно подготовиться к тесту по рекурсии в эту среду.

Ответы [ 4 ]

4 голосов
/ 06 декабря 2011

Вопрос изменился с тех пор, как я написал свой ответ.

Мои комментарии касаются кода, который выглядел так (и может повторить) ... 

#include <iostream>

using namespace std;

bool find(string s, string t)
{
    if (s.empty() || t.empty())
        return false;
    string start = s.substr(0, 2);
    if (start == t && find(s.substr(3), t));
        return true;
}

int main()
{
    bool b = find("Mississippi", "sip");
    string s;
    if (b == 1) s = "true";
    else 
        s = "false";
    cout << s;
}

Следите за этим: 

if (start == t && find(s.substr(3), t));
    return true;

Это не то, что вы думаете.

; в конце if заявления оставляетпустое тело.Ваша find() функция вернет true независимо от результата этого теста.

Я рекомендую вам включить уровни предупреждений на вашем компиляторе, чтобы уловить проблему такого рода, прежде чем отлаживать ее.

Кроме того, я обнаружил, что использование скобок вокруг каждого кодового блока, даже однострочных, помогает мне избежать ошибок такого рода.

В вашем коде есть и другие ошибки.Удаление магических чисел 2 и 3 из find() побудит вас задуматься о том, что они представляют, и укажет вам правильный путь.

Как вы ожидаете, что start == t && find(s.substr(3), t) будет работать?Если вы можете выразить алгоритм на простом английском (или на вашем родном языке), у вас гораздо больше шансов выразить его на C ++.

Кроме того, я рекомендую добавить тестовые случаи, которые должны возвращать false(например, find("satsuma", "onion")), чтобы гарантировать, что ваш код работает так же, как и вызовы, которые должны возвращать true.

Последний совет - стилистический: раскладывание вашего кода таким образом сделает логическое выражение, котороеВы тестируете более очевидное, не прибегая к временному и сравнивая с 1: 

int main()
{
    std::string s;
    if (find("Mississippi", "sip"))
    {
        s = "true";
    }
    else
    {
        s = "false";
    }
    std::cout << s << std::endl;
}

Удачи в вашем классе!

2 голосов
/ 06 декабря 2011

Ваша рекурсивная функция нуждается в 2 вещах:

  1. Определенные условия неудачи и успеха (может быть больше 1)
  2. вызов сам по себе для обработки более простой версии проблемы (приближаясь к ответу).

Вот краткий анализ: 

bool find(string s, string t)
{
    if (s.empty() || t.empty())  //definite condition of failure. Good
        return false;
    string start = s.substr(0, 2);
    if (start == t && find(s.substr(3), t)); //mixed up definition of success and recursive call
        return true;
}

Попробуйте вместо этого: 

bool find(string s, string t)
{
    if (s.empty() || t.empty())  //definite condition of failure. Done!
        return false;
    string start = s.substr(0, 2); 
    if (start == t)  //definite condition of success. Done!
        return true;
    else            
        return find(s.substr(3), t) //simply the problem and return whatever it finds
}
0 голосов
/ 06 декабря 2011

Вы не используете рекурсию.Использование std::string::find в вашей функции похоже на обман (это, скорее всего, не принесет очков).

Единственная разумная интерпретация задачи: Проверьте, является ли t инфиксом s без использования цикловили строковые функции.

Давайте рассмотрим тривиальный случай: Epsilon (пустое слово) - это инфикс любого слова, поэтому, если выполняется t.empty(), вы должны вернуть true.В противном случае у вас есть два варианта:

  1. t может быть префиксом s, который легко проверить с помощью рекурсии;просто проверьте, равен ли первый символ t первый символ s, и вызовите isPrefix с остальными строками.Если это возвращает true, вы возвращаете true.
  2. В противном случае вы вводите первый символ s (а не t) и продолжаете рекурсивно (на этот раз вызываете find).

Если вы будете следовать этому рецепту (который, кстати, проще реализовать с char const*, чем с std::string, если вы спросите меня), вы получите рекурсивную функцию, которая использует только условные выражения и не поддерживает библиотеку.

Примечание: это не во всех наиболее эффективных реализациях, но вы просили не эффективности, а рекурсивной функции.

0 голосов
/ 06 декабря 2011

Вы находитесь на правильных строках - пока функция вызывает себя, вы можете сказать, что она рекурсивная - но даже самое простое тестирование должно сказать вам, что ваш код работает неправильно. Например, измените "sip" на "sipx", и оно все равно выдаст true. Вы скомпилировали и запустили эту программу? Вы проверяли это с различными входами?

...