recursions

Question

marnun 0 Light Poster

13 Years Ago

Write a recursive, bool-valued function, containsVowel, that accepts a string and returns true if the string contains a vowel.
A string contains a vowel if:
The first character of the string is a vowel, or
The rest of the string (beyond the first character) contains a vowel

This is one of the recursion exercises I couldn't get right.
Any suggestions? Thanks!

My code:

    bool containsVowel (string s) {
        if (s.substr(0,1)=="a") return true;
        if (s.substr(0,1)=="e") return true;
        if (s.substr(0,1)=="u") return true;
        if (s.substr(0,1)=="o") return true;
        if (s.substr(0,1)=="i") return true;
        containsVowel (s.substr(1,s.length()-1));
    }

c++ recursion

7 Contributors
9 Replies
530 Views
2 Weeks Discussion Span
Latest Post 13 Years Ago Latest Post by marnun

Dani AI

Generated 10 Months Ago

Quick diagnosis: the crash came from calling substr(1, ...) when s was already empty — std::string::substr throws out_of_range if the start position is > size. Add a base case before you touch s[0] or call substr, and be sure to return the result of the recursive call (missing return was another issue mentioned by ). was right to flag the empty-string check; and gave working ideas but both create new strings on every call, which is wasteful.

A safer, lighter recursive pattern avoids copying the string each time by passing it by const reference and using an index:

#include <string>
#include <cctype>

bool containsVowel(const std::string& s, std::size_t i = 0) {
    if (i >= s.size()) return false;
    unsigned char uc = static_cast<unsigned char>(s[i]);
    char c = std::tolower(uc);
    if (c=='a' || c=='e' || c=='i' || c=='o' || c=='u') return true;
    return containsVowel(s, i + 1);
}

If you just want a concise, fast solution, use the standard library instead of recursion:

bool containsVowelIter(const std::string& s) {
    return s.find_first_of("aeiouAEIOU") != std::string::npos;
}

Practical tips: always check the base case before indexing or calling substr; cast to unsigned char before std::tolower to avoid UB on negative-char platforms; avoid creating substrings in a loop (O(n^2) behavior). For simple ASCII checks this is enough; for full Unicode you need a different approach. This should make the function robust and faster than the version submitted by .

All 9 Replies

vmanes 1,165 Posting Virtuoso

13 Years Ago

For starters, I would turn your testing into a series of if..else if statements, including the final recusive call. Then you need and else case that returns false.

vmanes 1,165 Posting Virtuoso

13 Years Ago

Still missing parts.

Base case - when string being examined is empty.

The recusive call needs to be in an if..else, and it's return needs to be returned.

The return false needs to be in an else block.

T-Dogg3030 0 Newbie Poster

13 Years Ago

You are getting the out of bounds from line 8. Before you try to length() - 1, do a check to see if length == 0. If true, return false.

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

marnun 0 Light Poster · Answer 1 · 2012-12-12T19:23:02+00:00

hi, thanks for answering.
still get error from codeLab

    bool containsVowel (string s) {
        if (s.substr(0,1)=="a") return true;
        else if (s.substr(0,1)=="e") return true;
        else if (s.substr(0,1)=="u") return true;
        else if (s.substr(0,1)=="o") return true;
        else if (s.substr(0,1)=="i") return true;
        else 
            containsVowel (s.substr(1,s.length()-1));
        return false;
    }

this is the error message:

Remarks:

⇒ terminate called after throwing an instance of
'std::out_of_range'
⇒ what(): basic_string::substr

⇒ Your code had an error during execution

nullptr 167 Occasional Poster · Answer 2 · 2012-12-13T07:25:54+00:00

bool containsVowel (string s) 
{
    if (0 == s.length())
        return false;

    if ( (s.substr(0,1)=="a") || (s.substr(0,1)=="e") || (s.substr(0,1)=="i") ||
        (s.substr(0,1)=="o") || (s.substr(0,1)=="u") ) 
        return true;

    return containsVowel (s.substr(1, s.length() - 1));
}

