রিকার্শন এবং ডাইনামিক প্রোগ্রামিং

Updated on October 22, 2019 in Competitive Programming
0 on October 22, 2019

ইউজার-ডিফাইন্ড ফাংশন এবং রিকার্শন

প্রোগ্রামিং ভাষা দিয়ে কোনো নির্দেশনা সম্পাদনের মূল হাতিয়ার হলো ফাংশন তৈরি। আমরা প্রাথমিক অবস্থায় শুধু main ফাংশন নিয়ে কাজ করলেও বড় বড় কাজ সম্পাদনের জন্য ইউজার-ডিফাইন্ড ফাংশন ব্যবহার করতে হয়। উদাহরণস্বরূপ একটি সংখ্যার ফ্যাক্টোরিয়াল নির্ণয়ের জন্য আমরা main ফাংশনের বাইরে factorial() নামে আরেকটি ফাংশন ব্যবহার করতে পারি যেটার স্ট্রাকচারটা অনেকটা এরকম-

int factorial(int n) 
{ 
    int res = 1, i; 
    for (i = 2; i <= n; i++) 
        res *= i; 
    return res; 
} 

এবার আমরা ভিন্ন একটি পথ অনুসরণ করবো। আমরা লুপের ভিতর প্রত্যেকবার ২ থেকে ঐ সংখ্যা পর্যন্ত গুণ না করে একই ফাংশন বারবার কল করে কাজটা করার চেষ্টা করবো। কোনো ফাংশন যখন নিজেকে নিজেই কল করে করে ঐ সমস্যার বেস কেস পর্যন্ত রান করে তখন সেই ফাংশনটিকে আমরা রিকার্সিভ ফাংশন এবং এই উপায়টিকে রিকার্শন বলে। উপরের একই প্রোগ্রামটিকে রিকার্শন ব্যবহার করে নতুন করে লিখে পাই-

int factorial(int n)
{
    if(n > 1)
        return n * factorial(n - 1);
    else
        return 1;
}

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

কিন্তু কেন করবো আমরা রিকার্শন? ইটারেশন দিয়েও তো একই কাজ করা যাচ্ছে! এখানেই চলে আসে ডাইনামিক প্রোগ্রামিং এর কেরামতি!

ডাইনামিক প্রোগ্রামিং

উইকিপিডিয়া অনুযায়ী,
Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. In both contexts it refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner. While some decision problems cannot be taken apart this way, decisions that span several points in time do often break apart recursively.

আমরা যদি আমাদের ফ্যাক্টোরিয়ালের সমস্যাটিই দেখি, এখানে আমরা factorial(n) জানি যদি আমরা factorial(n-1) এর মান জানি। এতে সমস্যাটি অনেকটা ছোট হয়ে ভাগ হয়ে গেলো। এখন আমরা ডিপির সাহায্যে ক্যালকুলেশনগুলো মনে রেখে প্রোগ্রামটিকে আরও ফাস্ট করতে পারি। এখানে আমরা যদি প্রতিবার হিসাবের পর factorial(n) এর মান মেমরিতে রেখে দিতে পারি তাহলে পরের হিসাবে factorial(n+x) এর মান বের করতে আর factorial(1) পর্যন্ত যাওয়াই লাগবে না! ভালো করে দেখো এইবার আমরা বেস কেস কে প্রত্যেকবার আপডেট করে দিচ্ছি, এতে বড় সংখ্যাগুলো কাছের বেস কেস নিয়েই হিসাব সম্পন্ন করতে পারে যাতে প্রোগ্রামটা অনেক ফাস্ট হয়ে যায়। আর ছোট সংখ্যাগুলো তখন হিসাবও করা লাগবে না! factorial(n) এর মান হিসাব করতে গিয়ে এর আগের সবগুলো ধাপ যদি মনে রাখা সম্ভব হয় তবে factorial(n-x) এর মান আগে থেকেই হিসাব করে মেমরিতে রাখা! এখন শুধু মানটা প্রিন্ট করে নিলেই হচ্ছে। চলো তাহলে প্রোগ্রামটা দেখে আসি-

int temp[100]; 
int factorial(int n) {
    if (n == 0 || n == 1) {
        return 1;
    } else {
        if (temp[n] != 0)
            return temp[n];
        else
            return temp[n] = (n * factorial(n - 1));
    }
}

এখানে আমরা একটি অ্যারে temp[] নিয়ে তাতে প্রত্যেক ধাপের ক্যালকুলেশনগুলো স্টোর করে রাখছি যা পরবর্তি ক্যালকুলেশনে ব্যবহার করে প্রোগ্রামটিকে আরও দ্রুতগতির করে দিচ্ছে!

  • Liked by
  • Fahim
Reply
Loading more replies