Wykorzystanie rekurencji do zbadania czy słowo jest palindromem

Palindrom to słowo brzmiące tak samo czytane od przodu i od tyłu. Na przykład, rotor jest palindromem, a motor nie jest.

Jak można użyć rekurencji do sprawdzenia czy dane słowo jest palindromem? Zacznijmy od wyjaśnienia czym tutaj jest przypadek bazowy. Rozważmy słowo a. To jest palindrom. Właściwie nie musimy myśleć o palindromach jako rzeczywistych słowach w języku angielskim, polskim (lub jakimkolwiek innym). Możemy myśleć o palindromach jako dowolnej sekwencji liter, która czytana jest tak samo od przodu i od tyłu, tak jak: xyzyzyx. Sekwencję liter nazywamy string (łańcuch). Możemy więc powiedzieć, że każdy łańcuch znaków zawierający jedną literę jest z pewnością palindromem. A co z łańcuchem znaków nie zawierającym liter? Nazywamy taki łańcuch pustym łańcuchem. Pusty łańcuch jest również palindromem, ponieważ "czytamy" go tak samo od przodu, jak od tyłu. Możemy zatem powiedzieć, że jakikolwiek łańcuch znaków zawierający co najwyżej jedną literę jest palindromem. To jest nasz bazowy przypadek: łańcuch z dokładnie jedną literą lub nie zawierający liter jest palindromem.

Co w przypadku, gdy łańcuch zawiera dwie lub więcej liter? Tu właśnie będziemy mieć nasz przypadek rekurencyjny. Rozważmy palindrom rotor. Jego pierwsza i ostatnia litera są takie same - i ta właściwość musi być zachowana dla każdego palindromu. Z drugiej strony, jeśli pierwsza i ostatnia litera nie są takie same, jak w słowie motor, wtedy łańcuch znaków nie może być palindromem. Mamy zatem sposób na określenie kiedy łańcuch znaków nie jest palindromem: kiedy jego pierwsza i ostatnia litera są różne. Możemy pomyśleć o tej sytuacji jako o innym przypadku bazowym, skoro odpowiedź znamy natychmiast. Wróćmy jednak do momentu, gdy pierwsza i ostatnia litera są takie same - co nam to mówi? Że łańcuch znaków może być palindromem. Ale również może nim nie być. W łańcuchu znaków rater pierwsza i ostatnia litera są takie same, ale łańcuch nie jest palindromem. Załóżmy, że usuniemy pierwszą i ostatnią literę, pozostawiając ciąg ate. Teraz pierwsza i ostatnia litera tego mniejszego łańcucha znaków nie są takie same, czyli wiemy, że słowo rater nie jest palindromem.

W taki właśnie sposób możemy rekurencyjnie stwierdzić czy łańcuch znaków jest palindromem. Jeśli pierwsza i ostatnia litera różnią się od siebie, stwierdzamy, że dany łańcuch znaków nie jest palindromem. W przeciwnym przypadku, usuwamy pierwszą i ostatnią literę i znów sprawdzamy czy łańcuch znaków, który pozostał jako —podproblem— jest palindromem. Odpowiedź na to pytanie dla krótszego łańcucha znaków jest odpowiedzią dla oryginalnego łańcucha. Kiedy już dojdziemy do łańcucha, który nie zawiera liter lub posiada tylko jedną literę, stwierdzamy, że łańcuch znaków jest palindromem. Oto wizualizacja dwóch słów, o których rozmawiamy:

Jak opiszemy to w pseudokodzie?

Materiał powstał we współpracy profesorów z Dartmouth Computer Science Thomasa Cormena i Devina Balkcoma oraz zespołu nauczycieli informatyki Khan Academy. Materiał jest udostępniony na licencji CC-BY-NC-SA.