Finding character count in string using recursion

Question

I am required to use recursion to determine the number of occurrences of a certain character in a given string. Now the non-recursive function is very simple. But, when trying to use recursion, I am getting an error when my program runs

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

}

By the looks of it, f_r has no viable break condition. It will always find the first char, and recurse with the same input data. — WhozCraig
– WhozCraig, Commented Nov 13, 2013 at 21:51
std::string::find returns std::string::npos when a value isn't found. You should test explicitly against that to decide if it failed to find something. — Retired Ninja
– Retired Ninja, Commented Nov 13, 2013 at 21:52
@RetiredNinja and Jekyll Absolutely. Even if that is fixed, I don't see how this doesn't recurse infinitely. — WhozCraig
– WhozCraig, Commented Nov 13, 2013 at 21:53

WhozCraig · Accepted Answer · 2013-11-13 22:27:33Z

Problem Analysis

Your fundamental problems in your implementation are:

Failure to use the proper data type for the discovered position
Incorrect conditional to terminate the recursion
Incorrect recursion parameters (you're passing the same parameters).

Solution

That said, this function is simpler than you may think:

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

Note the following:

Uses std::string::size_type for the position calculation
Terminates the recursion if no value is returned by comparing against std::string::npos, returning 0 as the result of that final recursion invocation.
Passes a substring of the original as a parameter to the recursed call. This substring includes all remaining characters passed the discovered location in pos.

Non Recursive Solution

I realize you're tasked with doing this recursively, but I wanted to make sure you knew the way to do it iteratively without having to write the loop yourself. The C++ standard library includes an algorithm called std::count that does exactly what this does, but with a single pass, no sub-allocations like those delivered from substr(), and no recursion at all:

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

and yes, it does make the very reason for f_r() somewhat pointless.

Alexander L. Belikoff · Accepted Answer · 2013-11-13 21:53:21Z

1

This "program" has too many problems to offer a quick fix. For starters, consider the following:

Your "recursion" keeps calling the function with the same state over and over again, so ultimately you'll blow the stack.
string.find() returns an npos in case of not found character.

answered Nov 13, 2013 at 21:53

Alexander L. Belikoff

5,7331 gold badge27 silver badges34 bronze badges

Comments

simonc · Accepted Answer · 2013-11-13 21:53:41Z

1

Your else branch keeps passes the entire string into the recursive call. This will continue until the stack overflows. You need to only pass the part of the string after the first instance of c. You can do this by changing

return count + f_r(str,c);

to

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

Note also that since count is always 1, this block would be simpler as

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

answered Nov 13, 2013 at 21:53

simonc

42.3k12 gold badges91 silver badges105 bronze badges

2 Comments

Jim Rhodes Over a year ago

Wouldn't it be more efficient to add pos as an argument to f_r() instead of doing substr?

WhozCraig Over a year ago

@PeteBecker lol. Flashback a long time ago from my op-sys graduate course. The instructor was fairly blunt: "1. Architect an efficient design. 2. If your project doesn't work, you fail the course, and I don't care how efficient your design is."

Vlad from Moscow · Accepted Answer · 2013-11-13 22:04:20Z

0

I would write the function using a static variable.

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

answered Nov 13, 2013 at 22:04

Vlad from Moscow

313k27 gold badges204 silver badges358 bronze badges

Collectives™ on Stack Overflow

Finding character count in string using recursion

4 Answers 4

Comments

Comments

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related