Rekursion, fürsorgliche Browser, vorherbestimmte Zufallszahlen
oder
Wie man den Stack verschont

Angehörige der erheblich jüngeren Zunft der Computerprogammierer verbinden mit dem Begriff rekursiv in der Regel1 rekursive Funktionen. Eine rekursive Funktion ist eine, die sich unter bestimmten Bedingungen selbst aufruft; die einfachste (und wenig sinnvolle) rekursive Funktion wäre:

                        
function do_something () {
    do_something();
}
                        

Für sich genommen ist diese Funktion harmlos. Sie mit do_something(); aufzurufen wäre allerdings eine höchst effiziente Methode, den Computer (im Fall einer interpretierten Sprache nicht den ganzen Computer, aber immerhin die Laufzeitumgebung oder die Sandbox) lahmzulegen. Der Grund für dieses ungebührliche Betragen ist darin zu suchen, daß die aufgerufene Funktion do_something() wiederum do_something() aufruft, diese do_something() usw. Das Aufrufen der Funktion im unendlichen Regress wäre für sich genommen noch gar nicht so schlimm2 - das größte Problem besteht darin, daß vor lauter Funktionsaufrufen nachfolgender Code niemals berücksichtigt wird. Zur Verdeutlichung dieser Tatsache kann man der Interpunktion innerhalb der Notation ausnahmsweise eine Bedeutung zumessen, statt sie als lästigen Formalismus aufzufassen - Semikolon und schließende geschweifte Klammer werden niemals erreicht:

                        
function do_something () {
    do_something();
}
                        

Sprachen, die auf die Verwendung dieser Zeichen verzichten (wie Python oder Ruby), unterliegen natürlich der gleichen Problematik, auch wenn man es nicht so deutlich sieht.
Moderne Betriebssysteme haben normalerweise Schutzmechanismen, die verhindern, daß ein in einer Endlosschleife gefangenes Programm alle anderen mit in die Tiefe reißt; trotzdem sind Endlosschleifen natürlich unbedingt zu vermeiden.
Der entscheidende Punkt in der Definition einer rekursiven Funktion, der eine Katastrophe in ein nützliches Werkzeug verwandeln kann, lautet unter bestimmten Bedingungen. Folgender Code ist leidlich sinnvoll (und zum Ausprobieren freigegeben):

                        
function count_down (number) {
    console.log(number);
    if ( number > 0 )
        count_down(--number);
}

count_down(10);
                        

Genau das gleiche Ergebnis liefet auch Folgendes:

                        
function reverse_count_down (number, limit) {
    if ( number < limit )
        reverse_count_down((number + 1), limit);
    console.log(number);
}

reverse_count_down(0, 10);
                        

Die Funktion count_down() verfährt nach dem Schema 1) Zeige die übergebene Zahl 2) Wenn die übergebene Zahl größer als 0 ist, rufe die Funktion erneut mit um 1 verminderter Zahl auf
Das Schema von reverse_count_down() ist 1) Wenn der übergebene Parameter number kleiner als der übergebene Parameter limit ist, rufe die Funktion erneut auf, wobei anstatt number eine um 1 vergrößerte Zahl zu übergeben ist. 2) Zeige Parameter number
Obwohl count_down() abwärts und reverse_count_down() aufwärts zählt, zeigen beide das gleiche Resultat. Das liegt daran, daß reverse_count_down(), solange die Rekursionsbedingung erfüllt ist, zuerst sich selbst erneut aufruft, bevor die Bildschirmausgabe mit console.log(number); veranlaßt wird. Es ist nicht obligatorisch, aber typisch für die Verwendung rekursiver Funktionen, Ergebnisse erst nach Erreichen des letzten Rechenschritts (und dann in umgekehrter Reihenfolge) zu präsentieren.

Beide Varianten sind funktionstüchtig, aber nicht als ideal anzusehen. Dafür gibt es einen eher maschinensprachlichen und einen eher logischen Grund. Erster besteht darin, daß die Verwendung einer Funktion vermeidbar ist und das gleiche Ergebnis mit vergleichbarem Programmieraufwand3 durch eine while - Schleife zu erzielen wäre:

                        
var number = 10;
while ( number >= 0 ) {
    console.log(number--);
}
                        

