c++ - 使用递归查找字符串中的字符数

Question

我需要使用递归来确定给定字符串中特定字符的出现次数。现在非递归函数就很简单了。但是，当尝试使用递归时，我的程序运行时出现错误

short f_r(string, char);
int main()
{
    string str;
    char c;
    cout << "Enter a string: ";
    getline(cin,str);
    cout << "Enter a character: ";
    cin >> c;
    cout << "\nString: " << str << endl;
    cout << f_r(str,c) << endl;


    return 0;

}

short f_r(string str, char c)
{

    int pos = 0;
    pos = str.find(c, pos);
    if (pos >  str.length()) return 0;
    else
    {
        int count = 0;
        count++;
        pos++;
        return count + f_r(str,c);
    }

}

Answer 1

问题分析

您在实现中的基本问题是:

• 未能为发现的位置使用正确的数据类型
• 终止递归的条件不正确
• 递归参数不正确(您传递的是相同的参数)。

解决方案

也就是说，这个函数比你想象的要简单:

std::size_t f_r(const std::string& s, char c)
{
    std::string::size_type pos = s.find(c);
    return (pos == std::string::npos) ? 0 : (1 + f_r(s.substr(pos+1), c));
}

注意以下几点:

• 使用 std::string::size_type 进行位置计算
• 如果通过与 std::string::npos 比较没有返回任何值，则终止递归，返回 0 作为最终递归调用的结果。
• 将原始字符串的子字符串作为参数传递给递归调用。此子字符串包括 通过 在 pos 中发现的位置的所有剩余字符。

---

非递归解决方案

我知道您的任务是递归执行此操作，但我想确保您知道无需自己编写循环即可迭代执行此操作的方法。 C++ 标准库包含一个名为 std::count 的算法。它的作用完全是这样做的，但是只需要一次传递，就不会像substr() 那样进行子分配，而且根本没有递归:

std::size_t f_r(const std::string& s, char c)
{
    return std::count(s.begin(), s.end(), c);
}

是的，它确实让 f_r() 的理由变得毫无意义。