রিকার্শন

তুমি কি রাশিয়ান পুতুলগুলো দেখেছ? প্রথমে, তুমি ছোট একটি প্রস্তরমূর্তির মত পুতুল দেখতে পারবে, সাধারণভাবে কাঠ ব্যবহার করে এটা খোঁদাই এবং রঙ করা হয়, পুতুলটি দেখতে অনেকটা এই রকম:

প্রথম পুতুলের উপরের অংশটি তুমি সরিয়ে ফেলতে পারবে এবং এর ভিতরে তুমি কি দেখতে পারবে? আরেকটি, আরও একটু ছোট, রাশিয়ান পুতুল!

তুমি ঐ পুতুলটিও সরিয়ে ফেলতে পার এবং পুতুলের উপরের এবং নিচের অংশ আলাদা করে ফেলতে পার। এবং তুমি ছোট আরও একটি পুতুল এর মধ্যে দেখবে:

এবং আরও একবার:

এবং তুমি এভাবে চালিয়েই যেতে পার। ধীরে ধীরে তুমি সবচেয়ে ছোট রাশিয়ান পুতুলটি এর মধ্যে খুঁজে পাবে। সর্বশেষ পুতুলটি সম্পূর্ণ একটি পুতুল হবে এবং এটির উপরে আর নিচের অংশ খোলা যাবে না:

আমরা বড় একটি রাশিয়ান পুতুল নিয়ে কাজ করা শুরু করেছিলাম এবং আমরা ছোট থেকে আরও ছোট রাশিয়ান পুতুল দেখলাম আর শেষ পুতুলটি এতো ছোট ছিল যে এটার ভিতরে আর কোন পুতুল রাখা সম্ভব ছিল না।

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

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

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