这是使用递归的正确方式吗？

Question

给定字符串s和t递归计算，如果t包含在s返回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;
}

如果有人在我的代码中发现错误，请告诉我，这样我就可以修复它，或者在哪里可以了解/阅读有关这个主题的更多信息。我需要为本周三递归测试做好准备。

Answer 1

自从我写了答案后，这个问题就变了。

我的评论是关于这样的代码(并且可以恢复).

#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-statement末尾留下一个空体。无论测试的结果如何，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;
}

祝你的班级好运！

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

Answer 3

您在正确的行上--只要函数自己调用它自己，就可以说它是递归的--但是即使是最简单的测试也应该告诉您，您的代码不能正确工作。例如，将"sip"更改为"sipx"，它仍然输出true。你编译并运行了这个程序吗？你用不同的输入测试过吗？