Verwende Rekursion zum bestimmen ob ein Wort ein Palindrom ist

Ein Palindrom ist eine Zeichenkette, die vorwärts wie rückwärts gelesen identisch ist. Zum Beispiel ist Rotor ein Palindrome, aber nicht Motor.

Wie kann man Rekursion verwenden, um festzustellen, ob ein Wort ein Palindrom ist? Zuerst definieren wir den Basisfall. Betrachten wir das Wort a. Es ist ein Palindrom. In der Tat sollten wir uns Palindrome nicht als tatsächliche Worte in der deutschen Sprache (oder in einer anderen Sprache, die dir liegt) vorstellen. Ein Palindrom ist eine beliebige Zeichenkette, die vorwärts und rückwärts gelesen werden kann und dabei gleich ist, wie zB xyzyzyx. Wir nennen eine Sequenz von Buchstaben einen string . So können wir also sagen, dass jeder String, der nur einen Buchstaben enthält, standardmäßig ein Palindrom ist. Nun kann ein String aber auch leer sein. Wir nennen einen String, der null Buchstaben enthält einen Leerstring . Ein Leerstring ist auch ein Palindrom, da er vorwärts wie rückwärts gelesen werden kann. Also legen wir fest , dass jeder String mit höchstens einem Buchstabe ein Palindrom ist. Das ist unser Grundfall: ein String mit genau null Buchstaben oder einem Buchstaben ist ein Palindrom.

Was ist, wenn der String zwei oder mehr Buchstaben enthält? Hier haben wir unseren rekursiven Fall. Betrachten Sie das Palindrom Rotor. Der erste und letzte Buchstabe sind gleich, und diese Eigenschaft muss für jedes Palindrom gelten. Wenn hingegen die ersten und letzten Buchstaben ungleich sind, wie bei Motor, dann kann der String kein Palindrom sein. Damit haben wir einen Weg gefunden zu erklären, wann ein String kein Palindrom ist: Nämlich wenn sein erster und letzter Buchstabe unterschiedlich sind. Wir können diese Situation als einen anderen Basisfall bezeichnen, da wir die Antwort sofort haben. Wenn der erste und letzte Buchstabe gleich sind, was sagt uns das? Der String könnte ein Palindrome sein. Aber vielleicht auch nicht. In der Zeichenfolge rater sind die ersten und letzten Buchstaben gleich, aber die Zeichenfolge ist kein Palindrom. Angenommen, wir trennen die ersten und letzten Buchstaben ab und nehmen den verbleibenden String ate. Dann sind die ersten und letzten Buchstaben dieses Strings nicht die gleichen, und so wissen wir, dass rater kein Palindrom ist.

So können wir also rekursiv feststellen, ob ein String ein Palindrom ist. Wenn sich der erste und letzte Buchstabe unterscheiden, dann deklarieren wir, dass die Zeichenfolge kein Palindrom ist. Andernfalls trennen wir den ersten und letzten Buchstaben ab und bestimmen, ob die Zeichenfolge, die übrigbleibt - das Unterproblem - ein Palindrom ist. Sobald du zu einem Leerstring ohne Buchstaben gelangst, oder zu einem String mit nur einem Buchstaben, dann deklariere ihn als ein Palindrom. Hier ist eine Visualisierung für zwei Wörter, die wir besprochen haben:

Wie würden wir das in Pseudocode beschreiben?

Dieses Tutorial ist in Zusammenarbeit zwischen den Professoren Thomas Cormen und Devin Bock von Dartmouth Computer Sience und dem Khan Academy Computing Curiculum-Team entstanden und wurde von der KA Deutsch Community übersetzt. Das Tutorial ist unter der Lizenz CC-BY-NC-SA lizenziert.