使用递归计算字符串中的元音

Question

我知道递归是当一个函数调用它自己时，但是我不知道如何确切地让我的函数调用它自己来获得期望的结果。我需要简单地计算给函数的字符串中的元音。

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:
        ???

---

我最终想到了这个，多亏了这里的一些洞察力。

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

您的函数可能需要大致如下所示：

• 如果字符串为空，则返回0。
• 如果字符串不是空的，并且第一个字符是元音，则返回1+对字符串其余部分进行递归调用的结果
• 如果字符串不是空的，并且第一个字符不是元音，则返回对字符串其余部分的递归调用的结果。

Answer 2

试试这个，这是一个简单的解决方案：

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

当元音是大写或小写时，它会考虑大小写。这可能不是递归遍历字符串的最有效方法（因为每次递归调用都会创建一个新的切片字符串），但很容易理解：

• 基本大小写：如果字符串为空，则它有零个元音。
• 递归步骤：如果第一个字符是元音，则向解决方案中添加1，否则添加0。不管怎样，通过删除第一个字符并继续遍历字符串的其余部分来推进递归。

第二步最终会将字符串长度减少到零，从而结束递归。或者，可以使用tail recursion来实现相同的过程，但考虑到CPython没有实现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)

有趣的是，如果我们取消了解决方案必须是递归的限制，我将这样解决它：

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

无论如何，这是有效的：

recVowelCount('murcielago')
> 5

iterVowelCount('murcielago')
> 5

Answer 3

使用slice删除第一个字符并测试其他字符。您不需要else块，因为您需要为每种情况调用函数。如果把它放在else块中，那么当最后一个字符是元音时，它将不会被调用：

### 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

这将使用第一个字符切片的新字符串调用递归函数。