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:])

Answer 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

Answer 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.