2

我知道递归是一个函数调用自身的时候，但是我无法弄清楚如何让我的函数调用它自己来获得所需的结果。我需要简单地计算给函数的字符串中的元音。

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

5 回答 5

6

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

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

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

  • 基本情况：如果字符串为空，则元音为零。
  • 递归步骤：如果第一个字符是元音，则在解中加 1，否则加 0。无论哪种方式，通过删除第一个字符来推进递归并继续遍历字符串的其余部分。

第二步最终将字符串减少到零长度，从而结束递归。或者，可以使用尾递归来实现相同的过程- 并不是说​​它对性能有任何影响，因为 CPython 没有实现尾递归消除。

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
于 2012-10-13T23:10:03.090 回答
3

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

  • 如果字符串为空，则返回 0。
  • 如果字符串不为空并且第一个字符是元音，则返回 1 + 对字符串其余部分的递归调用的结果
  • 如果字符串不为空并且第一个字符不是元音，则返回对字符串其余部分的递归调用的结果。
于 2012-10-13T22:47:14.733 回答
1

使用 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

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

于 2012-10-13T22:41:58.933 回答
0

这是直接的方法：

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

这与更少的代码相同：

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

这是另一个：

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

不幸的是，这对于长字符串会失败。

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

如果您对此感兴趣，请查看此博客文章。

于 2012-10-13T23:45:14.120 回答
0

这里有一个函数式编程方法供你学习：

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)

想法是将问题分为两个步骤，第一个（“map”）将数据转换为另一种形式（字母 -> 0/1），第二个（“reduce”）将转换后的项目收集为一个值（ 1 的总和）。

参考：

另一种更高级的解决方案是将问题转换为尾递归并使用蹦床来消除递归调用：

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

请注意，与简单的解决方案不同，此解决方案可以处理非常长的字符串，而不会导致“超出递归深度”错误。

于 2012-10-13T23:42:58.377 回答