Rekursive Algorithmen

Lösung geprüft

Die Aufgabe der heutigen Stunde sind die rekursiven Algorithmen! Fünf Teilaufgaben, und alle drehen sich um dieselbe Idee: eine Methode, die sich selbst aufruft. Das klingt erstmal nach einer Schlange, die sich in den Schwanz beißt, funktioniert aber – solange es einen Rekursionsanker gibt, der das Ganze wieder beendet.

Die Aufgabenstellung lautet

1 Die Fibonaccizahlen sowie deren rekursive und iterative Berechnung wurden im Kapitel vorgestellt. a) Geben Sie die Fibonaccizahlen bis 144 an. b) Analysieren Sie die rekursive und iterative Methode zur Berechnung der Fibonaccizahlen, indem Sie für die Berechnung der dritten Fibonaccizahl jeweils alle Methodenaufrufe und Variablenbelegungen übersichtlich darstellen. c) Rechnerarbeit: Implementieren und testen Sie die rekursive Fibonaccimethode in Java. Entfernen Sie den Rekursionsanker aus Ihrem Programm und testen Sie die Methode erneut. Beschreiben Sie die Fehlermeldung. Begründen Sie, warum der Fehler auftritt.

2 Gegeben ist die rekursive Methode ausgabe. a) Analysieren Sie die Methode, indem Sie angeben, welche Ausgabe erzeugt wird. Erläutern Sie, durch welche Befehle der Rekursionsschritt und der Rekursionsanker umgesetzt werden. b) Erläutern Sie, wie sich die Ausgabe ändert, wenn die beiden Zeilen innerhalb der bedingten Anweisung miteinander vertauscht werden. c) Entwickeln Sie eine iterative Methode, die dieselbe Ausgabe wie in a erzeugt.

3 Die Fakultät: a) Berechnen Sie 6!. Nehmen Sie dabei das Ergebnis von 5! zu Hilfe. b) Geben Sie an, durch welchen Teil der Definition der Rekursionsschritt und durch welchen Teil der Rekursionsanker beschrieben wird. c) Implementieren Sie eine rekursive Methode zur Berechnung der Fakultät. d) Implementieren Sie eine iterative Methode zur Berechnung der Fakultät.

4 Gegeben ist ein Klassendiagramm für ein Würfelspiel. a) Entwickeln Sie jeweils eine Strategie zur iterativen und rekursiven Umsetzung der Methoden addiere, maxFinden und gibErgebnisse und implementieren Sie diese. Erläutern Sie bei den rekursiven Strategien jeweils den Rekursionsanker und den Rekursionsschritt. b) Entwickeln Sie eine weitere Anforderung wie in a und implementieren Sie diese rekursiv.

5 Gegeben sind die drei Methoden rekStart, mA und mB. a) Analysieren Sie die Funktionsweise der Methoden, indem Sie die Abarbeitung der Methodenaufrufe rekStart(3) und rekStart(6) Schritt für Schritt darstellen. b) Beschreiben Sie für jede der drei Methoden, welche Aufgabe sie erfüllt. c) Entwickeln und implementieren Sie ähnliche Methoden und testen Sie ihre Funktionsweise.

Aufgabe 1 – Fibonacci

a) Die Zahlen bis 144

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144

Jede Zahl ist die Summe ihrer beiden Vorgänger. Die ersten beiden sind per Definition 1 – das sind die zwei Ursprungsprobleme, aus denen alles andere entsteht.

b) fib(3) rekursiv, Schritt für Schritt

1. Aufruf: fib(3)
   3 == 1 || 3 == 2  ->  false
   -> return fib(2) + fib(1)

2. Aufruf: fib(2)
   2 == 1 || 2 == 2  ->  true
   -> return 1

3. Aufruf: fib(1)
   1 == 1            ->  true
   -> return 1

Ergebnis: fib(3) = 1 + 1 = 2

b) fib_iterativ(3), Schritt für Schritt

n = 3, weder 1 noch 2  ->  else-Zweig
fib1 = 1, fib2 = 1

i = 1:  1 < n-1 = 2  ->  true
        neueZahl = fib1 + fib2 = 1 + 1 = 2
        fib1 = fib2 = 1
        fib2 = neueZahl = 2

i = 2:  2 < 2  ->  false, Schleife endet

return fib2 = 2

Beide kommen auf 2, aber der Weg ist ein völlig anderer. Die rekursive Fassung baut einen Baum aus Aufrufen auf, die iterative schiebt zwei Variablen durch eine Schleife.

c) Rekursionsanker entfernen – was passiert

public int fib(int n) {
    // if (n==1 || n==2) { return 1; }     <- Anker entfernt
    return fib(n - 1) + fib(n - 2);
}

