1

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

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

}
4

4 回答 4

1

这个“程序”有太多问题，无法快速解决。对于初学者，请考虑以下事项：

  • 你的“递归”一遍又一遍地调用具有相同状态的函数，所以最终你会破坏堆栈。
  • string.find()在未找到字符的情况下返回一个npos。
于 2013-11-13T21:53:21.773 回答
1

您的else分支不断将整个字符串传递给递归调用。这将一直持续到堆栈溢出。您只需要在第一个实例之后传递字符串的一部分c。您可以通过更改来做到这一点

return count + f_r(str,c);

至

str = str.substr(pos, str.size()-pos);
return count + f_r(str,c);

另请注意，由于countis always 1，此块将更简单为

pos++;
str = str.substr(pos, str.size()-pos);
return 1 + f_r(str,c);
于 2013-11-13T21:53:41.577 回答
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()有些毫无意义。

于 2013-11-13T22:27:33.753 回答
0

我会使用静态变量编写函数。

std::string::size_type f_r( const std::string &s, char c )
{
    static std::string::size_type pos;

    pos = s.find( c, pos );

    return ( pos == std::string::npos ? pos = 0 : ( ++pos, 1 + f_r( s, c ) ) );
}
于 2013-11-13T22:04:20.343 回答