13 Rekursive Algorithmen - Klasse Mathematik
13.1 Was ist eine Rekursion?
 
Der große Diktator
von Charles Chaplin
Einen ersten Eindruck davon, was man unter einer Rekursion versteht, vermittelt eine kurze Filmsequenz zu Beginn des Chaplin Filmes "Der große Dikatator". Zur Situation: eine Granate soll abgefeuert werden, verfehlt aber ihr Ziel, genauer sie fällt aus dem überdimensionalen Kanonenrohr. Der Zünder soll nun untersucht werden. Der höchstrangige Offizier übernimmt die Aufgabe. Die Aufgabe heißt: Zünder untersuchen.
Rekursions-tiefe0 Man könnte das Erledigen der Aufgabe mit einem Methodenaufruf identifizieren. Die Methode heißt: zünderUntersuchen(befehlsempfänger). An der Signatur erkennt man schon, dass die Aufgabe an den nächst Rangtieferen übergeben wird.
Rekursions-tiefe1 Der erste Offizier gibt den Befehl an den nächsten Untergebenen: Zünder untersuchen.
Rekursions-tiefe2 Dieser führt die Aufforderung dadurch aus, dass er seinerseits den Befehl "Zünder untersuchen" gibt, jetzt allerdings dem ihm Unterstellten. Wir sehen das "Zünder untersuchen" besteht darin "Zünder untersuchen" zu befehlen. Oder in der Sprache der Informatik: Die Methode zünderUntersuchen(..) ruft sich selbst auf - allerdings mit verändertem Parameterwert. Solche Methoden nennen wir rekursiv.
Rekursions-tiefe3

 

Auch dieser Soldat führt den Befehl "Zünder untersuchen"  dadurch aus, dass er seinerseits den Befehl "Zünder untersuchen" weitergibt, natürlich wieder an jemanden, der einen Rang tiefer ist.
Rekursions-tiefe4 = Basisfall Der Befehl erreicht den rangtiefsten Soldaten, dargestellt von Charles Chaplin. Auch er versuch den Befehl dadurch auszuführen, dass er den Befehl "Zünder untersuchen" aussprechen will. Es ist aber kein Adressat für den Befehl mehr da, er muss den Befehl jetzt 'echt' ausführen. ("Den letzten beißen die H..."). Der Informatiker sagt: Der rekursive Abstieg ist beendet, der "Basisfall" der Rekursion ist eingetreten. Wer Charles Chaplin kennt, weiß dass jetzt Szenen folgen, die die Tragik, die in dieser Szene liegt, durch Komik weiter auf die Spitze treibt. Eine Szene allerdings 'fehlt' in dem Film, nämlich, der rekursive Aufstieg. Chaplin müsste seinem 'Vordermann' mitteilen "Zünder untersuchen" ausgeführt. Sein Vordermann gäbe dann die gleiche Meldung an seinen Vordermann weiter und so fort, bis die Meldung den ersten Aufrufer erreicht. Um sich den rekursiven Aufstieg zu veranschaulichen, braucht man sich die gleiche Bildfolge, jetzt nur in umgekehrter Reichenfolge, also von unten noch oben abgespielt vorstellen.
   
zu 13.2 Rekursive Methoden in Java
zur Startseite www.pohlig.de  (C) MPohlig 2004