Übersetzt bedeutet das 1) Belege Variable number mit dem Wert 10. 2) Solange number größer oder gleich 0 ist, zeige number und vermindere number nach dem Zeigen um 1

Der zweite Grund besteht darin, daß die Häufigkeit der Wiederholung schon vor der Ausführung feststeht und zudem numerisch angegeben werden kann. Für solche Fälle empfiehlt sich eine for - Schleife, etwa:

                        
var number;
for ( number = 10; number >= 0; number-- )
    console.log(number);
                        

Im Klartext: 1) Definiere Variable number. [Bei manchen Programmiersprachen unnötig] 2) Belege number mit dem Anfangswert 10. 3) Prüfe, ob number größer oder gleich 0 ist. Falls nein: 4) Beende [und fahre mit 7), falls existent, fort]. Falls ja: 4) Zeige number. 5) Vermindere number um 1. 6) Fahre mit 3) fort.
In dieser Übersetzung wird deutlich, daß die for - Schleife viel eher der Denkweise eines Computers entspricht; zudem erleichert die Schreibweise dem Programmierer das Aufspüren von Endlosschleifen.

Läßt man die andersartigen internen Behandlungen einmal außen vor, worin besteht dann der Unterschied zwischen einer while - Schleife und einer rekursiven Funktion? In der tat ist er nicht groß, und ich möchte hier while - Schleifen und do-while - Schleifen als inhaltlich rekursiv bezeichnen, denn es überwiegt die gemeinsame Eigenschaft, daß die Steuerung der Abbruch- bzw. Fortführungsbedingung innerhalb der Schleife liegt.
Ein wesentlicher Unterschied zwischen rekursiven Funktionen und while - Schleifen besteht in der Ausführungsreihenfolge und auch darin, daß in einer while - Schleife in der Fortführungsbedingung immer die gleiche Variable verwendet wird (deren Wert sich innerhalb der Schleife ändert), wogegen die rekursive Funktion bei jedem Aufruf neuen Speicher benutzt. In den meisten Fällen spricht der sparsamere Umgang mit Ressourcen eher für die while - Schleife, aber manchmal ist die Verwendung frischen Speichers auch sehr praktisch, da die alten Werte eines vorangegangenen Funktionsaufrufes erhalten bleiben:

                        
var main_folder = { FOLDER_A: { file_a: "important file",
    file_b: "stupid file" }, file_c: "some data",
    FOLDER_B: { FOLDER_C: { file_d: "lost & found" } },
    file_e: "empty file",
    FOLDER_D: { file_f: "important file",
    FOLDER_E: { FOLDER_F: { FOLDER_G: { file_g: "passwords",
    file_h: "not secret" } } }, file_i: "empty file" } };
function explore (folder, level) {
    var i, file_name, ty, property;
    for ( property in folder ) {
        file_name = "";
        ty = ((typeof folder[property]).toString() == "object") ? 1 : 0;
        for ( i = 0; i < level; i++ )
            file_name += "&nbsp;"
        file_name += property;
        file_name += (ty) ? "" : " <span style='color: gray'>["
                + folder[property] + "]</span>";
        console.log( file_name );
        if ( ty )
            explore(folder[property], (level + 5));
    }
}

explore(main_folder, 0);
                        

Hier wird das Auslesen eines Ordners einschließlich sämtlicher Unterordner simuliert (da bei Ausführung im Browser Dateizugriffe aus Sicherheitsgründen unterbunden werden, ist in main_folder eine fiktive Ordnerstruktur hinterlegt). Die Funktionsweise von explore() ist: 1) Ermittle alle Dateien in folder. 2) Für jede Datei aus folder: 2a) Stelle fest, ob die aktuelle Datei selbst ein Ordner ist. Falls nein: 2b) Ermittle Dateiinformationen. 2c) Gib Dateinamen und eventuelle Dateiinformationen um level Leerzeichen eingerückt aus. 2d) Falls bei 2a) die Antwort 'ja' ist: 2e) Rufe explore() mit der aktuellen Datei und erhöhtem level auf.
Auch das wäre ohne Verwendung einer rekursiven Funktion durchaus möglich, erforderte aber mehr Schreib- und Denkaufwand.

