একটি শব্দ প্যালিনড্রোম শব্দ কিনা তা রিকার্শন ব্যবহার করে নির্ধারণ করা

A palindrome is a word that is spelled the same forward and backward. For example, rotor is a palindrome, but motor is not.

একটি সব্দ যে প্যালিনড্রোম পুনরাবৃত্তি ব্যবহারের মাধ্যমে কীভাবে তুমি তা নির্ধারণ করতে পারবে? এখন একদম প্রাথমিক একটি ধারণা থেকে শুরু করা যাক। এই a শব্দটি নিয়ে ভেবে দেখা যাক। এটি একটি প্যালিনড্রোম শব্দ। প্রকৃতপক্ষে, শুধুমাত্র যে ইংরেজি ভাষাতে প্যালিনড্রোম শব্দ থাকবে তা কিন্তু নয় (অথবা যে ভাষাই তুমি বিবেচনা কর না কেন)। আমরা যে কোন একটি শব্দ প্যালিনড্রোম হিসেবে চিন্তা করতে পারি, যে শব্দগুলো সামনে এবং পিছন দুইদিক থেকে পড়লেই একই শব্দ হিসেবে পড়া যাবে, উদাহরণস্বরূপ xyzyzyx। আমরা কিছু অক্ষরের নিয়ে একটি ক্রমকে string (স্ট্রিং) বলে থাকি। তাহলে আমরা এখানে বলতে পারি যে, যদি কোন স্ট্রিং এ শুধুমাত্র একটি অক্ষর থাকে তাহলে সেটা নিশ্চিতভাবে একটি প্যালিনড্রোম। এখন, কোন অক্ষর ছাড়াও একটি স্ট্রিং থাকতে পারে; কোন অক্ষর ছাড়া স্ট্রিংকে আমরা একটি empty string (খালি স্ট্রিং) বলে থাকি। একটি খালি স্ট্রিংও একটি প্যালিনড্রোম হয়ে থাকে, যেহেতু এটি সামনে এবং পিছন থেকে "পড়লে" একই শব্দ পাওয়া যায়। তাহলে এখন বলা যাক, যেকোন স্ট্রিং এ যদি সর্বোচ্চ একটি অক্ষর থাকে তাহলে সেটি একটি প্যালিনড্রোম। এটি হল একদম প্রাথমিক একটি দৃষ্টান্ত: একটি স্ট্রিং যেখানে কোন অক্ষর নেই কিংবা একটি অক্ষর থাকবে সেটি একটি প্যালিনড্রোম হবে।

এখন যদি স্ট্রিং এ দুইটি বা তার থেকে বেশি সংখ্যক অক্ষর থাকে? এখানে আমরা আমাদের রিকার্সিভ ধারণাগুলো এখানে পাব। Rotor(রটোর) কে প্যালিনড্রোম হিসেবে বিবেচনা করা যাক। এটির প্রথম এবং শেষ অক্ষরটি এক এবং যেকোন প্যালিনড্রোমেরই এই নির্দেশকটি থাকতে হবে। অন্য দিকে, প্রথম এবং শেষ অক্ষরটি যদি একই না হয়, যেরকম এই motor শব্দটিতে আছে, তাহলে স্ট্রিংটি প্যালিনড্রোম হবার সম্ভাবনা খুবই কম। আমরা তাহলে একটি স্ট্রিং যে, একটি প্যালিনড্রোম নয় তা ঘোষণা করবার একটি পথ খুঁজে পেলাম: যখন শব্দটির প্রথম এবং শেষ শব্দটি ভিন্ন। আমরা এই অবস্থাটিকে আরও একটি ভিত্তিমূলক ঘটনা হিসেবে চিন্তা করতে পারি কারণ এখানে আমরা উত্তরটি সাথে সাথেই পেয়ে যাচ্ছি। প্রথম এবং শেষ শব্দটি যখন একই, তখন সেটা আমাদের কি বলছে? স্ট্রিংটি একটি প্যালিনড্রোম হতে পারে। আবার এটা প্যালিনড্রোম নাও হতে পারে। Rater এই স্ট্রিং টিতে, প্রথম এবং শেষ অক্ষরটি একই, কিন্তু এই স্ট্রিংটি একটি প্যালিনড্রোম নয়। মনে করা যাক যে আমরা যে কোন একটি শব্দের প্রথম এবং শেষ শব্দটি মুছে দিলাম, স্ট্রিং টি তখন ধরা যাক এমন ভাবে থাকবে ate। এখন তাহলে দেখা যাচ্ছে বাকি থাকা স্ট্রিং টির প্রথম এবং শেষ শব্দ দুইটি এক নয়, আর আমরা তাহলে জানতে পারছি যে rater শব্দটি প্যালিনড্রোম নয়।

এখন তাহলে একটি স্ট্রিং যে প্যালিনড্রোম তা আমরা কীভাবে বের করব। যদি একটি স্ট্রিং এর প্রথম এবং শেষ অক্ষরটি ভিন্ন হয় তাহলে আমরা বলতে পারি যে স্ট্রিংটি প্যালিনড্রোম নয়। অন্যথায় শব্দটির প্রথম এবং শেষ অক্ষরটি মুছে ফেলতে হবে এবং বাকি থাকা স্ট্রিংটি —ছোট সমস্যাটি— প্যালিনড্রোম কিনা তা বিবেচনা করে দেখতে হবে। এই ছোট স্ট্রিং টি, আসল স্ট্রিং টির উত্তর হিসেবে ঘোষণা করা যাবে। যখন তুমি এমন একটি স্ট্রিং এ নেমে আসবে যেটাতে শুধুমাত্র একটি অক্ষর থাকবে কিংবা কোন অক্ষরই থাকবে না তখন এটাকে প্যালিনড্রোম বলা যেতে পারে। আমরা যে দুইটি শব্দ নিয়ে যা আলোচনা করলাম সে সম্পর্কিত ভিজুয়ালাইজেশন এখানে দেওয়া হল:

আমরা এই ব্যপারটি pseudocode (সিউডোকোডে) কীভাবে ব্যাখ্যা করতে পারি?

এই বিষয়বস্তুটি Dartmouth Computer Science এর প্রফেসর Thomas Cormen এবং Devin Balkcom এর সহযোগিতায় এবং একই সাথে খান একাডেমির কম্পিউটিং শিক্ষাক্রম দলের একসাথে কাজ করার মাধ্যমে তৈরি করা হয়েছে। এই বিষয়বস্তু CC-BY-NC-SA দিয়ে লাইসেন্সকৃত।