রিকার্সিভ ফাংশনের সৌন্দর্য – ২ [Factorial]

Post updated on 28th November, 2016 at 01:32 pm

আগের পর্বে ফাংশন ও রিকার্সিভ ফাংশন সম্পর্কে ব্যাসিক ধারণা দেয়া হয়েছে। তুমি যদি মিস করে থাকো তাহলে আগে ঐ পর্বটা পড়ে নিতে পার। এই পর্বে তাত্ত্বিক কোন কথাবার্তা তেমন থাকবে না। কমন ১ টা উদাহরণ উল্লেখ করে সেগুলোর কোডগুলো ব্যাখ্যা করা হবে। তুমি যদি আগের পর্বটা বুঝে থাকো তাহলে এই পর্ব বুঝতে কোন সমস্যা হবে না।

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

ধরো আমি তোমাকে 5! বের করতে বললাম। এর ফলাফল হবে 1 * 2 * 3 * 4 * 5 = 120. ৫ এর ফ্যাক্টরিয়াল বের করার জন্য আমরা ১ এর সাথে ২ গুণ করেছি, গুণফলের সাথে ৩ গুণ করেছি এভাবে ৫ পর্যন্ত গুণ করেছি। অর্থাৎ ১ থেকে ৫ পর্যন্ত সবগুলো সংখ্যাকে গুণ করে আমরা ৫ এর ফ্যাক্টরিয়ালের মান পেয়েছি। এটাকে একটু উল্টিয়ে বলতে পারি, ৫ থেকে ১ পর্যন্ত সকল সংখ্যার গুণফলই হচ্ছে ৫ এর ফ্যাক্টরিয়াল। অর্থাৎ, 5 * 4 * 3 * 2 * 1 = 120. একটু লক্ষ্য করো, 5 * 4 * 3 * 2 * 1 এর 5 কে বাদ দিলে দাঁড়ায় 4 * 3 * 2 * 1, যা 4! এর সমাধান নির্দেশ করে। অর্থাৎ 5! = 5 * 4!. বুঝতে কোন সমস্যা? সমস্যা হলে এই প্যারাটা আবারো পড়।

5! = 5 * 4 * 3 * 2 * 1, এটাকে লিখা যায় 5! = 5 * !4

4! = 4 * 3 * 2 * 1, এটাকে লিখা যায় 4! = 4 * 3!

3! = 3 * 2 * 1, এটাকে লিখা যায় 3! = 3 * 2!

2! = 2 * 1, এটাকে লিখা যায় 2! = 2 * 1!

1! = 1

এর থেকে বুঝতে পারছি যে কোন একটা সংখ্যার ফ্যাক্টরিয়ালের মান তার আগের সংখ্যার ফ্যাক্টরিয়ালের মানের উপর নির্ভর করছে। এটার জন্য রিকার্সিভ কল হবে এমন যে, আমার ৫ এর ফ্যাক্টরিয়াল জানা দরকার। কিন্তু আমি ৫ এর ফ্যাক্টরিয়াল জানি না। আমি জানি আমাকে যদি কেউ 4 এর ফ্যাক্টরিয়াল বের করে দেয় তাহলে সেই মানের সাথে ৫ গুণ করলে আমি ৫ এর ফ্যাক্টরিয়াল পেয়ে যাব। তাই আমি তোমাকে বললাম ৪ এর ফ্যাক্টরিয়াল বের করে দিতে। তুমি আবার তোমার বন্ধুকে বললে ৩ এর ফ্যাক্টরিয়াল বের করে দিতে। সে আবার আরেক জনকে বলল ২ এরটা বের করে দিতে। সে আবার আরেক জনকে বলল ১ এর ফ্যাক্টরিয়াল বের করে দিতে। লাস্টের জন ১ এর ফ্যাক্টরিয়াল বের করে আগের জনকে পাঠালো ১। সে আবার এই ১ এর সাথে ২ গুণ করে তোমার বন্ধুর কাছে পাঠালো ২। তোমার বন্ধু এবার ২ এর সাথে ৩ গুণ করে ৬ পাঠিয়ে দিল তোমার কাছে। তোমার হাতে এসে পৌঁছেছে 3! এর মান (৬)। এটাকে 4! বানানোর জন্য তুমি এর সাথে ৪ গুণ করে আমার কাছে পাঠালে। আমি পেয়ে গেলাম 4! = 24. এটাকে এখন আমি 5 দিয়ে গুণ করে পেয়ে যাব 120. আর এটাই 5! এর মান। তাহলে আমরা কী করেছি এখানে? পুরো প্রসেসটা আমি একা না করে ছোট ছোট দায়িত্ব ভাগ করে দিয়েছি অন্যদের মাঝে। এরপর সেগুলোর সমন্বয়ে মূল রেজাল্ট পেয়েছি।

