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を追加します。いずれの場合も、最初の文字を削除して再帰を進め、残りの文字列をトラバースし続けます。

2番目のステップでは、最終的に文字列の長さがゼロになり、再帰が終了します。または、末尾再帰を使用して同じ手順を実装することもできます。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

スライスを使用して最初の文字を削除し、他の文字をテストします。ケースごとに関数を呼び出す必要があるため、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

学習する関数型プログラミングのアプローチは次のとおりです。

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)

アイデアは、問題を2つのステップに分割することです。最初のステップ（「マップ」）はデータを別の形式（文字-> 0/1）に変換し、2番目のステップ（「リデュース」）は変換されたアイテムを1つの単一の値に収集します（ 1の合計）。

参照：

もう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 に答える
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 に答える