CODEWITHSUNDEEP
pythonstringrecursioncount
Daniel Love Jr
Daniel Love Jr

Reputation: 960

Counting vowels in a string using recursion

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

Upvotes: 2

Views: 20847

Answers (5)

Óscar López
Óscar López

Reputation: 236044

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

Upvotes: 6

georg
georg

Reputation: 214989

Here's a functional programming approach for you to study:

map_ = lambda func, lst: [func(lst[0])] + map_(func, lst[1:]) if lst else []
reduce_ = lambda func, lst, init: reduce_(func, lst[1:], func(init, lst[0])) if lst else init

add = lambda x, y: int(x) + int(y)
is_vowel = lambda a: a in 'aeiou'

s = 'How razorback-jumping frogs can level six piqued gymnasts!'
num_vowels = reduce_(add, map_(is_vowel, s), 0)

The idea is to divide the problem into two steps, where the first ("map") converts the data into another form (a letter -> 0/1) and the second ("reduce") collects converted items into one single value (the sum of 1's).

References:

Another, more advanced solution is to convert the problem into tail recursive and use a trampoline to eliminate the recursive call:

def count_vowels(s):
    f = lambda s, n: lambda: f(s[1:], n + (s[0] in 'aeiou')) if s else n
    t = f(s, 0)
    while callable(t): t = t()
    return t

Note that unlike naive solutions this one can work with very long strings without causing "recursion depth exceeded" errors.

Upvotes: 0

dnozay
dnozay

Reputation: 24324

this is the straightforward approach:

VOWELS = 'aeiouAEIOU'

def count_vowels(s):
    if not s:
        return 0
    elif s[0] in VOWELS:
        return 1 + count_vowels(s[1:])
    else:
        return 0 + count_vowels(s[1:])

here is the same with less code:

def count_vowels_short(s):
    if not s:
        return 0
    return int(s[0] in VOWELS) + count_vowels_short(s[1:])

here is another one:

def count_vowels_tailrecursion(s, count=0):
    return count if not s else count_vowels_tailrecursion(s[1:], count + int(s[0] in VOWELS))

Unfortunately, this will fail for long strings.

>>> medium_sized_string = str(range(1000))
>>> count_vowels(medium_sized_string)
...
RuntimeError: maximum recursion depth exceeded while calling a Python object

if this is something of interest, look at this blog article.

Upvotes: 0

Rohit Jain
Rohit Jain

Reputation: 213311

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.

Upvotes: 1

Amber
Amber

Reputation: 526923

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.

Upvotes: 3

Related Questions