Die Fehlermeldung lautet:

Konsole

Exception in thread "main" java.lang.StackOverflowError
	at Fibonacci.fib(Fibonacci.java:8)
	at Fibonacci.fib(Fibonacci.java:8)
	at Fibonacci.fib(Fibonacci.java:8)
	... (hunderte weitere Zeilen)

Warum der Fehler auftritt: Ohne den Anker gibt es keine Bedingung mehr, unter der die Methode aufhört. fib(3) ruft fib(2) und fib(1), die rufen fib(0) und fib(-1), und das geht ins Unendliche weiter – die Zahlen werden einfach immer negativer.

Jeder Methodenaufruf braucht Platz auf dem Stack: die Rücksprungadresse, die lokalen Variablen, die Parameter. Der Stack hat aber eine feste Größe. Irgendwann ist er voll, und dann bricht Java mit StackOverflowError ab. Das ist genau das, wovor der Rekursionsanker schützt.

Aufgabe 2 – Die Methode ausgabe

public void ausgabe(int n) {
    if (n > 0) {
        System.out.println(n);
        ausgabe(n - 1);
    }
}

a) Welche Ausgabe entsteht

Ein Countdown. Bei ausgabe(5):

Bestandteil	Im Code	Was er tut
Rekursionsschritt	`ausgabe(n - 1);`	Ruft sich selbst mit einem kleineren Problem auf
Rekursionsanker	`if (n > 0)`	Ist die Bedingung falsch, passiert nichts mehr und kein weiterer Aufruf erfolgt

Hier ist der Anker etwas versteckt: es gibt kein eigenes else und kein return. Der Anker ist einfach der Fall, dass die Bedingung nicht mehr zutrifft – dann wird der Rumpf übersprungen und die Methode ist zu Ende.

b) Die beiden Zeilen vertauschen

public void ausgabe(int n) {
    if (n > 0) {
        ausgabe(n - 1);
        System.out.println(n);
    }
}

Jetzt zählt es aufwärts: 1, 2, 3, 4, 5.

Der Grund ist, wann ausgegeben wird. Vorher wurde erst gedruckt und dann weitergerufen – die Ausgabe passiert also auf dem Weg hinein in die Rekursion. Jetzt wird erst komplett bis n = 0 durchgerufen, und die Ausgaben passieren beim Zurückkommen, also auf dem Weg heraus. Und zurück kommt man in umgekehrter Reihenfolge.

Das ist eine der wichtigsten Einsichten bei Rekursion überhaupt: es macht einen Unterschied, ob du vor oder nach dem rekursiven Aufruf arbeitest.

c) Dieselbe Ausgabe iterativ

public void ausgabeIterativ(int n) {
    for (int i = n; i > 0; i--) {
        System.out.println(i);
    }
}

Die Zählschleife läuft rückwärts von n bis 1. Kürzer, schneller und kein Stack-Problem.

Aufgabe 3 – Die Fakultät

a) 6! mit Hilfe von 5!

5! = 1 · 2 · 3 · 4 · 5 = 120
6! = 6 · 5! = 6 · 120 = 720

Genau das ist der rekursive Gedanke: man muss 6! nicht von vorne ausrechnen, wenn man 5! schon kennt.

b) Anker und Schritt in der Definition

Teil der Definition	Was es ist
`n! = 1` für `n = 0`	Rekursionsanker – hier hört es auf
`n! = n · (n-1)!` für `n > 0`	Rekursionsschritt – führt auf ein kleineres Problem zurück

c) und d) Beide Implementierungen

Fakultaet.java

/* meininfokurs.cmrg.site */

/**
 *
 * Fakultaet rekursiv und iterativ
 *
 * @version 1.0 vom 17.09.2025
 * @meininfokurs.cmrg.site
 */

public class Fakultaet {

    // c) rekursiv
    public int fakultaet(int n) {
        if (n == 0) {
            return 1;                       // Rekursionsanker
        } else {
            return n * fakultaet(n - 1);    // Rekursionsschritt
        }
    }

    // d) iterativ
    public int fakultaetIterativ(int n) {
        int ergebnis = 1;
        for (int i = 2; i <= n; i++) {
            ergebnis = ergebnis * i;
        }
        return ergebnis;
    }

    public static void main(String[] args) {
        Fakultaet f = new Fakultaet();
        System.out.println("6! rekursiv: " + f.fakultaet(6));
        System.out.println("6! iterativ: " + f.fakultaetIterativ(6));
    } // end of main

} // end of class Fakultaet

Die iterative Fassung startet bei i = 2, weil die Multiplikation mit 1 nichts bringt. Für n = 0 läuft die Schleife gar nicht und es kommt richtig 1 heraus.

