In der Serie "Named Problems" stelle ich dir klassische, namentlich bekannte Algorithmus-Probleme vor, die seit Jahrzehnten in Ausbildung, Studium und Interviews verwendet werden. Anhand verständlicher Problemstellungen wie FizzBuzz, Türme von Hanoi oder dem Sieb des Eratosthenes lernst du hier, algorithmisch zu denken, Lösungsstrategien zu entwickeln und diese sauber in Java umzusetzen.

Die Türme von Hanoi sind ein bekanntes Denkspiel: Scheiben müssen nach festen Regeln von einem Stab auf einen anderen umgezogen werden.

Das Problem ist berühmt, weil es sich fast wie von selbst in kleinere Teilprobleme zerlegen lässt. Genau das ist der Kern von Rekursion.

In diesem Artikel baust du dir ein klares Modell im Kopf auf und setzt es in Java um: erst straightforward, dann als Alternative mit einem iterativen Ansatz.

Wenn du danach Rekursion bisher eher „magisch“ fandest: hier wird sie nachvollziehbar und praktisch.

 

Problemstellung

Du hast drei Stäbe (z.B. A, B, C) und n Scheiben. Alle Scheiben liegen zu Beginn sortiert auf A (die größte unten, die kleinste oben). Ziel ist es, alle Scheiben nach C zu bewegen.

  • Du darfst immer nur eine Scheibe pro Zug bewegen.
  • Du darfst nur die oberste Scheibe eines Stapels nehmen.
  • Eine größere Scheibe darf nie auf einer kleineren liegen.

Mini-Beispiel für n = 3 (Start: alle auf A, Ziel: C):

  1. Bewege Scheibe 1 von A nach C
  2. Bewege Scheibe 2 von A nach B
  3. Bewege Scheibe 1 von C nach B
  4. Bewege Scheibe 3 von A nach C
  5. Bewege Scheibe 1 von B nach A
  6. Bewege Scheibe 2 von B nach C
  7. Bewege Scheibe 1 von A nach C

 

Die Idee dahinter

Kernkonzept: Rekursion und Problemzerlegung. Statt „n Scheiben auf einmal“ zu lösen, zerlegst du es so:

  • Um n Scheiben von from nach to zu bewegen, musst du zuerst n-1 Scheiben von from nach aux bewegen.
  • Dann bewegst du die größte Scheibe (Scheibe n) von from nach to.
  • Zum Schluss bewegst du die n-1 Scheiben von aux nach to.

Die Visualisierung als kurze Liste:

  • move(n, from, to, aux)
  •   1) move(n-1, from, aux, to)
  •   2) move disk n: from -> to
  •   3) move(n-1, aux, to, from)

 

Schritt für Schritt zur Lösung

  1. Definiere das Ziel: Alle Scheiben sollen von A nach C.
  2. Formuliere die Funktion: move(n, from, to, aux) beschreibt genau diese Aufgabe.
  3. Setze die Abbruchbedingung: Wenn n == 0, gibt es nichts zu tun.
  4. Zerlege das Problem: Bewege erst n-1 Scheiben zur Hilfsstange aux.
  5. Führe den Hauptzug aus: Bewege Scheibe n von from nach to.
  6. Räume auf: Bewege die n-1 Scheiben von aux nach to.
  7. Teste klein: Starte mit n = 1, dann n = 2, dann n = 3.

 

Java-Implementierung (Variante A: straightforward)

public class TowersOfHanoiStraightforward {
  public static void main(String[] args) {
    int n = 3;

    solve(n, 'A', 'C', 'B');
  }

  public static void solve(int n, char from, char to, char aux) {
    if (n < 0) {
      throw new IllegalArgumentException("n must be >= 0");
    }

    move(n, from, to, aux);
  }

  private static void move(int n, char from, char to, char aux) {
    if (n == 0) {
      return; // Abbruchbedingung: nichts zu bewegen
    }

    move(n - 1, from, aux, to);
    printMove(n, from, to);
    move(n - 1, aux, to, from);
  }

  private static void printMove(int disk, char from, char to) {
    System.out.println("Move disk " + disk + " from " + from + " to " + to);
  }
}

