Rekursion auf Zeichenketten

Ein Wort ist sein erstes Zeichen plus der Rest — und der Rest ist wieder ein Wort, nur kürzer. Mit den Operationen aus Kapitel 1 heißt das: s.charAt(0) und s.substring(1).

• Zerlegung:s.charAt(0) ist das erste Zeichen, s.substring(1) der Rest mit einem Zeichen weniger.
• Einfachster Fall:die leere Zeichenkette "" mit s.length() == 0.
• Terminierung:der Rest wird bei jedem Aufruf um ein Zeichen kürzer — nach s.length() Schritten ist er leer.
• Umkehren:erst den Rest umkehren, dann das erste Zeichen hinten anhängen.
• Zählen:das Ergebnis für den Rest plus 1, falls das erste Zeichen passt.

static String umkehren(String s) {
    if (s.length() == 0) {
        return "";
    }
    return umkehren(s.substring(1)) + s.charAt(0);
}

static int zaehle(String s, char c) {
    if (s.length() == 0) {
        return 0;
    }
    int rest = zaehle(s.substring(1), c);
    if (s.charAt(0) == c) {
        return rest + 1;
    }
    return rest;
}

• Zerlegung:erstes Zeichen, Mitte s.substring(1, s.length() - 1) und letztes Zeichen.
• Zwei Abbruchfälle:Länge höchstens 1: Palindrom (true). Äußere Zeichen verschieden: sofort false — der Rest muss nicht mehr geprüft werden.
• Aufwand:bei \(n\) Zeichen höchstens \(\lfloor n/2 \rfloor + 1\) Aufrufe, weil jeder Aufruf zwei Zeichen entfernt.
• Indexvariante:statt Teilzeichenketten zu bilden, wandern zwei Grenzen links und rechts aufeinander zu — dieselbe Idee nutzt gleich die binäre Suche.

static boolean istPalindrom(String s) {
    if (s.length() <= 1) {
        return true;
    }
    if (s.charAt(0) != s.charAt(s.length() - 1)) {
        return false;
    }
    return istPalindrom(s.substring(1, s.length() - 1));
}

static boolean istPalindrom(String s, int links, int rechts) {
    if (links >= rechts) {
        return true;
    }
    if (s.charAt(links) != s.charAt(rechts)) {
        return false;
    }
    return istPalindrom(s, links + 1, rechts - 1);
}

Spiele die Rekursion selbst: Klicke in jedem Aufruf das Zeichen an, das er abtrennt — beim Palindrom-Test beide äußeren Zeichen. Der Zähler läuft mit, unten entsteht die Liste der Aufrufe. Mit der Tastatur: ←/→ wählen, Enter markiert. ▶ spielt einen Aufruf vor.

Halte fest: Jeder Aufruf bearbeitet nur das erste Zeichen — oder die beiden äußeren — und überlässt den Rest dem Selbstaufruf. Gezählt, angehängt und entschieden wird beim Rücklauf; nur der Palindrom-Test kann schon vorher mit false abbrechen.