Rekursionsbeispiele

Im Hessen-Abitur tauchen immer wieder dieselben Rekursionsbeispiele auf: die Türme von Hanoi als Paradebeispiel für Divide and Conquer, die Ackermann-Funktion als nicht primitiv-rekursive Funktion und die Baumtraversierung als typische Anwendung in Datenstrukturen. Alle drei zeigen unterschiedliche Aspekte der Rekursion.

Drei Stäbe A, B, C; auf A liegen \( n \) Scheiben absteigender Größe. Ziel: alle Scheiben nach C bewegen, größere Scheiben dürfen nie auf kleineren liegen. Idee: Verschiebe \( n-1 \) Scheiben von A nach B (Hilfsstab C), die unterste Scheibe von A nach C, dann die \( n-1 \) Scheiben von B nach C.

Java:

public static void hanoi(int n, char von, char nach, char hilf) {
    if (n == 1) { System.out.println(von + " -> " + nach); return; }
    hanoi(n - 1, von, hilf, nach);
    System.out.println(von + " -> " + nach);
    hanoi(n - 1, hilf, nach, von);
}

Python:

def hanoi(n, von, nach, hilf):
    if n == 1:
        print(f"{von} -> {nach}")
        return
    hanoi(n - 1, von, hilf, nach)
    print(f"{von} -> {nach}")
    hanoi(n - 1, hilf, nach, von)

Die Anzahl der Züge ist \( 2^n - 1 \), der Algorithmus läuft in \( \mathcal{O}(2^n) \).

Die Ackermann-Funktion ist definiert als \[ A(m, n) = \begin{cases} n + 1 & \text{falls } m = 0 \\ A(m-1, 1) & \text{falls } n = 0 \\ A(m-1, A(m, n-1)) & \text{sonst} \end{cases} \] Sie ist total berechenbar, wächst aber so schnell, dass sie nicht primitiv rekursiv ist.

Java:

public static long ackermann(long m, long n) {
    if (m == 0) return n + 1;
    if (n == 0) return ackermann(m - 1, 1);
    return ackermann(m - 1, ackermann(m, n - 1));
}

Python:

def ackermann(m, n):
    if m == 0:
        return n + 1
    if n == 0:
        return ackermann(m - 1, 1)
    return ackermann(m - 1, ackermann(m, n - 1))

Schon \( A(4, 2) \) ist eine Zahl mit über 19000 Stellen.

Binärbäume können rekursiv durchlaufen werden: Inorder (links, Wurzel, rechts), Preorder (Wurzel, links, rechts) und Postorder (links, rechts, Wurzel).

Java (Inorder):

class Knoten { int wert; Knoten links, rechts; }

public static void inorder(Knoten k) {
    if (k == null) return;
    inorder(k.links);
    System.out.println(k.wert);
    inorder(k.rechts);
}

Python (Inorder):

def inorder(k):
    if k is None:
        return
    inorder(k.links)
    print(k.wert)
    inorder(k.rechts)

Hanoi ist exponentiell und damit für große \( n \) unbrauchbar – aber als Lehrbeispiel ideal. Die Ackermann-Funktion zeigt, dass Rekursion mächtiger sein kann als jede Schleife. Baumtraversierungen laufen in \( \mathcal{O}(n) \), wobei \( n \) die Anzahl der Knoten ist, und werden in Compilern, Datenbanken und Dateisystemen ständig eingesetzt.

Bei Hanoi werden die Stab-Parameter (von/nach/hilf) gerne vertauscht. Bei der Baumtraversierung wird der Null-Check vergessen, was zu einer NullPointerException führt. Bei Ackermann nutzt man besser long, da die Werte schnell den int-Bereich sprengen.

Zusammenfassung: Hanoi zeigt Divide and Conquer, Ackermann zeigt die Mächtigkeit der Rekursion, Baumtraversierung zeigt ihre praktische Anwendung in Datenstrukturen.

Abitur-Tipp: Bei Hanoi solltest du die Züge für \( n=3 \) (sieben Züge) auf Papier auflisten können – das ist eine beliebte Prüfungsfrage.