Using recursion to determine no. of letters

[ToniAz]

Hello everyone, 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 (possible due to memory overflow).

I tried declaring integers using the new operator to save memory but still, my program crashed!

This is my code here:

Any help is very much appreciated!

#include <iostream>
#include <string>

using namespace std;

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

}

What I am trying to do is:
Starting my search at 0 position, then I increment if character is found.
I start with a 0-value of count. When new appearance is found, I increment count.

[Albatross]

Every time you run the function, you set pos to zero. Initialize pos outside of the function.

-Albatross

[Dufresne]

First of all , you don't need to declare count variable , you can simply use 1 instead.
You shall also use substring here. Becase you're sending same string again and again.You shall discard the part that function already searched.
So your return statement in else block , shall be
return 1 + f_r( str.substr(pos),c)

[Duthomhas]

When using recursion, you must keep what you would ordinarily use as local variables (those inside your function) as function arguments.

For example, given the string "Hello world!"
If I were to ask how many lowercase 'L's there were, we would need four pieces of information:
1 - the string itself
2 - the character we are looking for
3 - where in the string we are at
4 - the number of times we have found the character

The last item is itself the result of the function, so we don't need to put it in as a function argument. This gives us a function prototype something like this:

unsigned          // result = number of times 'c' appears in 's'
count_r(
  string   s,     // the string we are searching
  unsigned c,     // the char we are searching for
  unsigned n = 0  // the current index into the string
  );

Notice how I set n to default to zero, the first character in the string. This makes it very natural to call your function:
cout << "The number of 'l's in \"Hello world!\" is " << count_r( "Hello world!", 'l' ) << ".\n";

Now the body of the function is pretty simple.
1 - if the index into the string, n, is too big, we are done. Return zero.
2 - if the indexed character equals the character we are looking for, return one plus the number of times the character appears in the remainder of the string.
3 - otherwise, just return the number of times the character appears in the remainder of the string.

Determining the number of times the character appears in the remainder of the string is pretty simple. As a hint, to count the number of 'o's in the "world!" part of "Hello world!", I would ask:
count_r( "Hello world!", 'o', 6 ).

The idea in recursion is to break a problem down into simple parts that add (or otherwise combine) together to produce the total answer. Hence, our string is a series of additions:

H   e   l   l   o       w   o   r   l   d   !
0 + 0 + 1 + 1 + 0 + 0 + 0 + 0 + 0 + 1 + 0 + 0

This is the same as:

0 +(0 +(1 +(1 +(0 +(0 +(0 +(0 +(0 +(1 +(0 +(0)))))))))))

which is:

first_letter_in( "Hello world!" ) == 'l'
+
first_letter_in( "ello world!" ) == 'l'
+
first_letter_in( "llo world!" ) == 'l'
+
first_letter_in( "lo world!" ) == 'l'
+
first_letter_in( "o world!" ) == 'l'
+
...

Recursion is popular in list processing -- which is what you are doing: processing a list of characters, aka a 'string' -- because it is easy to think of it this way. If you can do something to the first item in a list in relation to the remainder of the list, then you can do it to the whole list.

In counting a specific character, you are counting whether or not the character occurs at the head of the list plus the same for the remainder of the list.

Hope this helps.

[edit] BTW, Dufresne's example also works. Instead of keeping an index into the list (string), he is simply passing the remainder of the list (string) in as argument to the function directly.