Python – Counting vowels in a string using recursion

countpythonrecursionstring

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

Best Answer

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
Related Topic