Folosirea recursivității pentru a determina dacă un cuvânt este sau nu palindrom

Un palindrom este un cuvânt care se scrie la fel de la stânga la dreapta și de la dreapta la stânga. De exemplu, rotor este un palindrom, dar motor nu este.

Cum putem folosi recursivitatea pentru a verifica dacă un cuvânt este palindrom? Hai să înțelegem, pentru început, care este cazul elementar. Să luăm cuvântul a. El este palindrom. De fapt, nu trebuie să ne gândim numai la cuvinte dintr-o anumită limbă (oricare ar fi aceea). Ne gândim la orice secvență de litere care se citește la fel în ambele sensuri, cum ar fi xyzyzyx. Numim string o secvență de litere. Deci, putem spune că orice string format dintr-o singură literă este palindrom. Ei da, dar dacă un string nu conține nicio literă? Îl numim string vid. Un string vid este și el palindrom, deoarece se "citește" la fel în ambele sensuri. Acum putem spune că orice string care conține cel mult o literă este palindrom. Acesta este cazul elementar: un string cu exact zero sau o literă este palindrom.

Dar dacă în string sunt două sau mai multe litere? Atunci avem un caz recursiv. Să considerăm palindromul rotor. Prima și ultima literă coincid, iar asta este obligatoriu pentru un palindrom. Pe de altă parte, dacă prima și ultima literă nu coincid, ca la motor, atunci nu poate fi palindrom. Așa, deci avem un criteriu după care putem decide dacă un string nu este palindrom: dacă prima și ultima literă diferă. Și această situație poate fi gândită tot ca un caz elementar, deoarece avem răspunsul imediat. Revenind, dacă prima și ultima literă coincid, atunci ce putem spune? String-ul ar putea fi palindrom. Dar, tot așa, ar putea să nu fie. Iată, în string-ul rater prima și ultima literă coincid, dar el nu este palindrom. Să ne imaginăm că ștergem prima și ultima literă și rămânem cu ate. Ei bine, prima și ultima literă din string-ul rămas nu mai coincid, așa că rater nu este palindrom.

Iată cum putem verifica recursiv dacă un string este palindrom. Dacă prima și ultima literă diferă, atunci string-ul nu este palindrom. Altfel, dăm deoparte prima și ultima literă și verificăm dacă șirul rămas—subproblema—este palindrom. Răspunsul pentru șirul mai scurt conduce la răspunsul problemei inițiale. Dacă ajungem la un string fără litere sau format dintr-o singură literă, putem spune că este palindrom. Iată vizualizarea discuției noastre pentru două cuvinte:

Cum putem descrie asta în limbaj pseudocod?

Acest conținut este o colaborare a profesorilor Thomas Cormen și Devin Balkcom, de la Dartmouth Computer Science, cu echipa de elaborare a curriculumului de informatică de la Khan Academy. Conținutul este licențiat CC-BY-NC-SA.