Iteration in Rekursion umwandeln

Ich möchte überprüfen, ob der eingegebene string Benutzer einen ausgeglichenen Betrag von ( und )

Ex. ()( Ist nicht ausgeglichen (()) ausgeglichen

 def check(string): counter=0 string=string.replace(" ","") if string[0] is "(": for x in string: if x is "(": counter=counter+1 elif x is ")": counter=counter-1 if counter1 is 0: print("Balanced") else: print("Unbalanced") else: print ("Unbalanced") 

So funktioniert das, aber wie löst ich dieses Problem mit Rekursion? Ich versuche zu denken, wie ich eine Variable verringern kann jedes Mal, wenn ich es rekursiv nenne und sobald es 0 ist, stop.s

2 Solutions collect form web for “Iteration in Rekursion umwandeln”

Eine direkte, äquivalente Umwandlung des Algorithmus würde so aussehen:

 def check(string, counter=0): if not string: return "Balanced" if counter == 0 else "Unbalanced" elif counter < 0: return "Unbalanced" elif string[0] == "(": return check(string[1:], counter+1) elif string[0] == ")": return check(string[1:], counter-1) else: return check(string[1:], counter) 

Benutze es so:

 check("(())") => "Balanced" check(")(") => "Unbalanced" 

Beachten Sie, dass der obige Algorithmus Fälle berücksichtigt, in denen die schließende Klammer vor der entsprechenden Öffnungsklammer erscheint, dank der elif counter < 0 Bedingung – und damit ein Problem zu beheben, das im ursprünglichen Code vorhanden war.

 >>> def check(mystr, barometer=0): ... if not mystr: ... return barometer ... elif mystr[0] == "(": ... return check(mystr[1:], barometer+1) ... elif mystr[0] == ")": ... return check(mystr[1:], barometer-1) ... else: ... return check(mystr[1:], barometer) ... >>> for s in ["()", "(()", "(())", "()()"]: print(s, check(s)) ... () 0 (() 1 (()) 0 ()() 0 

0 bedeutet, dass du richtig ausgeglichen bist Alles andere bedeutet, dass du nicht ausgeglichen bist

  • Python-Funktion kehrt nach Rekursion nicht zurück
  • Merkwürdiges Rekursionsverhalten in Python
  • Was ist die maximale Rekursionstiefe in Python und wie man es erhöht?
  • Lösen von vollständig versteckten Ausdrücken mit Rekursion
  • Trennungsliste mit Rekursion
  • Rekursive Funktion, die keine zurückgibt?
  • Ist diese Funktion rekursiv, obwohl sie sich nicht nennt?
  • Notwendigkeit, Pyramiden-Dreieck auf Python neu zu erstellen
  • Python-Rekursions- und return-Anweisungen
  • Zählen der Rekursion in einem Python-Programm!
  • Python recursion return Keine Typ
  • Python ist die beste Programmiersprache der Welt.