Eine Schleife als Rekursion:

Will man für Kara eine Methode gehe(int schritte) schreiben, die ihn eine bestimmte Anzahl Schritte gehen lässt, geht man normalerweise so vor:

import javakara.JavaKaraProgram;

public class Schleife1 extends JavaKaraProgram
{
  public void gehe(int schritte)
  {  for (int i=1; i<=schritte; i++)
        kara.move();
  }

  public void myProgram()
  { gehe(5);  }
}

Ändert man aber seine Denkweise in Richtung Rekursion, dann besteht das Problem, z. B. 5 Schritte zu gehen, aus einem Schritt nach vorne und dem Problem, noch 4 Schritte zu gehen. Oder allgemein formuliert:
Problem(n) = ein Schritt plus Problem(n-1).
Auf diese Weise ist es ganz erstaunlich, dass man eine Schleife auch rekursiv umschreiben kann:

import javakara.JavaKaraProgram;

public class Schleife2 extends JavaKaraProgram
{
  public void gehe(int schritte)
  { if (schritte>0)
         { kara.move();
           gehe(schritte-1);
         }
  }

  public void myProgram()
  { gehe(5);  }
}

Aufgabe 1:

Schreibe eine rekursive Variante einer Methode lege(anzahl), die eine bestimmte Anzahl Kleeblätter ab der aktuellen Position legt. Auf Bäume muss nicht geachtet werden. Kopiere das komplette Programm hier in das Formular.

Eine Funktion mit Rekursion:

Kara startet auf einer Strecke, die bis zu einem Baum führt. Er soll die Anzahl der Blätter zählen und das Ergebnis als Funktionswert zurückliefern. Dieses Problem würde man herkömmlich so lösen:

import javakara.JavaKaraProgram;

public class Funktion1 extends JavaKaraProgram
{
  public int blaetterVormBaum()
  { int anzahl = 0;
    while (!kara.treeFront())
         { if (kara.onLeaf())
                anzahl++;
           kara.move();
         }
    if (kara.onLeaf())
         anzahl++;  // letztes Blatt nicht vergessen.
    return anzahl;
  }

  public void myProgram()
  { int x = blaetterVormBaum();
    tools.showMessage("Ich habe " + x + " Blaetter gefunden.");  }
}

Ändert man aber wieder seine Denkweise in Richtung Rekursion, dann besteht das Problem darin, zur Anzahl der Blätter auf dem Rest des Weges eine 1 oder eine 0 für ein oder kein Blatt auf der aktuellen Position dazu zu addieren. Oder allgemein formuliert:
Anzahl(Aktueller Weg) = 0 oder 1 plus Anzahl(Restweg nach einem Schritt).
Auf diese Weise kann man die Funktion auch rekursiv umschreiben:

import javakara.JavaKaraProgram;

public class Funktion2 extends JavaKaraProgram
{
  public int blaetterVormBaum()
  { if (kara.treeFront())        // Abbruch der Rekursion
         { if (kara.onLeaf())
                return 1;
           else return 0;
         }
    else { // vorne frei         Rekursion geht weiter
           if (kara.onLeaf())
                { kara.move();
                  return 1 + blaetterVormBaum();
                }
           else { kara.move();
                  return 0 + blaetterVormBaum();
                }
         }
  }

  public void myProgram()
  { int x = blaetterVormBaum();
    tools.showMessage("Ich habe " + x + " Blaetter gefunden.");  }
}

Aufgabe 2:

Schreibe eine rekursive Variante einer Funktion baumAbstand, die den Abstand zu einem Baum bzw. die Anzahl der nötigen Schritte bis zum Baum bestimmt. Kopiere das komplette Programm hier in das Formular.

Noch eine Funktion mit Rekursion:

Eine einfache Funktion, die das n-fache einer Zahl x berechnet, ist hier gegeben:

import javakara.JavaKaraProgram;

public class Funktion3 extends JavaKaraProgram
{
  public double vielfaches(double x, int n)
  { return x * n;
  }

  public void myProgram()
  { double zahl = 3.1415;
    int faktor  = 4;
    double ergebnis = vielfaches(zahl, faktor);
    String satz = "Das " + faktor + "-fache von " + zahl;
    satz = satz + " ist " + ergebnis + ".";
    tools.showMessage(satz);
  }
}

Nun ändern wir wieder die Denkweise in Richtung Rekursion. Dann bedeutet das z. B., dass das 4-fache einer Zahl die Zahl plus deren 3-faches ist. Oder allgemein formuliert:
n-faches(Zahl) = Zahl + (n-1)-faches(Zahl).
Auf diese Weise kann man die Funktion auch rekursiv umschreiben:

import javakara.JavaKaraProgram;

public class Funktion4 extends JavaKaraProgram
{
  public double vielfaches(double x, int n)
  { if (n==1) return x;
    else return x + vielfaches(x, n-1);
  }

  public void myProgram()
  { double zahl = 3.1415;
    int faktor  = 4;
    double ergebnis = vielfaches(zahl, faktor);
    String satz = "Das " + faktor + "-fache von " + zahl;
    satz = satz + " ist " + ergebnis + ".";
    tools.showMessage(satz);
  }
}

Hinweis: Natürlich ist es bei einer so einfachen Berechnung wie dem Vielfachen nicht nötig, auf die Rekursion zurückzugreifen, denn schließlich hat man irgendwann die Multiplikation erfunden. Wenn es einfach ohne Rekursion geht, dann macht man es eben einfach. Häufig sind aber Probleme schon eher rekursiv formuliert, so dass dann die rekursive Variante der Programmierung einfacher als die herkömmliche ist.

Wie ist der der Ablauf der Rekursion zu verstehen?

Aufgabe 3:

Schreibe eine rekursive Variante der Funktion potenz(double x, int n) für n>=0. potenz(5, 3) liefert dann 5³ = 125. Achtung: 5⁰ = 1; 5¹ = 5. Nimm dir das angegebene Beispiel mit vielfaches(...) als Vorlage, schreibe es um und kopiere das komplette Programm hier in das Formular.