Am stärksten im Ruf, etwas ganz besonderes leisten zu können, stehen rekursive Funktionen dann, wenn sie über einen Rückgabewert verfügen. Manchmal erscheint der Zusammenhang zwischen Code und Ergebnis wie pure Magie. Jürgen Wolf4 hat in einem seiner Bücher5 geschrieben: Mit Rekursionen haben Sie die Möglichkeit, den Computer zu etwas zu bewegen, was ihn intelligenter erscheinen lässt. Die durch den Tonfall zum Ausdruck gebrachte Skeptis gilt sicherlich nicht dem, was ich weiter oben als inhaltlich rekursiv bezeichnet habe (also der Steuerung des Programmablaufs durch im Inneren ermittelte Werte), sondern der Neigung, das Wesentliche zugunsten des Staunens über die vermeintliche Intelligenz der Maschine zu opfern.
Unabhängig davon, wann genau die Verwendung rekursiver Funktionen empfehlenswert ist, möchte ich Ihnen zum Abschluß dieses Kapitels die Lösung einer von Simon Singh berichteten Aufgabe6 vorstellen, die mithilfe einer rekursiven Funktion mit sehr wenig Code auskommt:

Auf einem Fußballplatz befinden sich die 22 Spieler beider Mannschaften und der Schiedsrichter. Wie groß ist die Wahrscheinlichkeit, daß zwei von ihnen am selben Tag Geburtstag haben?

Der spontane Einfall irgendwas mit 23 durch 365 (anders ausgedrückt: Es ist eher unwahrscheinlich) führt nicht zum Ziel. Da an dieser Stelle sowieso die ganze Zeit über Computer geredet wird, kann das Problem getrost kleinschrittig angegangen und das Zusammenrechnen der Einzelschritte später der Maschine überlassen werden.
Das Ergebnis wird ein Bruch zwischen 0 und 1 sein, also irgendetwas wie 1/10 (entspricht 10%) oder 2/5 (entspricht 40%). Zu allererst gewöhne man sich an den Gedanken, statt der Wahrscheinlichkeit für gemeinsame Geburtstage die Wahrscheinlichkeit für ein Ausbleiben der Übereinstimmung zu berechnen und dieses am Ende von 1 abzuziehen. Mathematisch interessierte Menschen, denen das nicht unmittelbar einleuchtet, können die Grundlagen hier nachlesen. Man stelle sich die Personen durchnumeriert vor und betrachte die erste. An irgendeinem Tag muß Nummer 1 Geburtstag haben; wenn es Ihrer Vorstellung hilft, können Sie sich den ersten Januar genauso gut wie jeden anderen Tag vorstellen. Nun geht es darum, wie groß die Wahrscheinlichkeit ist, daß keiner der übrigen 22 am selben Tag Geburtstag hat. Unter den Voraussetzungen, daß Geburtstage unter Fußballern gleichmäßig verteilt sind und es sich nicht um ein Schaltjahr handelt, beträgt diese Wahrscheinlichkeit 1-(22/365). Falls eine Übereinstimmung gefunden wurde, ist die ursprüngliche Frage beantwortet; falls nicht, erhält Nummer 2 eine Chance. Nummer 2 kann nicht am selben Tag wie Nummer 1 Geburtstag haben, sonst wäre das im letzten Schritt schon aufgefallen, aber an irgendeinem Tag muß auch Nummer 2 Geburtstag haben (meinetwegen dem zweiten Januar). Es verbleiben 21 Anwesende, deren Geburtstage sich auf 364 Tage verteilen (ein Tag wurde ja schon für Nummer 1 verbraucht); also muß das bisherige Zwischenergebnis mit 1-(21/364) multipliziert werden. So verfährt man weiter, bis nur noch eine Person übrig bleibt: Für diese gibt es keinen potentiellen Partner mehr, also kann die Wahrscheinlichkeit auch nicht weiter verändert werden.

                        
function football_birthday (players, days) {
    if ( players == 1 )
        return 1;
    return ((1 - (--players / days)) * football_birthday(players, --days));
}