এখন নিচের কোড দেখ। আশা করি বুঝতে কোন সমস্যা হবে না।

#include<stdio.h>

int factorial(int num)
{
    if(num<=1)
        return 1;

    return num*factorial(num-1);
}

int main()
{
    int n, f;

    printf("Enter a number:\n");
    scanf("%d", &n);

    f = factorial(n);

    printf("Value of %d! is: %d\n", n, f);

    return 0;
}

ফাংশনের শুরুতে বেজ কেস চেক করা হয়েছে। আমরা ৫ থেকে উপরের দিকে উঠতে উঠতে কখন থামব? যখন নাম্বারটা ১ হয়ে যাবে। কারণ ৫ থেকে ১ পর্যন্ত সকল সংখ্যার গুণফল বের করতে হবে। বেজ কেসে তাহলে কিন্তু if(num==1) return 1; করে দিলেই পারতাম তাই না? তাহলে কিন্তু একটা কেসের ক্ষেত্রে সমস্যা হত। যদি ইনপুট হিসাবে শূণ্য দেয়া হয় তাহলে কিন্তু এই ফাংশন কাজ করবে না। তাই if(num<=1) return 1; দেয়া হয়েছে যেন শূণ্য ইনপুট হলেও ১ রিটার্ন করে। কারণ 0! = 1.

num এর মান যদি ১ এর চেয়ে বড় হয় তাহলে বেজ কেসের কনডিশন মিথ্যা হবে। তাই এর পরের লাইন return num*factorial(num-1); এক্সিকিউট হবে। এই লাইনের মানে হচ্ছে, যদি একে ৫ দিয়ে কল দেয়া হয় তাহলে সে ৫ এর সাথে গুণ করতে বলছেfactorial(num-1) বা factorial(4) এর মান। এখনই কিন্তু 5! বের হবে না। যেহেতু factorial(4) কল হয়ে গেছে তাই এখন 4 এর ফ্যাক্টরিয়াল বের করার জন্য আবার ফাংশন কল হবে। সেই ফাংশন কল রিটার্ন করবে 4*factorial(3). এরপরের ফাংশন রিটার্ন করবে 3*factorial(2), এরপর 2*factorial(1)। factorial(1) কল হলে এটা বেজ কেসে আটকে যাবে। এটা আর নতুন কোন ফাংশন কল করবে না। সরাসরি আগের ফাংশনের কাছে ১ রিটার্ন করে দিবে। সেই ফাংশন 2*1=2 রিটার্ন করবে তার আগের ফাংশনের কাছে। সে তার আগের ফাংশনের কাছে রিটার্ন করবে 3*2=6. সে আগের ফাংশনের কাছে পাঠাবে 4*6=24 এবং ফাইনাল্যি মেইন ফাংশনের কাছে রিটার্ন হবে 5*24=120.

ফ্যাক্টরিয়াল বের করার সময় ইনপুট একটু বড় হলেই কিন্তু ইন্টিজারের রেঞ্জ অভারফ্লো করবে। এটা মাথায় রেখো।

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