Obwohl ich früher über die Schleifen sagte, dass sie einer der Meilensteine des Programmierens sind, ist es in der Tat möglich, Programme ohne eine explizite Schleifenkonstruktion zu erzeugen. Einige Srachen, so wie Lisp, haben tatsächlich keine explizite Schleifenkonstruktion wie FOR, WHILE, usw. Anstatt dessen verwenden sie eine als Rekursion bekannte Technik. Diese erweist sich für einige Problemtypen als eine sehr leistungsfähige Technik, so dass wir jetzt einen Blick darauf werfen werden.
Rekursion bedeutet einfach das Anwenden einer Funktion als ein Teil der Definition der gleichen Funktion. So kann man sagen , dass die Definition von GNU (die Quelle von vielen freier Software) rekursiv ist, weil GNU für 'GNU ist nicht Unix' steht. Somit ist GNU ein Teil der Definition von GNU!
Der Schlüssel, damit dies funktioniert, ist, dass dort eine Abbruchbedingung sein muss, so dass die Funktion bei einem bestimmten Punkt auf eine nicht-rekursive Lösung abzweigt. (Bei der GNU-Definition versagt dieser Test und sie bleibt in einer unendlichen Schleife stecken).
Lass uns ein einfaches Beispiel betrachten. Die mathematische Funktion der Fakultät ist definiert als das Produkt aller Zahlen bis zu und einschließlich des Argumentes, und die Fakultät von 1 ist 1. Wenn wir darüber nachdenken, so sehen wir, dass es einen anderen Weg gibt, dies auszudrücken und dass die Fakultät von N gleich dem N-fachen der Fakultät von (N-1) ist.
Also:
1! = 1
2! = 1 x 2 = 2
3! = 1 x 2 x 3 = 2! x 3 = 6
N! = 1 x 2 x 3 x .... (N-2) x (N-1) x N = (N-1)! x N
So können wir das in Python ausdrücken:
def facultaet(n):
if n == 1:
return 1
else:
return n * facultaet(n-1)
Weil wir jetzt jedesmal N dekrementieren und auf N gleich 1 testen, müsste die Funktion vollständig sein.
Das Erstellen der Fakultätsfunktion ohne Rekursion hat ein bisschen mehr Code zur Folge. Du musst eine Liste mit allen Zahlen von 1 bis N erzeugen und dann mittels einer Schleife über die Liste gehen und das momentane Ergebnis mit jedem Listenbestandteil multiplizieren. Versuche es als eine Übung und vergleiche das Ergebnis mit obiger Funktion.
Der andere Bereich, wo die Rekursion sehr nützlich ist, ist in der Bearbeitung von Listen. Zur Ausstattung mit einer Überprüfung, ob eine Liste leer ist, und der Generierung einer Liste ohne ihr erstes Element, können wir einfach eine Rekursion verwenden.
Betrachte den einfachen Fall des Ausgebens eines jeden Elementes einer Liste von Strings unter Verwendung der Funktion printList:
def printList(L):
if L:
print L[0]
# for [1:] - siehe 'slicing' im Python-Referenzhandbuch
printList(L[1:])
Wenn L wahr ist - nicht leer - drucken wir das erste Element und dann bearbeiten wir den Rest der Liste.
Für eine einfache Liste ist es mit der Benutzung einer einfache Schleife eine triviale Sache. Aber betrachte, was geschieht, wenn die Liste komplex ist und andere Listen in sich birgt. Wenn wir überprüfen können, ob ein Listenbestandteil eine Liste ist, dann können wir printList() rekursiv aufrufen. Wenn nicht, drucken wir es einfach. Versuchen wir es:
def printList(L):
# wenn sie leer ist, tue nichts
if not L: return
# ist es eine Liste, rufe printList bei ihrem ersten Element
if type(L[0]) == type([]):
printList(L[0])
else: #keine Liste, also drucke
print L[0]
# bearbeite jetzt den rest von L
printList(L[1:])
Wenn du versuchst, hier eine konventionelle Schleifenkonstruktion zu verwenden, wirst du es als sehr schwierig empfinden. Eine Rekursion macht eine sehr komplexe Aufgabe vergleichsweise einfach.
Es gibt einen Haken (wie immer!). Die Rekursion von langen Datenstrukturen neigt zu einem großen Verzehr von Speicherplatz, so dass, wenn du wenig Speicherplatz oder eine große Datenmenge zu bearbeiten hast, ein komplexer konventioneller Code sicherer sein kann.
OK, machen wir nun einen weiteren Sprung ins Unbekannte, indem wir die objektorientierte Programmierung (OOP) einführen.
Im Falle von Fragen und Anmerkungen sende eine Nachricht auf
Englisch an alan.gauld@yahoo.co.uk
oder auf Deutsch an bup.schaefer@freenet.de