Typische Fehler — was oft schiefgeht

Richtig ist: Die Abbruchbedingung muss vor dem Selbstaufruf stehen, sonst wird sie nie erreicht — jeder Aufruf ruft sofort den nächsten auf, bis zum StackOverflowError.

static int summe(int n) {
    if (n == 0) {
        return 0;
    }
    return n + summe(n - 1);
}

Richtig ist: Die Abbruchbedingung muss jeden möglichen Weg abfangen — hier auch ungerade und negative Werte.

static int haelfte(int n) {
    if (n <= 0) {
        return 0;
    }
    return 1 + haelfte(n - 2);
}

Richtig ist: Der Rückgabewert des Selbstaufrufs ist das Teilergebnis — er muss weitergegeben werden. Sonst liefert die Methode schon beim ersten Zeichen, das nicht passt, 0.

    return zaehle(s.substring(1), c);

Richtig ist: Die zweite Ausgabe läuft erst beim Aufstieg, und dort endet der zuletzt begonnene Aufruf zuerst: Ausgabe 321123. Der Aufrufstapel arbeitet nach dem Prinzip „zuletzt hinein, zuerst hinaus“.

Richtig ist: Der Aufrufbaum hat 9 Knoten, gleichzeitig offen sind aber nur die Aufrufe auf einem Weg von der Wurzel zu einem Blatt: fib(4), fib(3), fib(2), fib(1) — Tiefe 4. Ebenso Mergesort: \(2n - 1\) Aufrufe, aber nur \(\log_2 n + 1\) gleichzeitig.

Richtig ist: Wie bei Reihungen läuft der Index einer Zeichenkette von 0 bis s.length() - 1; s.charAt(s.length()) wirft eine StringIndexOutOfBoundsException. Der Rest ohne beide Randzeichen ist s.substring(1, s.length() - 1).

if (s.charAt(0) != s.charAt(s.length() - 1)) {
    return false;
}

Richtig ist: Bei zwei Elementen gilt mitte = links — der Bereich bleibt gleich, die Rekursion endet nie. a[mitte] ist nach dem Vergleich erledigt und gehört nicht mehr dazu.

if (a[mitte] < x) {
    return binSuche(a, x, mitte + 1, rechts);
}
return binSuche(a, x, links, mitte - 1);

Richtig ist: Die Teilbereiche müssen lückenlos aneinanderstoßen und dürfen sich nicht überlappen. Hier fehlt a[mitte]; bei zwei Elementen entsteht außerdem ein leerer Bereich, den der Basisfall links == rechts nicht abfängt.

int maxL = maximum(a, links, mitte);
int maxR = maximum(a, mitte + 1, rechts);

Richtig ist: Die Schleife endet, sobald eine Hälfte leer ist. Die übrigen Elemente der anderen Hälfte müssen ohne Vergleich übernommen werden — sonst bleiben in hilf Nullen stehen.

while (i <= mitte) { hilf[k] = a[i]; i++; k++; }
while (j <= rechts) { hilf[k] = a[j]; j++; k++; }

Richtig ist: Die Sortierung stimmt zwar, aber bei gleichen Werten wird das rechte Element zuerst übernommen — gleiche Schlüssel tauschen ihre Reihenfolge. Mit <= gewinnt das linke, früher stehende Element: Mergesort bleibt stabil.

if (a[i] <= a[j]) {

Richtig ist: Nach zerlege steht das Pivot an Index p endgültig. Wird es mitsortiert und liegt es ganz rechts, bleibt der Bereich gleich groß — endlose Rekursion.

quicksort(a, links, p - 1);
quicksort(a, p + 1, rechts);

Richtig ist: Quicksort braucht im Mittel etwa \(1{,}39\,n\log_2 n\), im ungünstigsten Fall (z. B. sortierte Eingabe, Pivot = letztes Element) \(\frac{n(n-1)}{2}\) Vergleiche bei Tiefe \(n\). Mergesort garantiert höchstens \(n\log_2 n\), braucht aber eine Hilfsreihung der Länge \(n\).