NPS2E1: Fibonacci - Iteration und Rekursion im direkten Vergleich

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 Fibonacci-Folge ist ein bekanntes Problem, weil man damit sehr gut den Unterschied zwischen Iteration und Rekursion verstehen kann.

Die Regel ist simpel: Jede Zahl ist die Summe der beiden vorherigen. Trotzdem kann die Umsetzung sehr unterschiedlich aussehen, je nachdem, ob du eine Schleife oder einen rekursiven Aufruf verwendest.

In diesem Artikel baust du beide Varianten in Java nach, siehst typische Fehler und lernst, wann welche Lösung sinnvoll ist.

Problemstellung

Schreibe eine Funktion, die das n-te Fibonacci-Zahl zurückgibt.

• Die Folge startet hier mit F(0) = 0 und F(1) = 1.
• Für n >= 2 gilt: F(n) = F(n - 1) + F(n - 2).
• Constraint: n soll nicht negativ sein.
• Hinweis: Fibonacci-Zahlen wachsen schnell. Wir nutzen long, sind aber trotzdem begrenzt.

Mini-Beispiel:

1. F(0) = 0
2. F(1) = 1
3. F(2) = 1
4. F(3) = 2
5. F(4) = 3
6. F(5) = 5

Die Idee dahinter

Das Kernkonzept hier ist Iteration vs. Rekursion. Beides kann zum gleichen Ergebnis führen, aber der Weg dahin unterscheidet sich.

• Iteration: Du rechnest die Folge Schritt für Schritt in einer Schleife aus und merkst dir die letzten zwei Werte.
• Rekursion: Du definierst das Problem über sich selbst: f(n) ruft f(n - 1) und f(n - 2) auf, bis eine Abbruchbedingung erreicht ist.

Eine kleine Visualisierung (Index -> Wert):

• 0 -> 0
• 1 -> 1
• 2 -> 1
• 3 -> 2
• 4 -> 3
• 5 -> 5

Schritt für Schritt zur Lösung

1. Definiere die Basisfälle. Wenn n 0 oder 1 ist, kennst du das Ergebnis sofort.
2. Validiere die Eingabe. Bei n < 0 wirfst du eine Exception, damit Fehler früh sichtbar werden.
3. Entscheide dich für den Ansatz. Iteration ist meist schneller und braucht weniger Speicher, Rekursion ist oft kürzer und erklärt gut die Definition.
4. Iterativ: Starte mit zwei Variablen für die letzten Werte und wiederhole das Addieren bis Index n erreicht ist.
5. Rekursiv: Stelle die Abbruchbedingung klar nach oben und rufe danach die Teilprobleme auf.
6. Teste mit kleinen Werten. Zum Beispiel n = 5 sollte 5 ergeben, und n = 10 sollte 55 ergeben.

Java-Implementierung (Variante A: straightforward)

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

    public static long fibIterative(int n) {
        validateNonNegative(n);

        if (n == 0) {
            return 0L;
        }
        if (n == 1) {
            return 1L;
        }

        long prev = 0L;  // F(0)
        long curr = 1L;  // F(1)

        for (int i = 2; i <= n; i++) {
            long next = prev + curr;
            prev = curr;
            curr = next;
        }

        return curr;
    }

    private static void validateNonNegative(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("n must be non-negative");
        }
    }
}

Diese Variante ist absichtlich naiv: Sie folgt direkt der Definition F(n) = F(n - 1) + F(n - 2). Wichtig ist die klare Abbruchbedingung für n == 0 und n == 1. Nachteil: Für größere n wird sie schnell sehr langsam, weil viele Werte immer wieder neu berechnet werden.

Java-Implementierung (Variante B: Alternative oder Verbesserung)

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

    public static long fibIterative(int n) {
        validateNonNegative(n);

        if (n == 0) {
            return 0L;
        }
        if (n == 1) {
            return 1L;
        }

        long prev = 0L;  // F(0)
        long curr = 1L;  // F(1)

        for (int i = 2; i <= n; i++) {
            long next = prev + curr;
            prev = curr;
            curr = next;
        }

        return curr;
    }

    private static void validateNonNegative(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("n must be non-negative");
        }
    }
}

Hier nutzt du Iteration: Du läufst von 2 bis n und hältst immer nur die letzten zwei Werte. Das ist sehr effizient, weil jeder Fibonacci-Wert genau einmal berechnet wird. Die Laufzeit wächst dabei linear mit n, und der Speicherverbrauch bleibt konstant.

Beispiel: Eingabe und Ausgabe

• Eingabe n = 0 Output 0
• Eingabe n = 5 Output 5
• Eingabe n = 10 Output 55

Typische Fehler

• Off-by-one in der Schleife: Wenn du bis i < n statt i <= n läufst, bekommst du oft F(n - 1) statt F(n).
• Falsche Basisfälle: Manche starten mit F(1) = 0 und F(2) = 1. Das ist ok, aber dann müssen alle Beispiele und Tests dazu passen.
• Abbruchbedingung bei Rekursion vergessen: Ohne klare Basisfälle läuft die Rekursion unendlich (bis zum Stack Overflow).
• Negative Eingaben still akzeptieren: Dann entstehen später schwer zu findende Fehler. Besser früh per IllegalArgumentException stoppen.
• Zu großer Datentyp ignoriert: Auch long läuft irgendwann über. Wenn Ergebnisse plötzlich negativ werden, ist das oft ein Overflow.
• Rekursive Variante für große n nutzen: Die naive Rekursion wird extrem langsam, weil sie sehr viele doppelte Berechnungen macht.

Fazit

Du hast gesehen, wie man Fibonacci einmal rekursiv und einmal iterativ löst. Rekursion ist gut, um die mathematische Definition sauber abzubilden, aber die naive Version wird schnell unpraktisch. Iteration ist meist die bessere Wahl, weil sie schnell bleibt und wenig Speicher braucht.