Приложение на рекурсия за определяне дали една дума е палиндром

Палиндром е дума, която наобратно се пише по същия начин. Например rotor е палиндром, но motor не е.

Как мога да използвам рекурсия, за да определя дали една дума е палиндром? Да започнем, като разберем какъв е основният случай. Взимаме думата a. Тя е палиндром. Всъщност не трябва да мислим за палиндромите като за думи в който и да е език. Можем да мислим за палиндромите като за всяка последователност от символи, които се четат еднакво отзад нaпред и отпред назад, като xyzyzyx. Наричаме последователност от символи низ. Затова можем да кажем, че всеки низ, който съдържа само един символ, по подразбиране е палиндром. Един низ може да не съдържа символи; наричаме низ без символи празен низ. Един празен низ също е палиндром, тъй като се "чете" еднакво отзад напред и отпред назад. Да речем, че всеки низ, който съдържа поне една дума, е палиндром. Това е основният случай: низ с точно 0 или 1 символ е палиндром.

Ами ако съдържа два или повече символа? Тук имаме рекурсивен случай. Разглеждаме палиндрома rotor. Първата и последната буква са еднакви, а това трябва да е изпълнено за всеки палиндром. От друга страна, ако първата и последната буква не са еднакви, както е в motor, то този низ не може да е палиндром. Сега имаме начин, по който да заключим, че един низ не е палиндром: когато първата и последната буква са различни. Можем да мислим за тази ситуация като за друг основен случай, тъй като веднага получаваме отговора. Връщаме се на случая, в който първата и последната буква са еднакви – какво ни казва това? Низът може би е палиндром. Но може и да не е. В низа rater, първата и последната буква са еднакви, но той не е палиндром. Да речем, че махнем първата и последната буква, което оставя низа ate. Тогава първата и последната буква на останалия низ не са еднакви и така знаем, че rater не е палиндром.

Ето така можем да определим рекурентно дали един низ е палиндром. Ако първата и последната буква са различни, то можем да заключим, че низът не е палиндром. В противен случай премахваме първата и последната буква и определяме, че низът, който остава – подзадачата – е палиндром. Декларираме, че отговорът за най-краткия низ е отговор за първоначалния низ. Ако стигнеш до низ без букви или само с една буква, то този низ е палиндром. Ето визуализация на решението за двете думи, които обсъдихме:

Как да опишем това с псевдокод?

Това съдържание е резултат от съвместната дейност на преподавателите по Компютърни науки в Дартмут Thomas Cormen и Devin Balkcom, както и на екипа по компютърни науки на Кан Академия. Съдържанието е лицензирано CC-BY-NC-SA.