রিকার্সন

রিকার্সন (Recursion) একটি প্রোগ্রামিং কৌশল যেখানে একটি ফাংশন নিজেই নিজেকে কল করে। এটি একটি সমস্যা সমাধানের পদ্ধতি যেখানে একটি বড় সমস্যাকে ছোট উপ-সমস্যায় ভাগ করা হয় এবং প্রতিটি উপ-সমস্যা সমাধানের জন্য একই ফাংশন পুনরায় ব্যবহার করা হয়।

রিকার্সনের মূল ধারণা

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

রিকার্সনের দুটি গুরুত্বপূর্ণ অংশ

১. বেস কেস (Base Case):

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

২. রিকার্সিভ কেস (Recursive Case):

• এটি এমন অংশ যেখানে ফাংশন নিজেই নিজেকে কল করে এবং সমস্যাটিকে একটি ছোট আকারে পুনরায় প্রয়োগ করে।

রিকার্সনের উদাহরণ

উদাহরণ ১: ফ্যাক্টোরিয়াল গণনা

নিচের উদাহরণে একটি ফাংশন রিকার্সনের মাধ্যমে একটি সংখ্যার ফ্যাক্টোরিয়াল গণনা করছে।

n! = n × (n − 1)!

কোড:

#include <iostream>
using namespace std;

int factorial(int n) {
    // বেস কেস
    if (n <= 1) {
        return 1;
    }
    // রিকার্সিভ কেস
    else {
        return n * factorial(n - 1);
    }
}

int main() {
    int number = 5;
    cout << "Factorial of " << number << " is: " << factorial(number) << endl;
    return 0;
}

ব্যাখ্যা:

• এখানে factorial ফাংশন একটি পূর্ণসংখ্যা n গ্রহণ করে।
• যদি n এর মান ১ বা তার চেয়ে ছোট হয়, তাহলে এটি ১ রিটার্ন করে (বেস কেস)।
• যদি n এর মান ১ এর চেয়ে বড় হয়, তাহলে এটি n * factorial(n - 1) রিটার্ন করে এবং ফাংশন নিজেই নিজেকে কল করে।

উদাহরণ ২: ফিবোনাচ্চি সিরিজ

ফিবোনাচ্চি সিরিজে প্রতিটি সংখ্যা তার আগের দুটি সংখ্যার যোগফল। সিরিজের প্রথম দুটি সংখ্যা ০ এবং ১।

F(n) = F(n − 1) + F(n − 2)

কোড:

#include <iostream>
using namespace std;

int fibonacci(int n) {
    // বেস কেস
    if (n <= 1) {
        return n;
    }
    // রিকার্সিভ কেস
    else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

int main() {
    int terms = 5;
    for (int i = 0; i < terms; i++) {
        cout << fibonacci(i) << " ";
    }
    return 0;
}

ব্যাখ্যা:

• fibonacci ফাংশন প্রতিটি n এর জন্য ফিবোনাচ্চি মান গণনা করে।
• যদি n এর মান ০ বা ১ হয়, তাহলে এটি n রিটার্ন করে (বেস কেস)।
• অন্যথায়, এটি fibonacci(n - 1) + fibonacci(n - 2) রিটার্ন করে এবং পুনরায় ফাংশন নিজেই নিজেকে কল করে।

রিকার্সনের সুবিধা এবং অসুবিধা

সুবিধা

1. কোড সহজ এবং সংক্ষিপ্ত: রিকার্সন ব্যবহার করলে অনেক বড় সমস্যার সমাধান সহজভাবে এবং সংক্ষিপ্তভাবে করা যায়।
2. জটিল সমস্যার সমাধান: কিছু সমস্যা সহজে পুনরাবৃত্তিমূলক (iterative) সমাধান দিয়ে করা সম্ভব নয়, যেখানে রিকার্সন একটি উপযোগী সমাধান দিতে পারে।

অসুবিধা

1. মেমোরি ব্যবহার: প্রতিবার ফাংশন নিজেই নিজেকে কল করার সময় নতুন স্ট্যাক ফ্রেম তৈরি হয়, যা অনেক বেশি মেমোরি ব্যবহার করতে পারে।
2. ধীরগতি: রিকার্সন কখনো কখনো পুনরাবৃত্তিমূলক (iterative) সমাধানের তুলনায় ধীরগতির হতে পারে, কারণ এটি একাধিকবার পুনরাবৃত্তি করতে হয়।
3. স্ট্যাক ওভারফ্লো: বড় ইনপুটের ক্ষেত্রে অনেক সময় ফাংশন কলের সংখ্যা বেশি হয়ে গেলে স্ট্যাক ওভারফ্লো হতে পারে।

রিকার্সনের ব্যবহার ক্ষেত্র

রিকার্সন প্রায়শই নিচের ক্ষেত্রে ব্যবহৃত হয়:

1. ডাটা স্ট্রাকচার (যেমন ট্রি এবং গ্রাফ): ট্রি ট্রাভার্সাল এবং গ্রাফের ক্ষেত্রে রিকার্সন একটি সাধারণ সমাধান।
2. অ্যালগরিদম (যেমন বাইনারি সার্চ, কুইকসোর্ট, মার্জসোর্ট): অনেক অ্যালগরিদম রিকার্সনের মাধ্যমে কার্যকরভাবে সমাধান করা যায়।
3. গাণিতিক সমস্যাগুলি: যেমন ফ্যাক্টোরিয়াল, ফিবোনাচ্চি সিরিজ, পাওয়ার ফাংশন ইত্যাদি।

রিকার্সনের সাথে পুনরাবৃত্তিমূলক সমাধানের তুলনা

সারসংক্ষেপ

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