Jahrgangsstufe Q1 - Informatik - Dienstag, der 02. März 2021


Rekursion

Mein Name:
Jahrgang/Klasse:
Meine E-Mail-Adresse:


Rekursionsbeispiel 1:

Noch einmal das erste Beispiel: Solange vorne kein Baum steht bewegt sich Kara um einen Schritt nach vorne. Die naheliegende Lösung sieht so aus und ist beim Start von Javakara schon vorgegeben.

  public void myProgram()
  {
       while (!kara.treeFront())
       {
            kara.move();
       }
  }

Kara hat hier das Problem, den Baum mit einer unbekannten Anzahl n von Schritten zu erreichen. Wir ändern nun die Sichtweise des Problems:
Kara geht - wenn möglich - einen Schritt weiter und hat damit
aus dem n-schrittigen Problem ein (n-1)-schrittiges Problem gemacht.

Das Problem wurde also durch einen Schritt quasi vereinfacht. Aber eigentlich steht Kara auch dann noch vor dem fast gleichen Problem, nämlich den Baum zu finden. Und dafür ist die gleiche Methode zuständig:

import javakara.JavaKaraProgram;
public class FindeBaumNeu extends JavaKaraProgram {

  public void findeBaum()
  {  if (!kara.treeFront())
          {  kara.move();  // Problem um einen Schritt vereinfachen
             findeBaum();  // vereinfachtes Problem loesen
          }
     else { kara.turnLeft();
            kara.turnLeft();
            tools.showMessage("Ich habe den Baum gefunden.");
          }
  }

  public void myProgram()
  {  findeBaum();  }
} // End der Klasse

Das ist das Neue: Die Methode findeBaum() ruft sich selbst auf.

Rekursionsbeispiel 2:

Das Programm FindeBaum2 der letzten Stunde beinhaltete das Problem, dass Kara nach dem Finden des Baumes seine Startposition wieder einehmen sollte. Die naheliegende Lösung mit dem Zählen der Schritte auf dem Hinweg und dem Abzählen auf dem Rückweg sieht so aus:

import javakara.JavaKaraProgram;
public class FindeBaum2 extends JavaKaraProgram {

  public void myProgram()
  { int schritte = 0;
    while (!kara.treeFront())
         {  schritte++;  // Auf Hinweg mitzaehlen.
            kara.move();
         }
    kara.turnLeft();
    kara.turnLeft();     // Umdrehen.
    for (int i = 1; i <= schritte; i++)
         kara.move();    // Genauso viel Schritte zurueck.
    kara.turnLeft();
    kara.turnLeft();
  }
} // End der Klasse

Wir ändern nun wieder die Sichtweise des Problems:
Kara geht - wenn möglich - einen Schritt weiter und hat damit
aus dem n-schrittigen Problem ein (n-1)-schrittiges Problem gemacht.
Nach der Lösung dieses Problems folgt ebenso ein Schritt auf dem Rückweg.

import javakara.JavaKaraProgram;
public class FindeBaumNeuZurueck extends JavaKaraProgram {

  public void findeBaum()
  {  if (!kara.treeFront())
          {  kara.move(); // Problem um einen Schritt vereinfachen,
             findeBaum(); // vereinfachtes Problem loesen
             kara.move(); // und einen Schritt auf dem Rueckweg gehen.
          }
     else { kara.turnLeft();
            kara.turnLeft();
          }
  }

  public void myProgram()
  {  findeBaum();
     kara.turnLeft();
     kara.turnLeft();
  }
} // End der Klasse

Bemerkung 1: Die beiden move-Befehle stehen symmetrisch zum Aufruf von findeBaum(). Also gibt es für jeden Schritt auf dem Hinweg auch einen Schritt auf dem Rückweg. Rekursion heißt Zurückkehren!

Bemerkung 2: Die beiden Befehle kara.turnLeft() ganz am Ende von der 1. Version dürfen nicht in der Methode findeBaum() stehen, denn dann würden sie bei jedem Aufruf ausgeführt werden.

Bemerkung 3: Wie geht das eigentlich? Was macht der Computer da eigentlich? Das kann man sich am besten in dieser Erläuterung klarmachen. Bei jedem Aufruf der Methode entsteht sozusagen eine neue Instanz der Methode, sodass eine Methode gleichzeitig mehrfach in einem Computer vorhanden sein kann.

Auftrag 1:


Nimm das Beispielprogramm FindeBaumNeu als Vorlage, nenne die Klasse jetzt FindeBlattNeu, speichere es ab als FindeBlattNeu.java und verändere das Programm so, dass Kara rekursiv (und nicht wie im Bild mit while) ein irgendwo vor ihm liegendes Blatt findet und am Ziel eine Erfolgsmeldung ausgibt. Gib dann das komplette Programm hier ein.

Auftrag 2:

Nimm das Beispielprogramm FindeBaumNeuZurueck als Vorlage, nenne die Klasse jetzt FindeBlattNeuZurueck, speichere es ab als FindeBlattNeuZurueck.java und verändere das Programm so, dass Kara rekursiv (und nicht wie im Bild mit while) ein irgendwo vor ihm liegendes Blatt findet und dieses Blatt an seine Startposition zurückbringt und ablegt. Gib dann das komplette Programm hier ein.

Ich glaube, dass ich die Rekursion in den Beispielen (bitte auswählen!)

verstanden habe.
nicht verstanden habe.

Hier sind weitere Informationen zu meinen Problemen: