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 Fakultät ist ein Klassiker, weil sie eine einfache Formel hat, aber trotzdem sehr gut zeigt, wie Rekursion funktioniert.

Du lernst hier zwei Dinge, die bei Rekursion immer entscheidend sind: die Abbruchbedingung (wann hört es auf?) und den rekursiven Schritt (wie komme ich dem Ziel näher?).

Ausserdem bauen wir zwei Java-Lösungen: erst eine straightforward rekursive Variante, danach eine Alternative, die ohne Rekursion auskommt.

 

Problemstellung

Berechne die Fakultät einer nichtnegativen ganzen Zahl n. Die Fakultät wird als n! geschrieben und bedeutet: n * (n-1) * (n-2) * ... * 1.

  • Eingabe: eine ganze Zahl n (nichtnegativ)

  • Ausgabe: der Fakultätswert n!

  • Regeln: 0! = 1 und 1! = 1

  • Hinweis: Werte werden schnell groß, daher nutzen wir in Java long und prüfen Überlauf.

  • Mini-Beispiel:

  1. 3! = 3 * 2 * 1 = 6
  2. 5! = 5 * 4 * 3 * 2 * 1 = 120
  3. 0! = 1

 

Die Idee dahinter

Rekursion bedeutet: Eine Methode löst ein Problem, indem sie ein kleineres Problem der gleichen Art löst.

Bei der Fakultät sieht das so aus: n! = n * (n-1)!. Das ist der rekursive Schritt.

Damit das nicht endlos weitergeht, brauchst du eine Abbruchbedingung: für n == 0 (oder n == 1) ist das Ergebnis direkt bekannt.

  • Mini-Visualisierung für 4!:
  • factorial(4) = 4 * factorial(3)
  • factorial(3) = 3 * factorial(2)
  • factorial(2) = 2 * factorial(1)
  • factorial(1) = 1 (Abbruch)

 

Schritt für Schritt zur Lösung

  1. Entscheide, welche Eingaben erlaubt sind: hier nur n >= 0.
  2. Lege die Abbruchbedingung fest: n == 0 (und optional n == 1).
  3. Formuliere den rekursiven Schritt: n * factorial(n - 1).
  4. Prüfe, ob die Methode bei jedem Aufruf wirklich kleiner wird (sonst Endlosschleife).
  5. Denke an Überlauf: Fakultäten wachsen schnell, also prüfen wir die Multiplikation.

 

Java-Implementierung (Variante A: straightforward)

public class FactorialRecursiveDemo {
  public static void main(String[] args) {
    System.out.println("0! = " + factorialRecursive(0));
    System.out.println("5! = " + factorialRecursive(5));
    System.out.println("10! = " + factorialRecursive(10));
  }

  static long factorialRecursive(int n) {
    validateNonNegative(n);

    if (n == 0) {
      return 1L; // Abbruchbedingung: 0! = 1
    }

    long sub = factorialRecursive(n - 1);
    return multiplyExactAsLong(n, sub);
  }

  static void validateNonNegative(int n) {
    if (n < 0) {
      throw new IllegalArgumentException("n must be >= 0");
    }
  }

  static long multiplyExactAsLong(long a, long b) {
    // Wir nutzen Math.multiplyExact fuer sauberen Ueberlauf-Check.
    return Math.multiplyExact(a, b);
  }
}

Diese Variante zeigt Rekursion sehr direkt: erst kommt die Abbruchbedingung, dann der rekursive Schritt n * factorialRecursive(n - 1).

Wichtig ist, dass n bei jedem Aufruf kleiner wird. So erreichst du sicher 0 und die Rekursion endet.

Mit Math.multiplyExact bekommst du bei zu großen Ergebnissen eine Exception statt eines still falschen Wertes.

 

Java-Implementierung (Variante B: Alternative oder Verbesserung)

public class FactorialIterativeDemo {
  public static void main(String[] args) {
    System.out.println("0! = " + factorialIterative(0));
    System.out.println("5! = " + factorialIterative(5));
    System.out.println("10! = " + factorialIterative(10));
  }

  static long factorialIterative(int n) {
    validateNonNegative(n);

    long result = 1L;
    for (int i = 2; i <= n; i++) {
      result = Math.multiplyExact(result, i);
    }
    return result;
  }

  static void validateNonNegative(int n) {
    if (n < 0) {
      throw new IllegalArgumentException("n must be >= 0");
    }
  }
}

Die iterative Variante macht das Gleiche, aber ohne Rekursion: sie multipliziert von 2 bis n auf.

Das ist oft robuster, weil kein Call-Stack verwendet wird. Gerade bei größeren n kann Rekursion sonst in einen Stackoverflow laufen.

Auch hier prüfen wir mit Math.multiplyExact den Überlauf.

 

Beispiel: Eingabe und Ausgabe

  • Eingabe: n = 0 Output: 1
  • Eingabe: n = 3 Output: 6
  • Eingabe: n = 5 Output: 120

 

Typische Fehler

  • Abbruchbedingung fehlt oder ist falsch: z.B. nur n == 1 behandelt, aber n == 0 vergessen.
  • Falscher rekursiver Schritt: z.B. factorial(n) ruft wieder factorial(n) auf (keine Verkleinerung) und endet nie.
  • Negatives n nicht abgefangen: ohne Validierung läuft die Rekursion immer weiter nach unten.
  • Off-by-one bei der Iteration: z.B. Schleife bis i < n statt i <= n, Ergebnis ist dann zu klein.
  • Überlauf ignoriert: long ist begrenzt; ohne Check bekommst du falsche Ergebnisse ohne Warnung.
  • Datentyp zu klein: int reicht nur für sehr kleine Fakultäten, danach wird es schnell falsch.
  • Zu große Eingabe für Rekursion: auch wenn die Logik stimmt, kann zu tiefe Rekursion einen Stackoverflow verursachen.

 

Fazit

Du hast gesehen, wie man die Fakultät mit Rekursion berechnet und warum die Abbruchbedingung dabei der wichtigste Schutz vor Endlosrekursion ist. Ausserdem hast du eine iterative Alternative kennengelernt, die oft die bessere Wahl ist, wenn du größere Eingaben erwartest.