Rekursive Funktion

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
HarryH
User
Beiträge: 266
Registriert: Freitag 23. Mai 2003, 09:08
Wohnort: Deutschland

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? :?:
joerg
User
Beiträge: 188
Registriert: Samstag 17. August 2002, 17:48
Wohnort: Berlin
Kontaktdaten:

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
Dookie
Python-Forum Veteran
Beiträge: 2010
Registriert: Freitag 11. Oktober 2002, 18:00
Wohnort: Salzburg
Kontaktdaten:

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
HarryH
User
Beiträge: 266
Registriert: Freitag 23. Mai 2003, 09:08
Wohnort: Deutschland

Vielen Dank! Das war schon sehr hilfreich! :D

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?
Voges
User
Beiträge: 564
Registriert: Dienstag 6. August 2002, 14:52
Wohnort: Region Hannover

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
HarryH
User
Beiträge: 266
Registriert: Freitag 23. Mai 2003, 09:08
Wohnort: Deutschland

Vielen Dank für alle eure Beiträge!
Antworten