Le comptage des voyelles dans une chaîne de caractères en utilisant la récursivité

Je comprends que la récursivité est une fonction qui s'appelle elle-même, cependant, je ne peux pas comprendre comment exactement pour obtenir ma fonction à appeler elle-même pour obtenir les résultats souhaités. J'ai besoin de simplement compter le nombre de voyelles dans la chaîne de caractères donnée à la fonction.

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

Je suis venu avec cette à la fin, grâce à la perspicacité d'ici.

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:])
  • Ne pas utiliser un else bloc. Vous devez répéter, peu importe.
  • Ok je vais voir ce que je peux venir avec.
  • Les devoirs de la balise a été désapprouvée; merci de ne pas l'utiliser. Si vous pensez qu'il est important de mentionner le travail dans votre question elle-même. 🙂
InformationsquelleAutor Daniel Love Jr | 2012-10-13
  1. 6

    Essayer ça, c'est une solution simple:

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

    Il prend en compte le cas lorsque les voyelles sont en majuscules ou en minuscules. Il pourrait ne pas être le moyen le plus efficace pour parcourir récursivement une chaîne de caractères (parce que chaque appel récursif crée un nouveau tranches de chaîne), mais c'est facile à comprendre:

    • Cas de Base: si la chaîne est vide, alors il n'a pas de voyelles.
    • Récursive étape: si le premier caractère est une voyelle ajouter 1 à la solution, sinon, ajouter 0. De toute façon, l'avance de la récursivité par la suppression du premier caractère et de continuer à traverser le reste de la chaîne.

    La deuxième étape sera de réduire à terme la chaîne de longueur zéro, donc la fin de la récursivité. Sinon, la même procédure peut être mise en œuvre à l'aide de la queue de la récursivité - non pas que cela fait une différence en termes de performances, étant donné que Disponible ne pas mettre en œuvre la queue de la récursivité de l'élimination.

    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)

    Juste pour le fun, si nous supprimer la restriction que la solution doit être récursive, c'est de cette façon que j'avais de le résoudre:

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

    De toute façon cela fonctionne:

    recVowelCount('murcielago')
> 5

iterVowelCount('murcielago')
> 5
    • +1 ne Peut pas résister à droit de vote de cette. 🙂
    • J'ai copié votre if bien que dans mon code 😉
    • homme je souhaite que j'avais eu de débordement de pile à faire mes devoirs quand j'étais à l'école 😛 ... +1 pour la réponse très
    • en fait, recVowelCount ne pas "travailler" (essayez recVowelCount('a'*1000))
    • C'est Python de la faute, pas de l'algorithme. Bien qu'il soit possible d'augmenter la profondeur de récursivité et l'algorithme pourrait être réécrit pour être récursives terminales, qui ne change pas le fait que Python n'est pas optimiser pour queue d'appel d'élimination. Tous les algorithmes récursifs d'assez grande taille en Python sont vouées à l'échec.
    • lol en fait je préfère comprendre les choses et pas seulement aveuglément les copier à partir de ce site. J'ai l'habitude de demander seulement quand je n'ai pas d'autres options. Mon professeur est lors d'une conférence à Calgary et n'est pas disponible pour répondre à mes mails donc je viens ici.
    • il est parfaitement possible de code de la queue-d'algorithmes récursifs en python dans une pile de façon sécuritaire. Le fait que la langue n'a pas prévoir que la sortie de la boîte est tout à fait une mauvaise excuse pour naïf de codage.
    • bien qu'il soit possible de coder l'algorithme en une queue-récursive de la mode (je viens de mettre à jour ma réponse avec un exemple de mise en œuvre), il est inutile de toute façon le standard de Python de la mise en œuvre de ne pas accomplir la queue-appel d'élimination. Compte tenu de la nature de la question (c'est un exercice académique, après tout), il est plus important de donner une réponse claire qu'une solution optimisée, ce serait exagéré.

    InformationsquelleAutor Óscar López
  2. 3

    Votre fonction probablement besoin de chercher généralement comme ceci:

    • si la chaîne est vide, retourne 0.
    • si la chaîne n'est pas vide et le premier caractère est une voyelle, retour 1 + le résultat d'un appel récursif sur le reste de la chaîne
    • si la chaîne n'est pas vide et le premier caractère n'est pas une voyelle, retourner le résultat d'un appel récursif sur le reste de la chaîne.
    • +1 pour ne pas faire ses devoirs à la maison pour lui 🙂
    • Ce commentaire a été le plus utile, je n'ai pas de copie de quelqu'un de travail.
    InformationsquelleAutor Amber
  3. 1

    Utilisation tranche de supprimer le 1er caractère et de tester les autres. Vous n'avez pas besoin d'un autre bloc parce que vous devez appeler la fonction pour chaque cas. Si vous le mettez dans le bloc else, alors il ne sera pas appelé, lors de votre dernière lettre est une voyelle: -

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

    Cela appel de votre fonction récursive avec la nouvelle chaîne avec le 1er caractère tranché.

    • Qui ne devrait pas être dans un else bloc...
    • Où dois-je mettre la tranche de déclaration?
    • Oh oui.. Édité.. Vous devriez avoir à l'extérieur de votre si. Il doit être appelé en tout cas. où en est votre dernier caractère a été voyelle ou pas.
    • Il y a toujours un problème ici que rien n'est retourné.
    • Ouais c'OP pouvez retourner le vowelCount à partir de la fonction.. Ok, je vais poster la fonction complète.
    • Eh bien, je voudrais juste l'impression(vowelcount) à la fin.
    • Vous ne voulez pas appeler à imprimer à partir de la fonction récursive.
    • Gestion des ressources humaines, de toute façon, je reçois beaucoup de texte en rouge et je ne suis pas la pleine compréhension de ce qui se passe. Je peux clairement voir que c'est "itération" par le biais de la chaîne de caractères en fonction du nombre de rouge, les lignes de texte, mais je suis assez d'avoir ça et ça ne fonctionne pas
    • Prenez le code actuel à la place. De son mieux. 🙂

    InformationsquelleAutor Rohit Jain
  4. 0

    c'est l'approche simple:

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

    ici est le même avec moins de code:

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

    en voici une autre:

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

    Malheureusement, cette sera échouer pour de longues chaînes.

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

    si c'est quelque chose qui l'intéresse, regardez cet article de blog.

    InformationsquelleAutor dnozay
  5. 0

    Voici une approche par programmation fonctionnelle pour vous permettre de l'étudier:

    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)

    L'idée est de diviser le problème en deux étapes, où la première ("carte") convertit les données en une autre forme (une lettre -> 0/1) et la seconde ("réduire") recueille converti éléments en une seule valeur (la somme de 1).

    Références:

    Un autre, plus avancé solution est de convertir le problème en queue récursive et l'utilisation d'un trampoline pour éliminer l'appel récursif:

    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

    Noter que, contrairement naïfs solutions de cela, on peut travailler avec de très longues chaînes sans causer de "profondeur de récursion dépassé les erreurs".

    InformationsquelleAutor georg