Oopm1516 Ex03

Zielsetzung für die Übung

  • Analyse rekursiver Funktionen
  • Call- bzw. recursiontree (Aufrufbaum)
    • subdivision Algorithmus
    • Anwendungsfall: subdivision.png
    • Entwickeln einer Abbruchbedingung
  • Call- bzw. recursionstack (Aufrufstapel)
    • Gegeben sei folgende rekursive mathematische Funktion
(1)
\begin{align} x_n = \begin{cases} 0 & \text{wenn } n < 0 \\ 1 & \text{wenn } n = 0 \\ 4 & \text{wenn } n = 1 \\ 10 & \text{wenn } n = 2 \\ 2 \cdot x_{n-1} + x_{n-3} & \text{sonst } \end{cases} \end{align}
Hieraus ergibt sich folgender Rekursionsbaum:
recursiontree.png
Mittels Tiefentraversierung erhalten wir folgendes Verhalten des Aufrufstapels:
[x(4)]
[x(4), x(3)]
[x(4), x(3), x(2)]
[x(4), x(3)]
[x(4), x(3), x(0)]
[x(4), x(3)]
[x(4)]
[x(4), x(1)]
[x(4)]
[]
  • Ackermannfunktion
    • Der folgende Code gibt den Rekursionsstapel für die Ackermannfunktion im Sinne der Hausaufgabe aus
    • Dazu wurde der Code wie folgt modifiziert
      • Initialisierung eines Stapels (Stack)
      • push beim Funktionsaufruf
      • pop nach jeder Rückkehr aus einer Rekursion. (Gegebenenfalls Trennung von rekursivem Aufruf und Return-Statement)
      • Ausgabe des Stapels nach jeder Stapel-Operation (push oder pop)
import java.util.Stack;
 
public class Main {
 
    static Stack<String> s = new Stack<String>(); // Anlegen eines leeren Stacks
 
    public static int ack(int n, int m) {
        s.push("ack(" + n + ", "+ m + ")"); // Hinzufügen des aktuellen Aufrufs zum Rekursionsstapel
        System.out.println(s); // Ausgeben des aktuellen Stapels nach "push"
        if (n == 0) {
            s.pop(); // Entfernen eines Stapel-Eintrags
            System.out.println(s); // Ausgeben des aktuellen Stapels nach "pop"
            return m + 1;
        }
        else if (m == 0) {
            int ret = ack(n - 1, 1); 
            s.pop(); // Entfernen eines Stapel-Eintrags zwischen dem rekursivem Aufruf und Return
            System.out.println(s); // Ausgeben des aktuellen Stapels nach "pop"
            return ret;
        } else {
            int ret = ack(n - 1, ack(n, m - 1));
            s.pop(); // Entfernen eines Stapel-Eintrags zwischen dem rekursivem Aufruf und Return
            System.out.println(s); // Ausgeben des aktuellen Stapels nach "pop"
            return ret;
        }
    }
 
    public static void main(String[] args) {
        System.out.println("result is: " + ack(1,2));
    }
 
}

Ausgabe auf der Konsole:

[ack(1, 2)]
[ack(1, 2), ack(1, 1)]
[ack(1, 2), ack(1, 1), ack(1, 0)]
[ack(1, 2), ack(1, 1), ack(1, 0), ack(0, 1)]
[ack(1, 2), ack(1, 1), ack(1, 0)]
[ack(1, 2), ack(1, 1)]
[ack(1, 2), ack(1, 1), ack(0, 2)]
[ack(1, 2), ack(1, 1)]
[ack(1, 2)]
[ack(1, 2), ack(0, 3)]
[ack(1, 2)]
[]
result is: 4

Zielsetzung für das Programmierpraktikum

  • Entwickeln einer rekursiven Lösung
    • Fakultät
    • Rekursive mathematische Notation
    • rekursive Suche im String
  • Korrekturverfahren transparent machen
    • Verstehen der PublicTests.java und der ExtraTests.java