Rekursion

Question 1

Fakultät mit Rekursion

Answer 1

public int fakultaet(int n)
{
   int result;
   if (n == 0)
   {
      result = 1;
   }
   else
   {
      result = n * fakultaet(n-1);
   }
   return result;
}

Question 2

Aufrufstack

Answer 2

° speichert zur Laufzeit Informationen über die gerade aktiven Methoden in Stackframes
° Bei Methodenaufruf werden die Rücksprungadresse und die lokalen Variablen in einem neuen Stackframe auf dem Stack gespeichert
° Bei Terminierung, wird der zugehörige Stackframe vom Stack geräumt
° In Java nicht zugänglich

Question 3

Aufrufstack bei Rekursion

Answer 3

° Rekursive Methodenaufrufe:
- Jeder rekursive Aufruf erzeugt einen Stackframe
- Jeder Rekursionsstufe arbeitet auf ihren eigenen lokalen Variablen und gibt ein Ergebnis zurück
° Jeder Aufruf legt folgende Informationen auf dem Stack ab: Platz für Ergebnis, Argument n, Rücksprungadresse in die rufende Methode

Question 4

Iterative Fakultät Berechnung

Answer 4

° Rekursive Programme haben oft kein gutes Speicher- und Ablaufverhalten
° Jedes mal wird ein neues Segment auf dem Aufrufstack belegt
° Vergleichsweiise hoher Aufwand

° Iterative Methode:
public int fakultaet (int n)
{
   int fakl = 1;
   for (int i = 1; i <= n; ++i)
   {
      fakl = i * fakl;
   }
   return fakl;
}

Question 5

Rekursion

Answer 5

° Methode m() ruft während der Ausführung ihres Rumpfes sich selber erneut auf:
-> Abruchbedingung zwingend benötigt!
° kleiner Teil des Problems wird gelöst
° Der Rest wird in kleinere Probleme zerlegt und ruft sich selbst mit diesen kleineren Problemen auf
° Zwei Arten von Rekursion:
- Direkt, wenn eine Methode m sich in Rumpf selbst aufruft
- Indirekt, wenn eine Methode m1 eine andere Methode m2 ruft, die aus ihrem Rumpf m1 aufruft

Question 6

Fibonacci-Zahlen mit Rekursion

Answer 6

public int fibonacci (int n)
{
   switch (n) {
      case 0: return 0;
      case 1: return 1;
      default: return fibonacci(n-1) + fibonacci(n-2);
   }
}

Question 7

Anwendungsbereiche von Rekursion

Answer 7

° Rekursiv definierte Strukturen z.B. Baumstrukturen in der Informatik (Syntaxbäume, Entscheidungsbäume, Verzeichnisbäume…)
° Viele sehr gute Sortierverfahren sind rekursiv definiert (z.B. Quicksort und Mergsort)
° Viele Probleme auf Graphen lassen sich elegant rekursiv lösen