Seite 1 von 1
Rekursive Funktion
Verfasst: Montag 26. Mai 2003, 14:16
von HarryH
Könnte mir mal bitte jemand verständlich erklären was eine rekursive Funktion ist. Was bedeutet es das sie sich selbst aufruft und wie?
Re: Rekursive Funktion
Verfasst: Montag 26. Mai 2003, 15:02
von joerg
HarryH hat geschrieben:Könnte mir mal bitte jemand verständlich erklären was eine rekursive Funktion ist. Was bedeutet es das sie sich selbst aufruft und wie?
Ein klassisches Beispiel ist hier die Fakultät. Sie läßt sich nämlich ausdrücken als fak(x) = x * fak(x-1) mit fak(1) = 1.
In Python kannst Du das ganze so schreiben:
Code: Alles auswählen
def fak(x):
if x > 1:
return x * fak(x-1)
else:
return 1
Du siehst, daß die Funktion sich selbst aufruft. Wichtig ist hier eine konkrete Abbruchbedingung. Bei zu vielen Rekursionen gibt nämlich Python sonst auf.
Um zu sehen, in welcher Reihenfolge das aufgerufen wird, kannst Du die Funktion noch gesprächig machen:
Code: Alles auswählen
def fak(x):
if x > 1:
print "%d *" % x,
return x * fak(x-1)
else:
print "1"
return 1
Probiere es aus!
Und wenn dir das viel zu lang ist, nimmst Du doch lieber
Code: Alles auswählen
def fak(x):
return reduce(lambda x,y:x*y, range(1,x+1) or (0,))
für die Fakultät.
Jörg
Verfasst: Montag 26. Mai 2003, 15:37
von Dookie
Hi HarryH,
auch Binärbäume sind ein Paradebeispiel für Rekursion. Schau Dir mal mein kleines Beispiel
http://python.sandtner.net/viewtopic.php?t=532 an, da wimmelts nur so von Rekursionen. Schon der Aufbau des Baumes aus einer Liste erfolgt rekursiv. Die Methoden zum durchlaufen des Baumes inorder(), preorder() und postorder() sind ebenfalls rekursiv.
Wichtig ist hier eine konkrete Abbruchbedingung. Bei zu vielen Rekursionen gibt nämlich Python sonst auf.
Zum glück terminiert Python bei zu tiefer Rekursion von selbst und sauber, wenn es Dir passiert, daß eine rekursive Funktion aus dem Ruder läuft, passierts bei anderen Programmiersprachen, daß bestenfalls das Programm abstürzt, schlimmstenfalls hängt sich der ganze Computer auf.
Gruß
Dookie
re
Verfasst: Montag 26. Mai 2003, 15:39
von HarryH
Vielen Dank! Das war schon sehr hilfreich!
Ich hätte da auch schon ein konkretes Beispiel:
Ich möchte auf einem Widget-Label immer die zuletzt erstellte Datei in einem bestimmten Verzeichnis angezeigen lassen, sobald eine neue hinzu kommt.
Geht das mit einer rekursiven Funktion?
Re: re
Verfasst: Montag 26. Mai 2003, 16:19
von Voges
HarryH hat geschrieben:Geht das mit einer rekursiven Funktion?
Nicht, wenn sich das nur einem Verzeichnis abspielt. Denn dann brauchst Du nur die Dateien dieses einen Verzeichnisses ermitteln und gucken, welche die neueste ist.
Wenn aber auch Unterverzeichnisse berücksichtigt werden sollen, Du also einen ganzen Verzeichnisbaum hast, dann wäre es sinnvoll, diesen Baum eben per rekursiver Funktion zu durchsuchen. Alternativ kannst Du aber dafür auch die Funktion os.path.walk() nutzen.
Jan
re
Verfasst: Dienstag 27. Mai 2003, 08:02
von HarryH
Vielen Dank für alle eure Beiträge!