studyklar
GdI 1 · Übungsblatt 10 · Aufgabe 3

Palindrom rekursiv prüfen: Lagerregal von außen nach innen

„Lagerregal“ liest sich von vorn wie von hinten. Solche Wörter heißen Palindrome. Eine Methode prüft das rekursiv: Sie vergleicht den ersten und den letzten Buchstaben und ruft sich dann selbst für den Rest in der Mitte auf. Rechts steht erst die Kette dieser Aufrufe für „Lagerregal“, dann das ganze Programm. Mit Weiter geht es Schritt für Schritt voran.

Die Aufgabe

Aufgabe 10.3

Ein Wort wird Palindrom genannt, wenn es vom Anfang und vom Ende her gelesen identisch ist. Beispiele sind Anna und Lagerregal. Ein nichtleeres Wort ist also offensichtlich ein Palindrom, wenn der erste und der letzte Buchstabe identisch sind und der verbleibende Mittelteil wieder ein Palindrom ist. Groß-/Kleinschreibung wird dabei nicht unterschieden.

Auf der Basis dieser Beschreibung soll ein Java-Programm implementiert werden, welches die Eigenschaft „ist Palindrom“ mit Hilfe der Rekursion entscheidet. Konkret soll also eine rekursive Java-Methode der Form boolean isPalindrom (String text) implementiert werden, welche in der main-Methode getestet werden kann. In der main-Methode sollen fortlaufend, d. h. in einer Endlosschleife, beliebige Wörter von der Tastatur gelesen und jeweils eine entsprechende Meldung zur Eigenschaft „ist Palindrom“ auf dem Bildschirm ausgegeben werden. Verwenden Sie die Vorlage A10_3.java.

Die Vorlage A10_3.java:

class A10_3 {     static boolean isPalindrom (String text) {         // Geben Sie den fehlenden Code der Methode hier ein!     }     public static void main (String[ ] args) {        while (true) {            // Aufforderung und Eingabe eines Worts              // Leeres Wort eingegeben?              // Umwandlung in Kleinschreibung              // Prüfung auf Palindrom und Ausgabe          }    }}

Gesucht sind zwei Dinge. Erstens die Methode isPalindrom: Sie bekommt einen Text und gibt true (wahr) zurück, wenn er ein Palindrom ist, sonst false (falsch). Zweitens ein Hauptprogramm, das immer wieder ein Wort einliest und das Ergebnis meldet.

Die Aufgabe gibt den Weg schon vor: Erster und letzter Buchstabe müssen gleich sein, und der Mittelteil muss wieder ein Palindrom sein. Großbuchstaben zählen wie Kleinbuchstaben, „Anna“ ist also ein Palindrom, obwohl A und a verschieden aussehen.

Merke: Rekursion heißt hier: dieselbe Frage für ein kürzeres Wort stellen. Weil das Wort bei jedem Aufruf um zwei Buchstaben kürzer wird, endet die Kette sicher. Spätestens bei einem Wort mit 0 oder 1 Buchstaben steht die Antwort fest.
  1. Die Idee: von außen nach innen.
  2. Der Basisfall: 0 oder 1 Buchstabe.
  3. Ersten und letzten Buchstaben vergleichen.
  4. Sich selbst für den Mittelteil aufrufen.
  5. Die ganze Aufrufkette für „Lagerregal“.
  6. Hauptprogramm: Endlosschleife, Eingabe, Abbruch.
  7. Alles in Kleinbuchstaben umwandeln.
  8. Prüfen, melden, testen.

Die Idee: von außen nach innen

    static boolean isPalindrom (String text) {
    }

Bei „lagerregal“ sind der erste und der letzte Buchstabe gleich: l und l. Übrig bleibt der Mittelteil „agerrega“. Ist er ein Palindrom, dann auch das ganze Wort. Für den Mittelteil stellt sich also dieselbe Frage wie vorher, nur für ein Wort mit zwei Buchstaben weniger.

Genau das macht eine rekursive Methode: Sie löst die Aufgabe, indem sie sich selbst mit einer kleineren Aufgabe aufruft. Rechts steht jeder Aufruf als eine Zeile. Das Wort ist dort schon klein geschrieben; warum, zeigt Schritt 7.

Aus Skript 5, Folie 5-75 („Ablauf einer rekursiven Methode“): Eine rekursive Methode ruft sich selbst auf. Jede Ausführung hat ihre eigenen Variablen. Die Aufrufe gehen nach unten bis zum Basisfall, die Ergebnisse kommen nach oben zurück.

Der Basisfall: 0 oder 1 Buchstabe

        if (text.length() <= 1) {            return true;        }

Irgendwann muss die Kette enden. Ein Wort mit nur einem Buchstaben, etwa „t“, liest sich von beiden Seiten gleich. Ein leeres Wort „“ auch, denn es gibt nichts, was verschieden sein könnte. Beide sind Palindrome.

Also gibt die Methode bei einer Länge von höchstens 1 sofort true zurück, ohne sich selbst aufzurufen. Wörter mit gerader Länge wie „lagerregal“ (10 Buchstaben) enden beim leeren Wort, Wörter mit ungerader Länge wie „rentner“ (7) bei einem Buchstaben.

Noch 7 Schritte bis zum Ergebnis
Den ganzen Lösungsweg sehen Studierende und Lehrende der HS KL. Registriere dich mit deiner Adresse @stud.hs-kl.de oder @hs-kl.de, dann geht es hier direkt weiter.
Registrieren

Abbildung 1Die Methode isPalindrom

von außen nach innen

  1. 1.lagerregal? = ?→ ?
  2. 2.?? = ?→ ?
  3. 3.?? = ?→ ?
  4. 4.?? = ?→ ?
  5. 5.?? = ?→ ?
  6. 6."" (leer)Basisfall→ ?
LegendeAufrufkette von isPalindrom.