Ab 13! passt das Ergebnis nicht mehr in einen int – du bekommst dann eine negative Zahl, ohne dass Java warnt. Mit long kommt man bis 20!. Danach hilft nur noch BigInteger.

Aufgabe 4 – Das Würfelspiel

Die Klasse Spiel hat ein Attribut wuerfel vom Typ Wuerfel – also eine Assoziation. Über wuerfel.wuerfeln() kommt man an eine Zufallszahl.

Spiel.java

/* meininfokurs.cmrg.site */

/**
 *
 * Wuerfelspiel - jede Methode einmal iterativ und einmal rekursiv
 *
 * @version 1.0 vom 17.09.2025
 * @meininfokurs.cmrg.site
 */

public class Spiel {

    private Wuerfel wuerfel;

    public Spiel(Wuerfel pWuerfel) {
        this.wuerfel = pWuerfel;
    }

    public Wuerfel getWuerfel() {
        return wuerfel;
    }

    // ---------- addiere ----------
    // iterativ: x mal wuerfeln und aufsummieren
    public int addiereIterativ(int x) {
        int summe = 0;
        for (int i = 0; i < x; i++) {
            summe = summe + wuerfel.wuerfeln();
        }
        return summe;
    }

    // rekursiv: Anker x <= 0 -> 0,  Schritt: ein Wurf + Summe der restlichen
    public int addiere(int x) {
        if (x <= 0) {
            return 0;
        }
        return wuerfel.wuerfeln() + addiere(x - 1);
    }

    // ---------- maxFinden ----------
    public int maxFindenIterativ(int x) {
        int max = 0;
        for (int i = 0; i < x; i++) {
            int wurf = wuerfel.wuerfeln();
            if (wurf > max) {
                max = wurf;
            }
        }
        return max;
    }

    // rekursiv: Anker x <= 1 -> ein einzelner Wurf,
    // Schritt: groesseren Wert aus aktuellem Wurf und Maximum des Rests
    public int maxFinden(int x) {
        if (x <= 1) {
            return wuerfel.wuerfeln();
        }
        int restMax = maxFinden(x - 1);
        int aktuell = wuerfel.wuerfeln();
        if (aktuell > restMax) {
            return aktuell;
        }
        return restMax;
    }

    // ---------- gibErgebnisse ----------
    // aus 2, 4, 6 wird die Zahl 246
    public int gibErgebnisseIterativ(int x) {
        int ergebnis = 0;
        for (int i = 0; i < x; i++) {
            ergebnis = ergebnis * 10 + wuerfel.wuerfeln();
        }
        return ergebnis;
    }

    // rekursiv: der erste Wurf muss an die vorderste Stelle,
    // also mal 10 hoch (x-1)
    public int gibErgebnisse(int x) {
        if (x <= 0) {
            return 0;
        }
        int erster = wuerfel.wuerfeln();
        return erster * (int)Math.pow(10, x - 1) + gibErgebnisse(x - 1);
    }

    // ---------- b) eigene Anforderung ----------
    // Zaehlt, wie viele der x Wuerfe eine Sechs sind. Rekursiv.
    public int zaehleSechser(int x) {
        if (x <= 0) {
            return 0;                                  // Rekursionsanker
        }
        int wurf = wuerfel.wuerfeln();
        if (wurf == 6) {
            return 1 + zaehleSechser(x - 1);           // Rekursionsschritt
        }
        return zaehleSechser(x - 1);
    }

} // end of class Spiel

Anker und Schritt der drei Methoden

Methode	Rekursionsanker	Rekursionsschritt
`addiere`	`x <= 0` → 0, denn die Summe von null Würfen ist 0	ein Wurf plus die Summe der restlichen `x-1`
`maxFinden`	`x <= 1` → ein einzelner Wurf ist automatisch das Maximum	der größere Wert von aktuellem Wurf und Maximum des Rests
`gibErgebnisse`	`x <= 0` → 0, es gibt keine Ziffer mehr	erster Wurf an die vorderste Stelle, dahinter der Rest

Bei maxFinden geht der Anker absichtlich auf 1 und nicht auf 0. Ein Maximum aus null Würfen ist nämlich nicht definiert – bei der iterativen Fassung musste ich deshalb mit max = 0 starten, was bei einem Würfel funktioniert, weil kein Wurf jemals 0 ergibt.

gibErgebnisse ist die interessanteste: iterativ ist es leichter, weil man mit ergebnis * 10 + wurf einfach von links nach rechts anbauen kann. Rekursiv muss man vorher wissen, an welche Stelle die Ziffer gehört – deshalb die Zehnerpotenz.

