Dies ist eine alte Version des Dokuments!

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

  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
  }

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() ;
  }