Diese Variante zeigt die Rekursion am klarsten: move beschreibt die Problemzerlegung direkt. Wichtig ist die Abbruchbedingung n == 0, damit die Rekursion endet. Die Methode printMove hält die Ausgabe getrennt, damit move leicht zu lesen bleibt.

 

Java-Implementierung (Variante B: Alternative oder Verbesserung)

import java.util.ArrayDeque;
import java.util.Deque;

public class TowersOfHanoiIterative {

  private record Frame(int n, char from, char to, char aux, int stage) {
    Frame nextStage() {
      return new Frame(n, from, to, aux, stage + 1);
    }
  }

  public static void main(String[] args) {
    int n = 3;

    solveIterative(n, 'A', 'C', 'B');
  }

  public static void solveIterative(int n, char from, char to, char aux) {
    if (n < 0) {
      throw new IllegalArgumentException("n must be >= 0");
    }

    if (n == 0) {
      return;
    }

    Deque<Frame> stack = new ArrayDeque<>();

    stack.push(new Frame(n, from, to, aux, 0));

    while (!stack.isEmpty()) {
      Frame f = stack.pop();

      if (f.n() == 0) {
        continue;
      }

      if (f.stage() == 0) {
        stack.push(f.nextStage());
        stack.push(new Frame(f.n() - 1, f.from(), f.aux(), f.to(), 0));
      } else if (f.stage() == 1) {
        printMove(f.n(), f.from(), f.to());
        stack.push(f.nextStage());
      } else {
        stack.push(new Frame(f.n() - 1, f.aux(), f.to(), f.from(), 0));
      }
    }
  }

  private static void printMove(int disk, char from, char to) {
    System.out.println("Move disk " + disk + " from " + from + " to " + to);
  }
}

Hier simulierst du den Aufruf-Stack der Rekursion mit einer eigenen Stack-Datenstruktur (ArrayDeque). Das ist eine gute Übung, um zu verstehen, was bei Rekursion „unter der Haube“ passiert. Die Frame-Datenstruktur merkt sich Parameter und eine kleine stage-Zustandsvariable, damit die Reihenfolge exakt wie bei der rekursiven Variante bleibt.

 

Beispiel: Eingabe und Ausgabe

Beispiel 1: Eingabe n=1 (Start A, Ziel C, Hilfe B)

Output: Move disk 1 from A to C

Beispiel 2: Eingabe n=2 (Start A, Ziel C, Hilfe B)

Output (3 Zeilen): Move disk 1 from A to B, Move disk 2 from A to C, Move disk 1 from B to C

Beispiel 3: Eingabe n=3 (Start A, Ziel C, Hilfe B)

Output beginnt mit: Move disk 1 from A to C, Move disk 2 from A to B, Move disk 1 from C to B ... und endet mit Move disk 1 from A to C

 

Typische Fehler

  • Falsche Abbruchbedingung: if (n == 1) return; ist falsch, weil du dann den letzten Zug nie ausgibst.
  • Off-by-one bei der Scheibennummer: Manche geben bei printMove versehentlich n-1 aus statt n.
  • Parameter vertauscht: Besonders häufig: aux und to in einem der rekursiven Aufrufe falsch gesetzt.
  • Negatives n nicht behandelt: Ohne Guard kann die Rekursion unendlich weiterlaufen oder zu unsinnigen Ausgaben führen.
  • Zu viel Logik in einer Methode: Wenn Ausgabe, Validierung und Rekursion vermischt werden, wird der Code schnell unleserlich.
  • Iterative Simulation ohne Zustand: In der iterativen Variante braucht man eine Art „stage“, sonst verliert man die Reihenfolge (erst links, dann Mitte, dann rechts).

 

Fazit

Bei den Türmen von Hanoi siehst du sehr klar, wie Rekursion durch Problemzerlegung funktioniert: ein großes Problem wird zu zwei kleineren plus einem einfachen Schritt. Du hast eine einfache rekursive Lösung umgesetzt und gelernt, wie man dasselbe Verhalten iterativ mit einem eigenen Stack nachbaut. Wichtig ist vor allem: Abbruchbedingung sauber definieren, Parameter konsistent halten, und erst mit kleinen n testen.