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
\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: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
page revision: 34, last edited: 21 Nov 2015 09:31