How do I count vowels in a string using recursion

Question

I'm trying to count the number of vowels in a string using recursion. Here is what I have so far:

int vowels(string str, int pos, int length)
{
    if (str.length() == 0)
    return 0;

    switch (str[pos])
    {
      case 'a':
      case 'e':
      case 'i':
      case 'o':
      case 'u':
      case 'A':
      case 'E':
      case 'I':
      case 'O':
      case 'U':
        return 1 + vowels(str.substr(1), pos, length);
      default:
        return vowels(str.substr(1), pos, length);
    }
}

int main()
{
    string str;
    int len;

    cout << "Enter a string: ";
    getline(cin, str);
    cout << endl;

    len = static_cast<int>(str.length());

    cout << "Number of vowels in \"" << str << "\" = "
         << vowels(str, 0, len) << endl;

    return 0;
}

The problem is, I need to set pos to 0 only on the first time the vowels function is called without resetting it to 0 on subsequent recursive calls. Also, instead of using substrings, I need to increment pos before each recursive call of vowels(). Also, the base case should be when pos == length (when there are no more characters to check in the string).

Answer 1

You shouldn't use recursion for this problem. There are times when it is sensible to use recursion when you're doing C++ development, but for general use the lack of tail-call elision represents a little bit of a performance bottleneck. Generally speaking, if a recursive process only calls itself once per invocation, you're probably better off using a loop. If a recusive process calls itself twice (eg. descending into the left and right branches of a tree-type data structure, or perhaps computing a fibonacci sequence), it may be easier to use a recursive function instead of a loop.

That said, this is clearly a homework assignment, and sensible software development practises have no place there.

Passing in pos and length as well as a string seems silly... C++ has already provided you with a nice general purpose tool to deal with iterating through a collection (and a string is just an iterable collection of characters after all) in the form of... Iterators!

Iterators effectively encapsulate the notion of 'position' within a container. string::begin() gets you an Iterator pointing to the beginning of the string, and string::end() gets you one pointed to the end. You can dereference a non-end iterator to get the character it points at (much like a pointer), and increment an iterator to advance it to the next element in the collection.

Here's an example which simply counts characters, but I'm sure you'll be able to adapt it to your needs.

template<class Iterator>
int count_characters(Iterator begin, Iterator end)
{
    // if we're at the end of the string, there's nothing more to count
    if (begin == end)
        return 0;
    else // note the pre-increment here. post-increment won't work.
        return 1 + count_characters(++begin, end);
}

It can be used like this:

std::string foo = "a phrase, yay";
std::cout << count_characters(foo.begin(), foo.end());

By way of a bonus, it can be used on any other simple container... a vector or set of char would work just as well as a string here, because iterators provide a nice generic way to work with containers. This facility probably isn't of interest for this specific homework question, however.

One function, no need for wrappers or passing superfluous parameters around. Be cautious if you copypaste this into the work you hand in; if you don't understand template it'll be a sure sign of thoughtless plagiarism ;-)

Answer 2

I would define the function the following way

#include <cstring>
#include <string>

std::string::size_type count_vowels( const std::string &s, 
                                     std::string::size_type pos, 
                                     std::string::size_type length )
{
   const char *vowels = "aeiouAEIOU";

   if ( s.length() <= pos || length == 0 ) return 0;

   return ( s[pos] && std::strchr( vowels, s[pos] ) != 0 ) + 
          count_vowels( s, pos + 1, length - 1 );
}

And using your approach

#include <string>

std::string::size_type count_vowels( const std::string &s, 
                                     std::string::size_type pos, 
                                     std::string::size_type length )
{
    if ( s.length() <= pos || length == 0 ) return 0;

    std::string::size_type n = 0;

    switch ( s[pos] )
    {
        case 'a':
        case 'e':
        case 'i':
        case 'o':
        case 'u':
        case 'A':
        case 'E':
        case 'I':
        case 'O':
        case 'U':
            ++n;
        default:
            return n + count_vowels( s, pos + 1, length - 1 );
    }
}

Answer 3

Seems like you forgot to increment pos:

/* inside the vowels function switch statement */
return 1 + vowels(str.substr(1), pos+1, length);
    default:
return vowels(str.substr(1), pos+1, length);

Besides, if you change the end of recursion condition to "pos==str.length()" you won't be needing str.substr(...) at all. Also, pass std::string by const reference (it's a good habit), if you do skip substr(...).