Rekursive Funktionen

Zum Abschluss der Funktionen in Python noch eine Besonderheit, mit der professionelle Programmierer regelmäßig zu tun haben: sogenannte rekursive Funktionen. Was ist das?

Rekursive Funktionen sind Funktionen, die sich selbst aufrufen.

Wie? Sie rufen sich selbst auf? Wie soll denn das gehen?

Das geht sehr einfach – aber es gibt ein paar Dinge zu beachten –, und es ist nicht immer ganz leicht, sich klarzuwerden, was da genau passiert.

Hier ist eine einfache Funktion, die sich selbst aufruft:

Die Funktion rekursiv wird mit dem Übergabewert x aufgerufen. Nehmen wir an, x ist beim Aufruf 1. Nun wird x ausgegeben (also 1), dann wird die Funktion selbst (rekursiv(x+1)) erneut aufgerufen, allerdings diesmal mit dem Wert 2. Die Funktion rekursiv ruft sich also selbst auf und ist damit nicht beendet, sondern der nächste Aufruf gibt eine 2 aus, ruft sich dann wieder selbst auf, diesmal mit dem Wert 3 usw. … usw. …

Die Funktion ist also ein Zähler, der immer eine Zahl höher zählt und sich selbst dann weiter aufruft … du siehst wahrscheinlich schon, was das Problem dabei ist. Die Funktion wird nie beendet – stattdessen ruft sie sich bis ins Unendliche immer wieder selbst auf …

Bis ins Unendliche? Wie oft kann eine Funktion sich selbst aufrufen, ohne dass die Programm-Engine ein Problem bekommt? Denn sie muss sich ja schließlich immer »merken«, wo sie gerade ist – welche Funktion gerade welche aufgerufen hat … und das kann nicht unendlich lange gut gehen.

Probiere es einmal aus: Gib die Funktion von oben ein, und füge am Ende noch einen Aufruf der Funktion hinzu:

def rekursiv(x):
    print x
    rekursiv(x+1)

rekursiv(1)

Was passiert? Der Zähler zählt hoch bis 1.000 – dann kann das Programm nicht mehr und bricht ab:

RuntimeError: maximum recursion depth exceeded

Also: Laufzeitfehler. Die maximale Rekursionstiefe wurde überschritten. Irgendwann reicht es dem Python-Interpreter, und er hat »keine Lust mehr«, sich ewig selbst aufzurufen und sich dabei stets zu merken, auf welcher Ebene er sich jetzt befindet – konkret gibt es irgendwann ernste Speicherprobleme, und der Computer würde »abstürzen«, wenn er nicht irgendwann abbricht.

Wie lösen wir das Problem?

Indem wir eine Bedingung einbauen, wann weiter aufgerufen und wann abgebrochen wird. Nehmen wir an, der Zähler soll bis 100 zählen – die Funktion soll sich also nur so lange selbst aufrufen, bis die 100 erreicht ist.

def rekursiv(x):
    print x
    if x<100:
        rekursiv(x+1)

rekursiv(1)

Schon besser: Jetzt läuft das Programm schnell durch und zählt von 1 bis 100.

Natürlich wollte ich mit diesem Programm nur zeigen, was Rekursion ist. In der Praxis würde man so einen Zähler wohl anders programmieren. Aber es gibt Aufgaben, bei denen Rekursion durchaus sinnvoll ist. Manche Probleme lassen sich sogar nur durch Rekursion angemessen lösen – oder zumindest viel einfacher.

Aufgabe

Eine neue Aufgabe: Schreibe eine rekursive Funktion, die die mathematische Fakultät einer Zahl berechnet.

Was ist die Fakultät?

Fakultät bedeutet, dass eine Zahl mit allen positiven ganzen Zahlen über 0, die kleiner sind als sie, multipliziert wird. Die Fakultät von 5 ist somit 5 × 4 × 3 × 2 × 1 = 120.

Klar, man könnte das in Python auch mit einer Zählerschleife lösen – aber die rekursive Version ist elegant und etwas raffinierter.

def fakultaet(x):
    if x == 1:
        return 1
    else:
        return (x * fakultaet(x-1))

Verstehst du, wie das funktioniert? Man muss sich beim Denken ein bisschen verrenken. Nehmen wir an, die Funktion wird mit dem Wert 3 aufgerufen. Da 3 nicht gleich 1 ist, wird das if-Kommando übersprungen. Jetzt liefert die Funktion mit return etwas zurück, aber sie endet noch nicht, denn für die Ermittlung des Rückgabewertes muss die Funktion sich erst einmal selbst aufrufen, diesmal mit der 2 als Wert. Dort passiert wieder dasselbe, die Funktion ruft sich beim return wiederum selbst auf, und dann startet sie mit der 1 als Wert. Hier liefert sie nun einfach die 1 zurück und ruft sich nicht mehr selbst auf. Damit wird der zweite Aufruf auch beendet (1 × 2) und der dritte ebenso (2 × 3) – und die Funktion kann endlich beendet werden, das Ergebnis 6 kommt zurück.

Um die Funktion mit verschiedenen Werten auszuprobieren, kannst du die folgenden Zeilen dazuschreiben:

f = input("Zahl eingeben:")
print "Die Fakultät von",f,"ist",fakultaet(f)

Vorsicht: Die Ergebnisse werden schnell sehr hoch.

[+]  Für Mathe-Profis: Wozu braucht man die Fakultätsberechnung eigentlich?

Die Fakultät spielt eine wichtige Rolle in der Wahrscheinlichkeitsrechnung. Man kann hiermit zum Beispiel die möglichen Anordnungen einer Anzahl von Dingen berechnen. Wenn ich 5 Personen habe, gibt es 120 (Fakultät von 5) Reihenfolgen, in denen sie sich auf eine Bank setzen können. 10 Personen haben bereits über dreieinhalb Millionen Möglichkeiten, wie sie sich auf der Bank anordnen können. Unglaublich – aber beweisbar wahr!