I'll leave you to work out handling uppercase vowels.

Lucaci Andrew 140 Za s|n · Answer 3 · 2012-12-13T07:41:41+00:00

The thinking mainly is wrong, because, on recursive calls, if indeed a vowel is found, it will still return false, because of the last condition. I suggest you take an extra variable, if allowed, which will carry the information:

void containsVowel (string s, bool &isIt) {
    if (s.empty()) return;
    if (s[0]=='a' || s[0]=='e' || s[0]=='u' || s[0]=='o' || s[0]=='i') isIt=true;
    containsVowel(s.substr(1, s.size()-1), isIt);
}

int main(){
    string a="bcdghijklmnpqrst";
    bool isIt=false;
    containsVowel(a, isIt);
    if (isIt) cout<<"True.\n";
    else cout<<"Not true.\n";
    return 0;
}

Let me explain a bit what I mean, regarding your function:

string a="bcdfghijklmnpqrst"

this string conains the vowel i.

when calling your function, eventually will return true from finding the vowel:
here are the recursive returns:


"t" return false
"st" return false
"rst" return false
"qrst" return false
"pqrst" return false
"npqrst" return false
"mnpqrst" return false
"lmnpqrst" return false
"klmnpqrst" return false
"jklmnpqrst" return false
"ijklmnpqrst" return true // we found a solution
"hijklmnpqrst" return false //here the return changes, because 'h' is not a vowel.
"ghijklmnpqrst" return false
"fghijklmnpqrst" return false
"dfghijklmnpqrst" return false
"cdfghijklmnpqrst" return false
"bcdfghijklmnpqrst" return false

So, even thou your word conains vowels, it will still return false.
Again, I don't know if your teacher allowes you to make it into a void, and take an extra value which will hold the information.

Gonbe 32 Newbie Poster · Answer 4 · 2012-12-13T08:13:24+00:00

There is no need for additional variables.

#include <iostream>
#include <string>
#include <cctype>

using namespace std;

bool isVowel(const char symbol)
{
    return (string("aeiou").find(tolower(symbol)) != string::npos);
}

bool containsVowel(const string text)
{
    return ((text.length() > 0) && (isVowel(text[0]) || containsVowel(text.substr(1))));
}

int main()
{
    // Stuff with containsVowel..
    return 0;
}

YaLeon 0 Newbie Poster · Answer 5 · 2012-12-25T18:23:35+00:00

public boolean containsVowel ( String a)
{
if  (a.length() == 0)
    return false;

if ((a.charAt(a.length()-1)==('a'))||
      ((a.charAt(a.length()-1)==('e'))||
        ((a.charAt(a.length()-1)==('i'))||
            ((a.charAt(a.length()-1)==('o'))||
                ((a.charAt(a.length()-1)==('u')))))))
                    return true;
if ((a.charAt(a.length()-1)==('A'))||
      ((a.charAt(a.length()-1)==('E'))||
        ((a.charAt(a.length()-1)==('I'))||
            ((a.charAt(a.length()-1)==('O'))||
                ((a.charAt(a.length()-1)==('U')))))))
                    return true;
else 
 return containsVowel(a.substring(0, a.length()-1));
}

marnun 0 Light Poster · Answer 6 · 2012-12-27T18:32:53+00:00

Thanks everybody for extensive explanations - been very very helpful.
i ended up submitting the following code:

    bool containsVowel (string s) {
        bool hasVowel=false;
        if (s.length()==0) return false;
        else if (s[0]=='a'||
                    s[0]=='e'||
                    s[0]=='u'||
                    s[0]=='o'||
                    s[0]=='i'||
                    s[0]=='A'||
                    s[0]=='E'||
                    s[0]=='U'||
                    s[0]=='O'||
                    s[0]=='I') 
            hasVowel=true;
        else
            hasVowel=containsVowel(s.substr(1,s.length()-1));
        return hasVowel;
    }

recursions

Dani AI

Recommended Answers Collapse Answers

All 9 Replies

Recommended Answers