Aufgabe 5 – rekStart, mA und mB

a) rekStart(3) Schritt für Schritt

rekStart(3)  ->  mA(3, "")

mA(3, "")    3 > 0   ->  "a" + mB(2, "")
mB(2, "")    2 > 0   ->  mA(1, "") + "b"
mA(1, "")    1 > 0   ->  "a" + mB(0, "")
mB(0, "")    0 <= 0  ->  ""

Zurueck einsetzen:
mA(1, "")  =  "a" + ""     =  "a"
mB(2, "")  =  "a" + "b"    =  "ab"
mA(3, "")  =  "a" + "ab"   =  "aab"

Ergebnis: "aab"

flowchart TD
    S["rekStart(3)"] --> A3["mA(3): a + mB(2)"]
    A3 --> B2["mB(2): mA(1) + b"]
    B2 --> A1["mA(1): a + mB(0)"]
    A1 --> B0["mB(0): Rekursionsanker, 0 <= 0"]
    B0 -.->|liefert leeren String| A1
    A1 -.->|liefert a| B2
    B2 -.->|liefert ab| A3
    A3 -.->|liefert aab| S

Wie mA und mB sich gegenseitig aufrufen, bis aab dasteht

Die durchgezogenen Pfeile sind der Weg hinein in die Rekursion, die gestrichelten der Weg zurück. Erst auf dem Rückweg entsteht das Wort – bis zum Anker steht nämlich noch gar nichts fest.

a) rekStart(6) Schritt für Schritt

rekStart(6)  ->  mA(6, "")

mA(6, "")  ->  "a" + mB(5, "")
mB(5, "")  ->  mA(4, "") + "b"
mA(4, "")  ->  "a" + mB(3, "")
mB(3, "")  ->  mA(2, "") + "b"
mA(2, "")  ->  "a" + mB(1, "")
mB(1, "")  ->  mA(0, "") + "b"
mA(0, "")  ->  ""

Zurueck einsetzen:
mB(1, "")  =  ""      + "b"  =  "b"
mA(2, "")  =  "a"     + "b"  =  "ab"
mB(3, "")  =  "ab"    + "b"  =  "abb"
mA(4, "")  =  "a"     + "abb" =  "aabb"
mB(5, "")  =  "aabb"  + "b"  =  "aabbb"
mA(6, "")  =  "a"     + "aabbb" =  "aaabbb"

Ergebnis: "aaabbb"

b) Was jede Methode tut

Methode	Aufgabe
`rekStart`	Startet das Ganze. Sie rechnet selbst nichts, sondern ruft nur `mA` mit einem leeren String auf. So eine Methode nennt man Hüllmethode.
`mA`	Hängt vorne ein „a" an und gibt den Rest an `mB` weiter. Ihr Anker ist `n <= 0` → leerer String.
`mB`	Holt sich das Ergebnis von `mA` und hängt hinten ein „b" an. Gleicher Anker.

Zusammen erzeugen sie Wörter der Form aⁿbⁿ – also gleich viele a wie b, alle a vorne, alle b hinten. Bei rekStart(6) ist es „aaabbb", bei rekStart(8) wäre es „aaaabbbb".

Das ist auch der Grund, warum mA und mB getrennt sind. mA arbeitet vor dem rekursiven Aufruf, mB danach – genau der Unterschied aus Aufgabe 2. Dadurch landen die a am Anfang und die b am Ende, obwohl sie abwechselnd erzeugt werden.

Der Fachbegriff dafür ist wechselseitige Rekursion: nicht eine Methode ruft sich selbst, sondern zwei Methoden rufen sich gegenseitig.

Der Parameter s wird durch alle Aufrufe durchgereicht, aber nirgends gelesen. Man könnte ihn ersatzlos streichen und das Ergebnis wäre dasselbe. So etwas fällt beim Analysieren auf und ist einen Satz in der Antwort wert.

c) Eine ähnliche Methode

// Erzeugt Woerter der Form x^n y^n, also z.B. "xxxyyy"
public String rekStart2(int n) {
    return mX(n);
}

public String mX(int n) {
    if (n <= 0) {
        return "";
    }
    return "x" + mY(n - 1);
}

public String mY(int n) {
    if (n <= 0) {
        return "";
    }
    return mX(n - 1) + "y";
}

Wer es spannender mag, dreht die Reihenfolge um und erzeugt mit return mA(n-1, s) + "a" und return "b" + mB(n-1, s) stattdessen bⁿaⁿ. Es lohnt sich, das einmal durchzuspielen – man merkt schnell, wie sehr die Position des rekursiven Aufrufs alles bestimmt.