Counting vowels in a string using recursion

Question

I understand that recursion is when a function calls itself, however I can't figure out how exactly to get my function to call it self to get the desired results. I need to simply count the vowels in the string given to the function.

def recVowelCount(s):
    'return the number of vowels in s using a recursive computation'
    vowelcount = 0
    vowels = "aEiou".lower()
    if s[0] in vowels:
        vowelcount += 1
    else:
        ???

---

I came up with this in the end, thanks to some insight from here.

def recVowelCount(s):
'return the number of vowels in s using a recursive computation'
vowels = "aeiouAEIOU"
if s == "":
    return 0
elif s[0] in vowels:
    return 1 + recVowelCount(s[1:])
else:
    return 0 + recVowelCount(s[1:])

Solution 1

Try this, it's a simple solution:

def recVowelCount(s):
    if not s:
        return 0
    return (1 if s[0] in 'aeiouAEIOU' else 0) + recVowelCount(s[1:])

It takes into account the case when the vowels are in either uppercase or lowercase. It might not be the most efficient way to traverse recursively a string (because each recursive call creates a new sliced string) but it's easy to understand:

• Base case: if the string is empty, then it has zero vowels.
• Recursive step: if the first character is a vowel add 1 to the solution, otherwise add 0. Either way, advance the recursion by removing the first character and continue traversing the rest of the string.

The second step will eventually reduce the string to zero length, therefore ending the recursion. Alternatively, the same procedure can be implemented using tail recursion - not that it makes any difference regarding performance, given that CPython doesn't implement tail recursion elimination.

def recVowelCount(s):
    def loop(s, acc):
        if not s:
            return acc
        return loop(s[1:], (1 if s[0] in 'aeiouAEIOU' else 0) + acc)
    loop(s, 0)

Just for fun, if we remove the restriction that the solution has to be recursive, this is how I'd solve it:

def iterVowelCount(s):
    vowels = frozenset('aeiouAEIOU')
    return sum(1 for c in s if c in vowels)

Anyway this works:

recVowelCount('murcielago')
> 5

iterVowelCount('murcielago')
> 5

Solution 2

Your function probably needs to look generally like this:

• if the string is empty, return 0.
• if the string isn't empty and the first character is a vowel, return 1 + the result of a recursive call on the rest of the string
• if the string isn't empty and the first character is not a vowel, return the result of a recursive call on the rest of the string.

Solution 3

Use slice to remove 1st character and test the others. You don't need an else block because you need to call the function for every case. If you put it in else block, then it will not be called, when your last character is vowel: -

### Improved Code

def recVowelCount(s):
    'return the number of vowels in s using a recursive computation'

    vowel_count = 0 
    # You should also declare your `vowels` string as class variable  
    vowels = "aEiou".lower()

    if not s:
        return 0

    if s[0] in vowels:
        return 1 + recVowelCount(s[1:])

    return recVowelCount(s[1:])

# Invoke the function
print recVowelCount("rohit")   # Prints 2

This will call your recursive function with new string with 1st character sliced.

Comments

[Daniel Love Jr]

Where would I put the slice statement?

[Rohit Jain]

@Amber. Oh yeah.. Edited.. You should have it outside your if. It should be called in any case. where your last character was vowel or not.

[Amber]

There's still an issue here that nothing's being returned.

[Rohit Jain]

@Amber. Yeah that OP can return the vowelCount from the function.. Ok, I'll post the complete function.

[Daniel Love Jr]

Well I would just print(vowelcount) at the end.

[Amber]

@DanielLoveJr You don't want to be calling print from the recursive function.

[Daniel Love Jr]

Hrm, either way I get a lot of red text and I'm not fully understanding what is happening. I can clearly see it's "iterating" through the string based on the number of red text lines, but I pretty much have that and it's not working

[Joran Beasley]

man i wish i had had stack overflow to do my homework when i was in school :P ... +1 for great answer

[georg]

actually, recVowelCount doesn't "work" (try recVowelCount('a'*1000))

[Óscar López]

@thg435 That's Python's fault, not the algorithm's. Although it's possible to increment the recursion depth and the algorithm could be rewritten to be tail-recursive, that doesn't change the fact that Python doesn't optimize for tail call elimination. All recursive algorithms of big enough size in Python are doomed to fail.

[Daniel Love Jr]

lol actually I prefer to understand things and not just blindly copy them from this site. I usually only ask when I have no other options. My professor is at a conference in Calgary and is unavailable to answer my emails so I come here.

[georg]

@ÓscarLópez: it's perfectly possible to code tail-recursive algorithms in python in a stack-safe way. The fact that the language doesn't provide that out of the box is quite a poor excuse for naive coding.

[Daniel Love Jr]

This comment was the most helpful, I didn't copy anyone's work.

[Óscar López]

@thg435 although it's possible to code the algorithm in a tail-recursive fashion (I just updated my answer with one such implementation) it's useless - anyway the standard Python implementation won't perform tail-call elimination. Given the nature of the question (it's an academic exercise after all) it's more important to give a clear answer than an optimized solution, that'd be overkill.