রিকার্সিভ অ্যালগোরিদমের বৈশিষ্ট্য

এখানে রিকার্সিভ অ্যালগোরিদম সম্পর্কে সাধারণ কিছু ধারণা দেওয়া হল:

যখন আমরা $n!$‍ হিসাব করব, আমরা $n!$‍ কে হিসাব করার সমস্যাটি (মূল সমস্যাটি) সমাধান করব একটি ছোট সমস্যা সমাধান করার মাধ্যমে, যেটা ছোট একটি সংখ্যার উৎপাদক হিসাব করবে, যেটা হল $(n-1)!$‍ হিসাব করে বের করা (ঐ মূল একই সমস্যার ছোট একটি রূপ) এবং তারপরে এই ছোট সমস্যাটির সমাধান ব্যবহার করে $n!$‍ এর মানটি হিসাব করে বের করব।

রিকার্সিভ অ্যালগোরিদমটি কাজ করানোর জন্য, ছোট সমস্যাগুলো ধীরে ধীরে বেস কেসে নিয়ে আসতে হবে। $n!$‍ টি হিসাব করার সময়, ছোট সমস্যাটি আরও ছোট হতেই থাকে, ছোট হতেই থাকে যতক্ষণ পর্যন্ত না আমরা $0!$‍ হিসাব করে বের করছি। তোমাকে অবশ্যই নিশ্চিত করতে হবে যেন সমাধানটি নিয়ে তুমি যেন ধীরে ধীরে মূল সমস্যার দিকে অগ্রসর হও।

উদাহরণস্বরূপ, আমরা যদি আমাদের রিকার্সিভ মেথডটি ব্যবহার করে ঋণাত্মক একটি সংখ্যা হিসাব করতে চাই তাহলে কি হবে? $(-1)!$‍ হিসাব করার জন্য, তুমি প্রথমে $(-2)!$‍হিসাব করে বের করার জন্য চেষ্টা করে দেখতে পার, যাতে এর থেকে পাওয়া ফলাফলটি তুমি $-1$‍ দিয়ে গুণ করতে পার। কিন্তু $(-2)!$‍ হিসাব করার জন্য, প্রথমে তোমাকে $(-3)!$‍ হিসাব করতে হবে, যাতে ফলাফলটি তুমি $-2$‍ দিয়ে গুণ করতে পার। এবং তারপরে তুমি $(-3)!$‍ হিসাব করার জন্য চেষ্টা করবে এবং এভাবে চলতেই থাকবে। অবশ্যই, সংখ্যাগুলো ছোট হয়ে যাচ্ছে, কিন্তু সংখ্যাগুলো বেস কেস $0!$‍ থেকে আরও অনেক দূরে সরে যাচ্ছে। এরকম হলে কখনই তুমি এর উত্তরটি পাবে না।

এখানে যদি তুমি এই নিশ্চয়তাও দিতে পার যে $n$‍ এর মানটি ঋণাত্মক হবে না, তবুও তুমি ঝামেলার মধ্যে পড়বে যদি না তুমি ছোট সমস্যাটির মান পর্যায়ক্রমে ছোট করে না নিয়ে আসো। এখানে একটি উদাহরণ দেওয়া হল। এই সূত্রটি নেওয়া যাক $n!=n\cdot (n-1)!$‍ এবং উভইপক্ষকে $n$‍ দিয়ে ভাগ করা যাক, যেটা $n!/n=(n-1)!$‍ ফেরত দিবে। এখন নতুন একটি চলক তৈরি করা যাক, $m$‍ এবং এর মান $n+1$‍ নির্ধারণ করা যাক। যেহেতু আমাদের সূত্রটি যেকোন ধনাত্মক সংখ্যাতে প্রয়োগ করা সম্ভব, তাই এখন $m$‍ কে $n$‍ দিয়ে প্রতিস্থাপিত করা যাক, যেটা আমাদের $m!/m=(m-1)!$‍ ফলাফলটি দিবে। যেহেতু $m=n+1$‍, আমাদের কাছে তাহলে এখন $(n+1)!/(n+1)=(n+1-1)!$‍ আছে। দিক পরিবর্তন করলে এখানে দেখা যাচ্ছে যে $n+1-1=n$‍ যেটা আমাদের $n!=(n+1)!/(n+1)$‍ দিবে। এই সূত্রটি আমাদের সেই বিশ্বাসের দিকে নিয়ে যাচ্ছে যেখান থেকে আমরা বলতে পারব যে প্রথমে $(n+1)!$‍ হিসাব করার মাধ্যমে এবং তারপরে ফলাফলটি $n+1$‍ দিয়ে ভাগ করার মাধ্যমে আমরা $n!$‍ সংখ্যাটি হিসাব করতে পারব। কিন্তু $(n+1)!$‍ হিসাব করা জন্য, প্রথমে তোমাকে $(n+2)!$‍ হিসাব করতে হবে, তারপরে $(n+3)!$‍ এবং এভাবে আরও হিসাব করে ফল বের করতে হবে। কিন্তু এভাবে 0 এর বেস কেসে আমরা কখনই পৌঁছাতে পারব না। কেন নয়? কারণ প্রতিটি রিকার্সিভ ছোট সমস্যা তোমার কাছে বড় একটি সংখ্যা হিসাব করতে বলে, ছোট কোন সংখ্যা নয়। $n$‍ যদি একটি ধনাত্মক সংখ্যা হয়, তাহলে তুমি কখনই 0 এর বেস কেসে পৌঁছাতে পারবে না।

রিকার্শন সম্পর্কিত ধারণাটি আমরা দুইটি সাধারণ নিয়মে বিভক্ত করতে পারি:

এখন রাশিয়ান পুতুলগুলোর কাছে ফেরত যাওয়া যাক। যদিও তারা কোন অ্যালগোরিদমের ভিতরে থাকতে পারবে না, তুমি এখানে দেখতে পারবে যে প্রতিটি পুতুল এখানে ছোট ছোট অনেকগুলো পুতুল নিয়ে তৈরি হয়েছে (রিকার্সিভের মত অনেকটা), যতক্ষণ পর্যন্ত না সবচেয়ে ছোট পুতুলটি অন্য কোন পুতুলের ভিতরে যেতে পারবে (বেস কেসের মত)।

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