Arbeitsblätter für JavaKara

Einführung in Java: Rekursion

Autor: Horst Gierhardt

Aufgabe: Kara steht vor einer freien Strecke, an deren Ende ein Baum steht. Er soll bis zum Baum laufen und sich dort umdrehen.

Dieses Problem ist mit einer while-Schleife sehr einfach zu lösen. Darum geht es hier nicht.

Das Neue: Kara soll ohne eine while-Schleife den Weg bis zum Baum finden, weil dies Kara ohne Java auch schon konnte. Damals wurde ein Zustand zumBaum benutzt, der einen Übergang in den selben Zustand und einen Übergang in den Zustand stop hatte. Dieses Vorgehen soll hier mit Methoden nachgebildet werden.

Lösung:

import JavaKaraProgram;
public class BisZumBaum extends JavaKaraProgram
{
  void zumBaum()
  {
   if (!kara.treeFront())
        {  kara.move();
           zumBaum(); // rekursiver Aufruf
        }
   else { kara.turnLeft();
          kara.turnLeft();
        }
  }

  public void myProgram()
  { zumBaum();
  }
}  // Ende von BisZumBaum

Erläuterungen:

1. Die Methode zumBaum ruft sich, solange Kara nicht vor einem Baum steht, immer wieder nach einem kara.move() selbst auf. Erst wenn Kara den Baum erreicht hat, erfolgt kein Selbstaufruf mehr und die Methode ist beendet, nachdem Kara sich umgedreht hat. Der Aufruf von zumBaum in myProgram entspricht dem Setzen des Zustands zumBaum als Startzustand in Kara.

2. Andere Sichtweise: Wenn Kara keinen Baum vor sich hat, geht er vor und hat damit das Problem, den Baum zu finden, um einen Schritt vereinfacht und ruft die gleiche Methode auf.

3. Nach dem rekursiven Aufruf können weitere Methoden aufgerufen werden. Dazu ein Beispiel: Kara soll bis zum Baum laufen und zu seiner Startposition zurückkehren. Rekursion bedeutet Zurückkehren!

   import JavaKaraProgram;
   
   public class BisZumBaumUndZurueck extends JavaKaraProgram
   {
     void zumBaum()
     {
      if (!kara.treeFront())
           {  kara.move();
              zumBaum(); // rekursiver Aufruf
              kara.move();
           }
      else { kara.turnLeft();
             kara.turnLeft();
           }
     }
   
     public void myProgram()
     { zumBaum();
     }
   }  // Ende von BisZumBaumUndZurueck
   
   

   Den Ablauf der rekursiven Aufrufe macht man sich am besten mit der folgenden Übersicht klar.

   
   

   void zumBaum()
    {
      if (!kara.treeFront())
           {
             kara.move();
             zumBaum(); -------->  void zumBaum()
                                    { 
   
                                      if (!kara.treeFront())
                                           { 
   
                                             kara.move();
                                              zumBaum(); -------->  void zumBaum()
                                                                     {
                                                                      if (!kara.treeFront())
                                                                           { // entfaellt }
                                                                      else { kara.turnLeft();
                                                                             kara.turnleft(); }
                                                         <--------   } // Ende von zumBaum
                                              kara.move();
                                           }
                                      else { // entfaellt }
                        <--------   } // Ende von zumBaum
             kara.move();
           }
      else { // entfaellt }
    } // Ende von zumBaum
   

   Man kann es sich so vorstellen, dass sich der Computer bei jedem Aufruf der Methode merkt, wo er die Methode verlassen hat, um die gleiche Methode noch einmal abzuarbeiten. Nach der Abarbeitung macht der Computer dann jeweils an der Stelle weiter, die er sich beim Aufruf gemerkt hat.

4. Rekursive Methoden benötigen unbedingt an einer Stelle eine Abbruchbedingung. Wenn nicht, dann merkt sich der Computer so viele Stellen, an denen er eine Methode rekursiv verlassen hat, bis der Speicher voll ist.

5. Viele Probleme lassen sich rekursiv und nicht-rekursiv lösen. Ein rekursiver Ansatz bietet sich immer dann, wenn man ein gegebenes Problem schrittweise vereinfachen kann und nach einem Schritt im Prinzip das gleiche Problem (aber um einen Schritt einfacher) vorliegen hat.

6. Manchmal sind nicht-rekursive schneller als rekursive Lösungen. Oft sind sie aber nur sehr viel komplizierter zu programmieren. Meistens sind rekursive Lösungen eleganter formulierbar.