Hi polynux,
bin zwar nicht milan, aber auch relativ fit in Python und allgemein im Programmieren
Leider werden in Büchern sehr oft wenig brauchbare Beispiele zur Rekursion gezeigt, die sich oft besser durch Iteration lösen lassen, wie auch Dein Beispiel mit der Quersumme. Durch Recursion werden die Beispiele dann oft komplizierter als erforderlich.
Eine Ausnahme bildet das die Fakultätsfunktion, hier sind sowohl die rekursive als auch die iterative Variante recht klar zu lesen.
Ich würde die rekursive Falkultätsfunktion allerdings so formulieren:
Code: Alles auswählen
def fakul2(n):
if n > 2:
return n * fakul2(n-1)
else:
return n
So braucht nur eine Bedingung geprüft zu werden und für 0 und 1 ergibt sich auch das richtige Ergebnis.
Rekursive Methoden/Funktionen bieten sich besonders an bei Datenstrukturen die ihrerseits schon rekursiv definiert sind, wie z.B. bei Bäumen. Ich hab hier mal ein kleines Beispiel gecodet:
Code: Alles auswählen
class node(object):
""" Klasse für eine einfache Baumstruktur """
__slots__ = ["left","right","value"]
def __init__(self, value):
""" Neuen Knoten des Baumes initialisieren """
self.left = None
self.right = None
self.value = value
def insert(self, value):
""" Wert in Baumstruktur einfügen """
if value < self.value:
if self.left:
self.left.insert(value)
else:
self.left = node(value)
else:
if self.right:
self.right.insert(value)
else:
self.right = node(value)
def print_tree(self, indent=0):
""" Baumstruktur darstellen, die Einrückung stellt die Tiefe im Baum dar """
if self.left:
self.left.print_tree(indent+1)
print (" "*indent)+self.value
if self.right:
self.right.print_tree(indent+1)
def inorder(self):
""" Baum "inorder" als Liste zurückgeben """
result = [self.value]
if self.left:
result = self.left.inorder()+result
if self.right:
result = result+self.right.inorder()
return result
def preorder(self):
""" Baum "preorder" als Liste zurückgeben """
result = [self.value]
if self.left:
result = result+self.left.preorder()
if self.right:
result = result+self.right.preorder()
return result
def postorder(self):
""" Baum "postorder" als Liste zurückgeben """
if self.left:
result = self.left.postorder()
else:
result = []
if self.right:
result += self.right.postorder()
result.append(self.value)
return result
if __name__ == "__main__":
tree = node("d")
tree.insert("c")
tree.insert("f")
tree.insert("a")
tree.insert("b")
tree.insert("e")
tree.insert("g")
tree.print_tree()
print tree.inorder()
print tree.preorder()
print tree.postorder()
Ausser der __init__ Methode sind alle anderen Methoden rekursiv. Diese Methoden iterativ zu realisieren stellt selbst bei dieser einfachen Struktur schon einen relativ grossen Aufwand dar.
Gruß
Dookie
Oberon stinkt!). Angefangen Rekursion zu kapieren hab ich dann, als ich eine Mischung aus Rekursion und Iteration zusammenbauen musste: die Aufgabe war eine Liste umzudrehen, also eine Funktion reverse zu schreiben. Eigentlich eine triviale Sache, aber die Bedingung war, alle Sublisten auch umzudrehen. Und genau da hats dann gegriffen: durch die Iteration hattest du den nötigen Überblick, was in einem Arbeitsschritt passieren muss und dann ist auch automatisch klar, was passieren muss, wenn man eine Ebene tiefer geht.