var probability = 1 - football_birthday(23, 365);
console.log( Math.round(probability * 1000) / 10 + "%" );
                        

Die Vorgabe 22 Spieler und der Schiedsrichter ist geschickt gewählt, denn so lohnt es sich gerade, auf eine Geburtstagsübereinstimmung zu wetten; ohne den Schiedsrichter wäre es eher empfehlenswert, auf ein Ausbleiben derselben zu setzen. Die Pfiffigkeit dieses Rätsels ist aber nicht der einzige Grund, warum ich gerade dieses Beispiel ausgewählt habe. Viele Tutorials demonstrieren rekursive Funktionen anhand von Beispielen, die rechnerisch wesentlich einfacher zu lösen wären; im vorliegenden Fall ist die vorgestellte Lösung jedoch wirklich praxisnah7.

Falls Sie jetzt vom Zauber rekursiver Funktionen gefangengenommen worden sind, empfehle ich Ihnen das Studium klassischer Beispiele wie dem Damenproblem oder den Türmen von Hanoi.

1 Auch diese Sichtweise ist zu einengend. Unix-Programmierer beispielsweise werden möglicherweise eher an den Auftrag Führe den genannten Befehl auch bei allen Dateien in Unterordnern und in deren Unterordnern aus denken.  ↑ 

2 In der Praxis ist es doch schlimm. Als Ende der 60er Jahre Anstrengungen unternommen wurden, den berüchtigten Spaghetticode durch leichter les- und wartbare Notationsweisen zu ersetzen, geschah das um den Preis, daß Computer sich bei jedem Funktionsaufruf den 'Absprungpunkt' merken müssen, um später dahin zurückzukehren. Angesichts des riesigen Speichervorrats moderner Computer fällt das in den meisten Fällen nicht ins Gewicht, aber ein unendlich oft wiederholtes Springen füllt irgendwann auch den größten Speicher.  ↑ 

3 Intern kennen Computer keine Funktionen (und rekursive schon gar nicht), sondern nur die unter Programmierern in Ungnade gefallenen Sprungbefehle. Falls die verwendete Programmiersprache die ungeliebten Sprungbefehle gestattet, ist es also immer möglich, (rekursive) Funktionen zu umgehen. Aber auch ohne Sprungbefehle bietet jede Programmiersprache Möglichkeiten, alles, was durch den Einsatz rekursiver Funktionen möglich ist, umzuformulieren (allerdings unter Verwendung jeweils unterschiedlicher Techniken). Wenn auch minimale Verbesserungen im Bereich der Ausführungsgeschwindigkeit und des Speicherverbrauchs ins Gewicht fallen, sollte man genau das tun. Die eventuellen Vorteile rekursiver Funktionen liegen eher in ihrer Lesbarkeit und ihrer Flexibilität begründet.  ↑ 

4 Wenn Sie an Programmierung wirklich interessiert sind, kann ich Ihnen die Bücher von Jürgen Wolf wärmstens und uneingeschränkt empfehlen.  ↑ 

5 Jürgen Wolf, C von A bis Z, Galileo Computing, ISBN 978-3-8362-1411-7  ↑ 

6 Simon Singh, Fermats letzter Satz, ISBN 3-423-33052-X
In diesem Buch wird die Aufgabe unter dem Aspekt mathematischer Beweisführung, nicht unter algorithmischen Gesichtspunkten vorgestellt. Bezüglich der historischen Ursprünge dieses Rätsels siehe Wikipedia: Geburtstagsparadoxon.  ↑ 

7 Es gilt die Faustregel Löse eine Aufgabe niemals algorithmisch, wenn eine rechnerische Lösung möglich ist, es sei denn, es liegt ein triftiger Grund vor. Dieser triftige Grund ist hier gegeben; eine Umformung des Ausgangsterms führt letztlich zu

1     -      343²³ * 342!
__________

      365!

Sie können diesen Ausdruck gern in Ihren Taschenrechner eingeben um zu verstehen, was ich meine.  ↑