ডেটা স্ট্রাকচারে রিকার্শনের নীতিমালা

রিকার্শন হলো একটি প্রসেস যার মাধ্যমে একটি ফাংশন নিজে নিজে কল করে। আমরা বড় সমস্যাকে ছোট সাব-প্রোবলেমে ভাগ করে সমাধান করতে রিকার্শন ব্যবহার করি। একটা জিনিস মনে রাখতে হবে, যদি প্রতিটি সাব-প্রোবলেম একই ধরনের প্যাটার্ন ফলো করে, তবেই আমরা রিকার্সিভ এপ্রোচ্ছ ব্যবহার করতে পারি।

একটি রিকার্সিভ ফাংশনের দুটি অংশ থাকে। বেস কেস এবং রিকার্সিভ কেস। বেস কেস রিকার্শন টার্মিনেট করতে ব্যবহৃত হয়। যদি বেস কেস ডিফাইন করা না থাকে, তবে ফাংশন থিওরেটিক্যালি অনন্তবার রিকার হবে।

কম্পিউটার প্রোগ্রামে, যখন আমরা একটি ফাংশন কল করি, প্রোগ্রাম কাউন্টারের মান ইন্টারন্যাল স্ট্যাকে সংরক্ষিত হয় ফাংশন এরিয়াতে যাওয়ার আগে। টাস্ক কম্প্লিট হলে, এড্রেস পপ করে প্রোগ্রাম কাউন্টারে অ্যাসাইন করে এবং টাস্ক রিজিউম করে। রিকার্সিভ কলের সময়, এড্রেস একাধিকবার স্টোর হয় এবং নেক্সট ফাংশন কল স্টেটমেন্টে জাম্প করে। যদি বেস কেস ডিফাইন না থাকে, তবে আবার আবার রিকার হবে এবং স্ট্যাকে এড্রেস স্টোর হবে। যদি স্ট্যাকে স্পেস না থাকে, তবে "Internal Stack Overflow" এরর আসবে।

রিকার্সিভ কলের একটি উদাহরণ হলো একটি সংখ্যার ফ্যাক্টোরিয়াল বের করা। আমরা দেখতে পাচ্ছি n-এর ফ্যাক্টোরিয়াল n! = n * (n-1)!, আবার এটি n * (n-1) * (n-2)!। তাই ফ্যাক্টোরিয়াল যদি একটি ফাংশন হয়, তবে এটি বারবার কল হবে, কিন্তু আর্গুমেন্ট ১ কমানো হবে। যখন আর্গুমেন্ট ১ বা ০ হবে, তবে এটি ১ রিটার্ন করবে। এটি রিকার্শনের বেস কেস হতে পারে।

উদাহরণ

#include 
using namespace std;
long fact(long n){
    if(n <= 1)
        return 1;
    return n * fact(n-1);
}
int main(){
    cout << "Factorial of 6: " << fact(6);
}

আউটপুট

Factorial of 6: 720