Rekursion

Lösung eines Problems durch Rekursion

Eine Operation kabel(n:GZ):GZ soll die Anzahl der Kabel ermitteln, die nötig sind um n Häuser mit jeweils einem Kabel direkt miteinander zu verbinden. Bei vielen Aufgabenstellungen ist eine Lösung leichter zu finden, indem sie rekursiv definiert wird. Beispiel:

Graphik	Anzahl der Häuser	Ergebnis	Funktion
	n = 1	0 Kabel	kabel(1)->0
	n = 2	1 Kabel	kabel(2)->1
	n = 3	Das 3. Haus wird mit den ersten beiden Häusern verbunden: 1 + 2 = 3 Kabel	kabel(3)=kabel(2)+2->3
	n = 4	Beim 4. Haus braucht es 3 weitere Kabel: 3 + 3 = 6 Kabel	kabel(4)=kabel(3)+3->6
	n = 5	Beim 5. Haus: 6 + 4 = 10 Kabel (0+1+2+3)+4 = 10	kabel(5)=kabel(4)+4->10
	n	Bei n Häusern:   0+1+2+..+n-1 die Summe der Zahlen von 0 bis n-1.	kabel(n)=kabel(n-1)+n-1

public class Kabel{
  static int kabel(int n){
    if (n<=1) return 0;
    return kabel(n-1)+n-1;
  }
}

Auflösen einer Rekursion durch Iteration

Viele rekursiv gelöste Probleme lassen sich durch eine Schleife (Iteration) bewältigen, die weniger speicherintensiv ist. Entwickler versuchten vor optimierenden Compilern daher Rekursion möglichst zu vermeiden. Mittlerweile erkennen Compiler auflösbare Rekursionen (Endrekursionen) und ersetzen sie durch Iterationen. Bei dem Kabel-Problem ist eine Lösung mit for-Schleife greifbar nahe:

Erstellen Sie eine Operation kabelFor(n:GZ):GZ. Lösung anzeigen..

public class KabelFor{
  static int kabelFor(int n){
    int i, summe=0;
    for(i=1;i<n;i++){
      summe = summe + i;
    }
    return summe;
  }
}

Aufgabe: Klingende Gläser

Auf einer Fete sind bereits 17 Leute. Sebastian kommt als 18. Jeder Neuankömmling stößt mit jedem an. Sebastian wird gefragt wie oft nun nach seiner Ankunft die Gläser schon geklungen haben. "Die Frage kann ich leicht beantworten, wenn derjenige, der vor mir gekommen ist, sein Ergebnis nennt." sagt Sebastian. Alle lachen, Timo sagt: "Ursula kam vor dir und hat auch schon so gefragt!" "Timo hat gut lachen", sagt Sabine, "er hat niemand zu fragen brauchen, er war nämlich der erste heute Abend und brauchte bloß einmal mit dem Gastgeber anzustoßen."

Analysieren Sie das Problem (Tabelle)

Entwickeln Sie eine Operation Summe.angestossen(n:GZ):GZ und ein Struktogramm für die Lösung. Lösung anzeigen..

public class Summe{
  static int angestossen(int n){
    if (n<=1) return 0;
    return angestossen(n-1)+n-1;
  }
}

Permutation (Fakultät, Produkt über n)

Rekursive Definition der Möglichkeiten: m(1)=1; sonst m(n)=m(n-1)*n

Entwickeln Sie eine rekursive Operation Hut.m(n:GZ):GZ Lösung anzeigen..

public class Hut{
  static int m(int n){
    if(n<=1) return 1;
    return m(n-1)*n;
  }
}

Mathe-Einschub

In der Mathematik wird das '!' Zeichen für die Fakultätsfunktion benutzt:

D.h.. Sollen 4 Hüte auf 4 Haken verteilt werden, gibt es 4! =1*2*3*4 = 24 Möglichkeiten!

Entwickeln Sie eine iterative Operation Fakultaet.fak(n:GZ):GZ, die das Produkt von 1..n berechnet. Lösung anzeigen..

public class Fakultaet{
  static int fak(int n){
    int i,produkt=1;
    for(i=1;i<=n;i++){
      produkt*=i;
    }
    return produkt;
  }
}

Fibonacci

In Lehrbuch der Mathematik aus dem Mittelalter stellte "Leonard der des Bonaccus" (filius bonacci = fibonacci) die folgende Aufgabe:

Wieviele Kaninchenpaare werden im Laufe eines Jahres, von einem Paar ausgehend geboren?
Dabei wirft jedes Paar monatlich ein weiteres Paar, das wiederum nach Ablauf des 2.Lebensmonats ein weiteres Paar wirft. Die Populationsfolge wird auch Fibonacci-Folge genannt.

Erstellen Sie eine Operation Fibonacci.fib(n:GZ):GZ, die die existierenden Kaninchenpaare im Montat n zurückgibt.

Tipp: 1, 1, 2, 3, 5, 8, 13, ... fib(n) = fib(n-1) + fib(n-2)

Erstellen Sie eine Operation Fibonacci.tabelle(n:GZ), die eine formatierte Tabelle der Population bis zum Monat n ausgibt. Lösung anzeigen..

public class Fibonacci{
  static int fib(int n){
    if(n<=2) return 1;
    return fib(n-1)+fib(n-2);
  }
  static void tabelle(int n){
    int i;
    System.out.println("Monat | Kanninchenpaare");
    for(i=1;i<=n;i++){
      System.out.printf("%3d   | %12d \n",i,fib(i));
    }
  }
}

Beachten Sie die Dauer der Rechenzeit ab n=40 und wieso wird das Ergebnis ab n=46 negativ?