Сөздің палиндром екенін анықтау үшін рекурсияны қолдану

Палиндром - бұл алға-артқа бірдей жазылған сөз. Мысалы, rotor-палиндром, ал motor-жоқ.

Палиндром сөзінің бар-жоғын анықтау үшін рекурсияны қалай қолдануға болады? Негізгі істің не екенін түсінуден бастайық. Сөзді қарастырайық а. бұл палиндром. Шын мәнінде, біз палиндромдарды ағылшын тіліндегі нақты сөздер ретінде қарастырудың қажеті жоқ (немесе сіз қарастырғыңыз келетін кез-келген басқа тіл). Біз палиндромды кез-келген әріптер тізбегі ретінде қарастыра аламыз, мысалы, xyzyzyx. Біз әріптер тізбегін жолдеп атаймыз. Сонымен, тек бір әрпі бар кез-келген жол әдепкі бойынша палиндром деп айта аламыз. Енді жолда әріптер болмайды; біз нөлдік әріптерден жолды бос жолдеп атаймыз. Бос жол палиндром болып табылады, өйткені ол бір нәрсені алға-артқа" оқиды". Сонымен, енді бір әріптен - ден аспайтын кез-келген жол палиндром деп есептейік. Бұл біздің негізгі жағдайымыз: дәл нөлдік әріптермен немесе бір әріппен жазылған жол-палиндром.

Егер жолда екі немесе одан да көп әріптер болса ше? Міне, бізде рекурсивті жағдай болады. Палиндром роторды қарастырайық. Оның бірінші және соңғы әріптері бірдей және бұл қасиет кез-келген палиндром үшін сақталуы керек. Екінші жағынан, егер бірінші және соңғы әріптері motor сияқты сәйкес келмесе, онда жол палиндром бола алмайды. Енді бізде жол палиндром емес екенін жариялаудың жолы бар: оның бірінші және соңғы әріптері әр түрлі болған кезде. Біз бұл жағдайды тағы бір негізгі жағдай ретінде қарастыра аламыз, өйткені бізде жедел жауап бар. Бірінші және соңғы әріптер сәйкес келген уақытқа оралсақ, бұл бізге не туралы айтады? - Жол палиндром болуы мүмкін. Екінші жағынан, олай болмауы мүмкін. rater жолында бірінші және соңғы әріптер сәйкес келеді, бірақ жол палиндром емес. ate жолын қалдырып, бірінші және соңғы әріптерді алып тастаймыз делік. Содан кейін қалған жолдың бірінші және соңғы әріптері сәйкес келмейді, сондықтан біз rafer палиндром емес екенін білеміз.

Сонымен, жолдың палиндром екенін рекурсивті түрде қалай анықтауға болады. Егер бірінші және соңғы әріптер өзгеше болса, онда жол палиндром емес екенін жариялаңыз. Әйтпесе, бірінші және соңғы әріптерді алып тастап, қалған ішкі жол палиндром екенін анықтаңыз. Қысқа жол үшін жауапты бастапқы жол үшін жауап ретінде жариялаңыз. Сіз әріпсіз немесе тек бір әріппен жолға түскеннен кейін оны палиндром деп жариялаңыз. Міне, біз талқылаған екі сөзге арналған визуализация:

Мұны псевдокодта қалай суреттейміз?

Бұл мазмұн ынтымақтастықтың нәтижесі Дартмут компьютерлік ғылымы профессорлар [Томас Кормен](http://www.cs.dartmouth.edu / ~thc/) және [Дэвин Бэлком](http://www.cs.dartmouth.edu / ~devin/), сонымен қатар Хан академиясының компьютерлік оқу бағдарламасы бойынша тобы. Мазмұн лицензияланған CC-BY-NC-SA.