Rekursion und Iteration

Aus Kapitel 2 kennst du die Summe einer Reihung mit einer Schleife. Dieselbe Aufgabe lässt sich rekursiv lösen: Die Summe ab Index i ist a[i] plus die Summe ab i + 1. Aufruf: summe(a) bzw. summe(a, 0).

static int summe(int[] a) {
    int s = 0;
    for (int i = 0; i < a.length; i++) {
        s = s + a[i];
    }
    return s;
}

static int summe(int[] a, int i) {
    if (i == a.length) {
        return 0;
    }
    return a[i] + summe(a, i + 1);
}

• Schleifenvariable:wird zum Parameter: i wird im Selbstaufruf als i + 1 weitergegeben.
• Schleifenbedingung:wird verneint zur Abbruchbedingung: Die Schleife läuft, solange i < a.length; die Rekursion endet bei i == a.length.
• Schleifenkörper:wird zum Rekursionsschritt: a[i] wird mit dem Ergebnis für den Rest verknüpft.
• Hilfsvariable:s entfällt — das Zwischenergebnis steckt im Rückgabewert.
• Endrekursion:ist der Selbstaufruf die letzte Aktion (return f(…); wie bei ggT), lässt sich die Methode direkt als Schleife schreiben.
• Gleich mächtig:jede Schleife lässt sich als Rekursion schreiben und jede Rekursion als Schleife — notfalls mit einem selbst verwalteten Stapel.

static long fibIter(int n) {
    long a = 0;                 // fib(0)
    long b = 1;                 // fib(1)
    for (int i = 0; i < n; i++) {
        long neu = a + b;
        a = b;
        b = neu;
    }
    return a;
}

Fibonacci iterativ: zwei Variablen wandern die Folge entlang, fibIter(10) liefert 55.

• Laufzeit:fib aus 3.1.2 berechnet dieselben Teilprobleme immer wieder — die Zahl der Aufrufe wächst exponentiell; fibIter braucht \(n\) Durchläufe.
• Speicher:die Rekursion braucht einen Rahmen je offener Ebene (Tiefe \(n\)), die Schleife nur den einen Rahmen der Methode.
• Lesbarkeit:die rekursive Fassung steht näher an der Definition und ist oft kürzer und leichter zu prüfen.

Stelle mit dem Regler \(n\) ein und vergleiche, wie viele Aufrufe fib(n) braucht und wie viele Durchläufe fibIter(n). Der zweite Regler legt fest, wie viele Aufrufe der Rechner pro Sekunde schafft. Schalte zwischen logarithmischer und linearer Skala um; ▶ lässt \(n\) wachsen.

Halte fest: Jedes zusätzliche \(n\) vervielfacht die Aufrufe von fib etwa um den Faktor 1,6 — bei fibIter kommt nur ein Durchlauf dazu. Ein schnellerer Rechner verschiebt die Grenze kaum.