In Kapitel 9 wurde die Berechnung der Fakultät als Beispiel für die Einführung von Methoden benutzt. Die eigentliche Berechnung erfolgte damals mit Hilfe einer Schleife. Die Berechnung der Fakultät lässt sich jedoch auch anders auffassen: Fakultät von 20 ist nichts anderes als 20- mal Fakultät von 19, Fakultät von 19 ist 19-mal Fakultät von 18, usw. Eine solche Definition setzt allerdings voraus, dass man mindestens einen konkreten Wert der Fakultät kennt (z.B. ist 1!=1). Zusammengefasst mit der Abkürzung fak für Fakultät gilt also $$fak(n)=n\cdot fak(n-1)$$ und $$fak(1)=1.$$
Eine solche Definition einer Funktion bezeichnet man als rekursiv („rückbezüglich“). Viele Programmiersprachen erlauben die unmittelbare Umsetzung einer solchen Funktionsdefinition. Bei speziellen Sprachen wie PROLOG gibt es überhaupt keine Schleifen, diese müssen dann immer durch rekursive Funktionen nachgebildet werden.
// Anfang Methoden long fak(int n) { if(n==1) // Abbruchbedingung der Rekursion return 1; else return n*fak(n-1); // Wenn n>1 ist, wird die Funktion erneut } // aufgerufen // Anfang Ereignisprozeduren public void jButton1_ActionPerformed(ActionEvent evt) { //Einlesen der Zahl: int zahl = Integer.parseInt(jTextField1.getText()); long fakultaet; //Rufe Funktion auf: fakultaet = fak(zahl); //Ausgabe: jTextField2.setText(Long.toString(fakultaet)); } // Ende Ereignisprozeduren
Die zugehörige grafische Oberfläche:
Das nebenstehende Diagramm zeigt den Ablauf der rekursiven Aufrufe für n=3. Jede Methode ruft rekursiv sich selbst als „Unterprogramm“ auf, ist selbst aber noch nicht abgeschlossen (Pfeile abwärts). Die Sache endet, wenn fak(1) aufgerufen wird. Jetzt wird der konkrete Wert 1 zurückgegeben, fak(1) ist beendet. Nun kann auch fak(2) fertig rechnen und wird beendet, usw. (Pfeile aufwärts).
Dabei wird ein Problem der Rekursion deutlich. Wenn die Rekursionstiefe sehr hoch ist, sind sehr viele Methoden noch nicht beendet. Alle Zwischen¬werte und die Rücksprungadressen (siehe auch Kapitel 19) müssen gespeichert werden, d.h. in der Regel hat eine rekursive Lösung einen höheren Speicherbedarf als eine iterative (eine mit einer Schleife).
In vielen Fällen ist es jedoch erheblich leichter, eine rekursive Lösung zu formulieren als eine iterative.
Man kann beweisen, dass alle rekursiven Implementierungen eines Problems auch iterativ und umgekehrt dargestellt werden können.
Als komplexeres Problem sollen die sog. „Kinderkreise“ betrachtet werden. Jeder Kreis hat dabei links und rechts zwei Kinder, diese haben wiederum Kinder, usw. Wenn eine gewisse Größe unterschritten wird, gibt es keine Kinder mehr:
Diese Grafik soll mit einer rekursiven Methode erstellt werden.
int y = 150; public void kinderkreis(double x, double radius, Graphics g) { // das Programm arbeitet für x-Mitte und Radius mit Kommazahlen // für die Zeichenbefehle sind int-Zahlen notwendig, // deshalb wird mit round gerundet und die entstehenden long mit (int) // in int gewandelt. g.drawOval((int)(Math.round(x-radius)),(int)(Math.round(y-radius)), (int)(Math.round(radius*2)),(int)(Math.round(radius*2))) ; // drawOval arbeitet als Parameter nicht mit den Mittelpunktskoord. // und dem Radius, sondern mit einem umbeschriebenen Rchteck. // Parameter 1 und 2 sind die Koordinaten des linken oberen // Rechteckpunkts. Parameter 3 und 4 sind Breite und Höhe des Rechtecks double neuerRadius = radius*0.6 ; // die Verkleinerung der Kinderkreise if(radius > 3) // Hierin steckt die Abbruchbedingung für die Rekursion { // nun kommen die rekursiven Aufrufe: kinderkreis(x-radius-neuerRadius,neuerRadius,g); kinderkreis(x+radius+neuerRadius,neuerRadius,g); // Hier steckt die Berechnung der Mittelpunkte der Kinderkreise drin } } public void paint(Graphics g) { kinderkreis(400.0,100,g); // Aufruf der Methode mit dem Startkreis // Mittelpunkt an der x-Position 400 und Radius 100 }
Hier erfolgt pro Methode ein Aufruf von zwei „Unterprogrammen“, was die Speicherauslastung weiter erhöht. Dieses Beispiel dürfte allerdings nur ziemlich schwierig in eine nichtrekursive Darstellung überführt werden können.
Realisierung von Quicksort
Mit der Rekursion lässt jetzt eine einigermaßen nachvollziehbare Realisierung von Quicksort programmieren. Der Grundgedanke dabei ist, dass die Quicksortmethode nach erfolgter Teilung sich selbst für die beiden Teilfelder aufruft.
Hier zunächst die eigentliche Methode.
public void quicksort (int links, int rechts) { int lizeig = links ; // Initialisieren der beiden Zeiger int rezeig = rechts ; int vergleichpos = (links+rechts)/2 ; long vergleich = werte[vergleichpos] ; // Bestimmen des Vergleichs- // elements do // Beginn der Do-WHILE-SChleife { while ( werte[lizeig] < vergleich ) // linker Zeiger sucht { lizeig++ ; } while ( werte[rezeig] > vergleich ) // rechter Zeiger sucht { rezeig-- ; } if (lizeig <= rezeig) { tausche(lizeig,rezeig) ; //Tauschen, wenn links und rechts zwei lizeig++ ; // nicht passende Elemente gefunden rezeig-- ; // wurden } } while (lizeig <= rezeig ); // wird wiederholt, solange die Zeiger sich // nicht gekreuzt haben if (links < rezeig) quicksort(links,rezeig) ; // rekursiver Aufruf fürs linke Teilfeld if (lizeig < rechts) quicksort(lizeig,rechts) ; // rekursiver Aufruf fürs rechte Teilfeld }
Und hier die Ereignismethode des Quicksort-Buttons.
public void jButton4_ActionPerformed(ActionEvent evt) { long startTime = System.currentTimeMillis(); quicksort(0,aktuGroesse - 1) ; long timeNow = System.currentTimeMillis(); double diff = (timeNow-startTime)/1000.0 ; jTextField2.setText(Double.toString(diff)) ; if (jRadioButton1.isSelected()) gibAus() ; }
Zum Schluss noch die grafische Oberfläche, die auch die Zeitmessung und die beiden einfachen Sortierverfahren enthält. Mit dem Radiobutton kann die Ausgabe ausgeschaltet werden, da bei großen Feldern die Ausgabe des sortierten, bzw. unsortierten Teils ein Vielfaches der Zeit fürs Sortieren erfordert. Mit Zahlengrösse lässt sich der Umfang der Zufallszahlen einstellen, d.h. bei Eingabe 100 erhält man Zufallszahlen zwischen 0 und 99.
Aufgabe
Aufgabe 1
Löse das Problem der Summe der Zahlen von 1 bis 100 („Strafarbeit des kleinen Gauss“, vgl. Kapitel 3) rekursiv.
Aufgabe 2
Eine Folge von Kommazahlen ist folgendermaßen rekursiv definiert: a1 = 1 und . Bestimme zunächst per Hand a2, a3 und a4. Schreibe ein Java-Programm mit einer Methode, die die n-te Zahl in dieser Folge rekursiv berechnet. Das Hauptprogramm soll dann a100 ausgeben.
Aufgabe 3
Die Fibonacci-Folge, deren Elemente auch Fibonacci-Zahlen genannt werden, beginnt mit den Werten1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, Jede Zahl ist die Summe der beiden Vorgänger. Leonardo von Pisa, genannt Fibonacci, stellte in seinem 1202 erschienen Buch Il liber abbaci die berühmte Kaninchenaufgabe, die in heutiger Formulierung so lautet: Wir nehmen an:
- Jedes Kaninchenpaar wird im Alter von 2 Monaten gebärfähig.
- Jedes Kaninchenpaar bringt (ab dem 3. Monat) jeden Monat ein neues Paar zu Welt und
- alle Kaninchen leben ewig (oder wenigstens lange genug).
Beginnen wir nun mit einem frisch geborenen Kaninchenpaar. Wie viele Kaninchenpaare, die von diesem einen Paar abstammen, leben im n-ten Monat? Wie man leicht nachprüft, ergeben sich hierbei die Fibonacci-Zahlen. Erstelle ein Java-Programm, das die n-te Fibonaccizahl rekursiv berechnet. Schreibe zur Übung auch ein Programm, das klassisch mit einer Schleife rechnet. Ein interessanter Test zeigt, dass schon fibo(50), rekursiv berechnet, eine sehr lange Rechenzeit braucht, während dieselbe Zahl iterativ berechnet praktisch sofort erscheint. Erkläre dieses Phänomen!
Aufgabe 4
Erkläre die Funktionsweise des folgenden Konsolen-Programms:
public class test { static void p(int x) { if(x>0) p(x-1); System.out.println(x); } public static void main(String[] args) { p(4); } }
Aufgabe 5
Welche Ausgabe erzeugt folgende Methode, wenn man sie mit p(5) aufruft?
static int p(int x) { if(x==0) return 1; else { int y = p(x-1); System.out.println(x+y); return y + 1; } }
Aufgabe 6
Der Turm von Hanoi ist ein Denkspiel, das aus drei Stäben und einem Turm besteht. Der Turm ist aus n Scheiben aufgebaut, die zu Beginn auf dem ersten Stab aufgefädelt sind, so dass die Scheibengröße von unten nach oben abnimmt:Ziel des Spiels ist es, den Turm vom ersten auf den zweiten Stab zu bewegen, wobei immer nur eine Scheibe auf einmal bewegt werden und nie eine größere auf eine kleinere gelegt werden darf.
Für einen Turm der Höhe 3 könnte eine Lösung wie folgt aussehen:
Veranschauliche diese Lösung zunächst zeichnerisch!
Finde Lösungen für Türme der Höhe 4 und 5 und notiere sie wie in a). Wie viele Züge sind jeweils nötig? Was hat dieses Problem mit Rekursion zu tun?
Schreibe ein rekursives Java-Programm, das eine Lösung für einen Turm der Höhe n ausgeben kann!
Aufgabe 7
Es gibt viele weitere grafische Beispiele zur Rekursion. Ein anspruchsvolles Beispiel ist der Baum des Pythagoras (Bundeswettbewerb Informatik 1986). Finde heraus, wie er erzeugt wird, und programmiere ihn mit Java!
