Das Zeichen rekursiv zählen

Question

def count_m_recursive(sentence): 
    s = len(sentence) 
    if s == 0: 
     return 0 
    elif sentence[0] == 'm': 
     return 1 
    else: 
     return count_m_recursive(sentence[1:s-1] 

Dies ist mein Code. wenn count_m_recursive('my oh my') So I 2

bekommen soll Was ist falsch mit dem Code?

Answer 1

Zwei Dinge sind falsch:

1. Sie sind die letzten Zeichen auf jedem rekursiven Aufruf abschneidet:

   return count_m_recursive(sentence[1:s-1]) 
   

   Sie das Gespräch nicht zu s-1, das Ende Index begrenzen nicht enthalten.

2. Sie möchten den Rest des Textes nicht ignorieren, wenn Sie am Anfang eine m finden; Ihre Version gibt 1 zurück und ignoriert den Rest der Zeichenfolge.

Ihre Funktion arbeitet mit:

elif sentence[0] == 'm': 
    return 1 + count_m_recursive(sentence[1:]) 
else: 
    return count_m_recursive(sentence[1:]) 

oder vereinfacht:

def count_m_recursive(sentence): 
    if not sentence: # an empty string tests false 
     return 0 
    return (1 if sentence[0] == 'm' else 0) + count_m_recursive(sentence[1:]) 

oder sogar die Tatsache nutzen, dass bool ist eine Unterklasse von int und True 1 ist, False 0 :

def count_m_recursive(sentence): 
    if not sentence: # an empty string tests false 
     return 0 
    return (sentence[0] == 'm') + count_m_recursive(sentence[1:]) 

Demo:

>>> def count_m_recursive(sentence): 
...  if not sentence: # an empty string tests false 
...   return 0 
...  return (sentence[0] == 'm') + count_m_recursive(sentence[1:]) 
... 
>>> count_m_recursive('my oh my') 
2 

Answer 2

def count_m_recursive(sentence): #mmmm 
    if not sentence: 
     return 0 
    m_first = 1 if sentence[0] == 'm' else 0 
    return m_first + count_m_recursive(sentence[1:]) 

Um einige Probleme in der aktuellen Implementierung zu skizzieren:

1. Keine Notwendigkeit Länge eines Strings zu berechnen zu überprüfen, ob es leer ist. Leere Strings werden equivivalent zu False in boolean „Kontext“ (z not s ist wahr, wenn s leer ist oder None)
2. Sie Summe nicht auf Vorkommen des m in einem String, so sollte es einige count_so_far + recursive_call() sein. In Ihrem Fall, da Sie Zeichenkette durch Char chartern count_so_far ist 1, wenn aktuelle Char ist m, 0 sonst.
3. Proper Slicing, um die ganze Zeichenfolge außer den ersten N Zeichen zu erhalten wäre string[N:]. Es gibt eine good explanation of slicing auf SO

Auch dies ist ein perfektes Beispiel für tail recursive algorithm. Solche Arten von Algorithmen können als eine Schleife ausgedrückt werden mit dem Vorteil der Ausführung in einem Aufrufstapelrahmen. Beachten Sie, dass viele Compiler ohnehin die Tail-Rekursion für die Schleife optimieren (das gilt jedoch nicht für den Python-Interpreter).

Answer 3

Problem ist mit

1. elif sentence[0] == 'm':
2. slicing off last char with sentence[1:-1]

// Boolean Hinweis Klasse von Integer-Klasse abgeleitet ist

def count_m_recursive(sentence): 
    return (sentence or 0) and ((sentence[0] == 'm') + count_m_recursive(sentence[1:])) 

Answer 4

Für den Spaß, können Sie die gesamte schreiben Ding als anonymer Lambda-Ausdruck wie folgt:

def make_funny_func(): 
    # wrapped the code with return clause to emphasize that it is 
    # anonymous ;) 
    return (
     # Y combinator 
     (lambda f: (lambda x: x(x))(lambda y: f(lambda a: y(y)(a)))) 
     # our function wrapped 
     (lambda count: 
      lambda s: 
       # return 1 + f(s[1:]) if the first character is 'm' 
       # 0 + f(s[1:]) otherwise. 
       (s[0] == 'm') + count(s[1:]) 
       # but do the thing before only if s is non-empty string 
       if s 
       # else return 0 
       else 0 
     ) 
    ) 

count_m_recursive = make_funny_func() 
print(count_m_recursive('mmmkay')) 

Peer pessure Abzeichen, wir kommen ;-)