রিকার্সিভ ফাংশনের সৌন্দর্য

ধরো তোমার দুনিয়ায় রিকার্সিভ ফাংশন বলে কিসসু নাই। তুমি মহা শান্তিতে কোড করে দিন পার করতেছো। তোমার একদিন হঠাৎ করে জটিল একটা প্রবলেম সলভ করতে ইচ্ছা করলো। জটিল (!) প্রবলেমটা হচ্ছে ১ থেকে ১০ পর্যন্ত সংখ্যাগুলোকে তুমি প্রিন্ট করতে চাও। এই জটিল প্রবলেমের সহজ সমাধানের জন্য তুমি একটা কোড লিখলে এরকম করেঃ

#include<stdio.h>
void printSeries(int n)
{
    for(int i=1; i<=n; i++)
        printf("%d\n",i);
}
int main()
{
    printSeries(10);
    return 0;
}

চমৎকার ভাবে একটা ফাংশন কল করে তুমি ১ থেকে ১০ পর্যন্ত প্রিন্ট করে ফেললা! তবে এই একই কাজ করার জন্য আরেকটা দারুণ কোড লিখা যায় নিচের মত করেঃ

#include<stdio.h>
void printSeries(int n)
{
    if(n==0)
        return;
    printSeries(n-1);
    printf("%d\n", n);
}
int main()
{
    int res;
    printSeries(10);
    printf("Main Function Done!");
    return 0;
}

কোডটা রান করে দেখো। এটাও ১ থেকে ১০ পর্যন্ত প্রিন্ট করে। কী এমন আছে এই কোডের মধ্যে? আসো লাইন বাই লাইন কোডের ব্যবচ্ছেদ করি!

main function থেকে printSeries(10); কল করা হয়েছে। বুঝলাম এটা একটা ফাংশন। এর মধ্যে ১০ পাঠানো হয়েছে। ফাংশনের কাজ হচ্ছে ১ থেকে ১০ পর্যন্ত প্রিন্ট করে দেখানো। এবার দেখি এই ফাংশনের ভিতরে কী এমন আছে যার কারণে সে লুপ-টুপ ঘুরানো ছাড়াই কাজ করে ফেললো!

ফাংশনের বডির প্রথম লাইনে চেক করা হয়েছে n==0 কিনা? আমরা যেহেতু ১০ দিয়ে কল দিয়েছি তাই এখানে এই IF সত্য হবার কোন কারণ নাই। তাই আপাতত এটা নিয়ে মাথা না ঘামালাম। কোডের ৮ নাম্বার লাইনে দেখ আবার কল করা হয়েছে printfSeries(n-1); ঘটনা কী? মেইন ফাংশন থেকে একবার কল দিলাম ১০ দিয়ে, ফাংশনের ভিতরে দেখি আবার কল দেয়ার কোড লেখা। তেলেসমাতি কান্ড!!! এই লাইনে তাহলে কল হবে printSeries(9) দিয়ে (কারণ, n=10 সুতরাং n-1 = 9)। ফাংশনের বডির মধ্যে বসে আবারো সেই একই ফাংশনকে কল করা হয়েছে।

এখন আপাতত কোডের দিকে মন দিও না। মাথায় জট পাকানোর আগে আসো একটু গফ-সফ করি! :P

তুমি যেহেতু ফাংশন কল বুঝো তাই বলছি আর কি। ফাংশন কল হলে প্রোগ্রামে কী ঘটনা ঘটে জানো? ধরো মেইন ফাংশনটা এক্সিকিউট হচ্ছে। একটা স্ট্যাক থাকে ফাংশনগুলো রাখার জন্য। স্ট্যাক না বুঝলে আপাতত ধরে নাও স্ট্যাক নামক একটা সিডি/ডিভিডি রাখার কেস আছে (যাতে সিডি/ডিভিডি ডিস্কগুলো একটার উপর একটা রাখা যায়)। তো এই স্ট্যাকের মধ্যে প্রোগ্রামে থাকা ফাংশনগুলোকে একটার উপর একটা সাজিয়ে রাখা হয়।

আমাদের মেইন ফাংশনটা কাজ করছে এই মুহুর্তে। তাই স্ট্যাকে মেইন ফাংশনটাকে রাখা হয়েছে। মেইন ফাংশন থেকে মনে করো A() নামক একটা ফাংশনকে কল করা হয়েছে। তখন কিন্তু মেইন ফাংশনের কাজ pause হয়ে থাকবে। কাজ চলতে থাকবে A() ফাংশনের। নতুন এই ফাংশনটাকে স্ট্যাকে রাখা হবে। স্ট্যাকের সিসটেমটাই হচ্ছে এরকম যে, সবার প্রথমে যাকে স্ট্যাকে রাখা হবে সে সবার নিচে থাকবে। আর সবার পরে যাকে রাখা হবে সে উপরে থাকবে। ১০ টা প্লেট একটার উপর একটা রাখলে যেই ঘটনা ঘটে সেটাই স্ট্যাক। তো এই মুহুর্তে আমাদের স্ট্যাকের উপরে আছে A(). উপরে যে থাকবে সে-ই কাজ করতে থাকবে। A() এর ভিতর থেকে আরেকটা ফাংশন কল হল B(). তখন স্ট্যাকে B() কে push করে দেয়া হবে। B() কাজ করতে থাকবে। B() এর কাজ শেষ হলে একে স্ট্যাকের উপর থেকে তুলে ডিলেট করে দেয়া হবে। এখন স্ট্যাকের উপর কে আছে? A() ফাংশন তাই না? এখন A() ফাংশন তার কোন কাজ বাকি থাকলে সেগুলো সেরে নিবে। এটার কাজ শেষ হলে এটাকেও স্ট্যাক থেকে মুছে দেয়া হবে। এখন স্ট্যাকে কে আছে? আমাদের মেইন ফাংশন তাই না? মেইন ফাংশন তার কাজ করতে থাকবে। যখন এর কাজ শেষ হয়ে যাবে তখন প্রোগ্রাম ক্লোজ হবে। স্ট্যাক থেকে একেও মুছে ফেলা হবে। এভাবেই ফাংশনগুলোর কল ম্যানেজ করে আমাদের বোকাসোকা কম্পিউটারগুলো।

• স্ট্যাক ডেটা স্ট্রাকচার সম্পর্কে জানা যাবে এখান থেকে

লক্ষ্য করো, একটার পর একটা ফাংশন কল হচ্ছে। প্রতিটা ফাংশনের ভিতরেই এক বা একাধিক ভেরিয়েবল ডিক্লিয়ার হতে পারে। তার মানে প্রতিটা ফাংশন যখন কাজ করে তখন সে তার জন্য প্রয়োজনীয় মেমরি দখল করে। একটা ফাংশনের ভেরিয়েবল বা ডেটার সাথে কিন্তু অন্য ফাংশনের ডেটার সম্পর্ক থাকে না। অর্থাৎ A() ফাংশনের ভিতরে number নামের একটা ভেরিয়েবল ডিক্লিয়ার করলে B() ফাংশনের ভিতরেও number নামের ভেরিয়েবল ডিক্লিয়ার করতে পারবে। দুইটার মধ্যে কিন্তু কনফ্লিক্ট হবে না। অর্থাৎ ফাংশনগুলো নিজেদের একেকটা জগত তৈরি করে। ততক্ষণই তাদের রাজত্ব স্থায়ী হয় যতক্ষণ ফাংশনটা এক্সিকিউট হতে থাকে। ফাংশনের কাজ শেষ হলেই তাসের ঘরের মত ভেঙ্গে পরে তাদের সংসার। তার ডেটা রাখার জন্য যে সকল মেমরি দখল করা ছিল সেগুলোও ফ্রি হয়ে যায়। Recursive function বুঝার জন্য ফাংশন কল হবার বা স্ট্যাকের আইডিয়া থাকলে একটু সুবিধা হবে। তাই একটু বলে নেয়া।

কোডে ফেরত যাই। মেইন ফাংশন থেকে printSeries(10) দিয়ে যখন ফাংশন কল করা হয়েছে তখন স্ট্যাকে থাকা মেইন ফাংশনের উপরে এই ফাংশনটাকে রাখা হয়েছে। যার ভিতর n নামের একটা ভেরিয়েবল আছে। যার মান 10. ফাংশন বডিতে ঢোকার পরে একই ফাংশনকে যখন printSeries(9) দিয়ে কল করা হল তখন স্ট্যাকের উপরে আবারো একই ফাংশনের আরেকটা instance রাখা হল। যেখানে আগের ফাংশনের মতই n নামের একটা ভেরিয়েবল আছে। যার মান এটার ক্ষেত্রে ৯। আগের ফাংশনের n আর এই ফাংশনের n কিন্তু আলাদা। তাই একটার সাথে আরেকটা কনফ্লিক্ট করবে না। ৯ দিয়ে যখন একই ফাংশনকে আবারো কল দেয়া হল তখন প্রথম লাইনে চেক হল n==0 কিনা? ৯ দিয়ে কল হওয়ায় n এর মান 9 তাই IF এর আন্ডারে থাকা return কাজ করবে না। পরের লাইনে গিয়ে আবার কল হবে printSeries(n-1) বা printSeries(8) দিয়ে। এই ফাংশনের একটা instance আবারো রাখা হবে স্ট্যাকে। এভাবে রাখতেই থাকবে, রাখতেই থাকবে। স্ট্যাকে একটার উপর একটা ফাংশন থাকার মানেই হচ্ছে এই ফাংশনগুলোর কাজ এখনো কমপ্লিট হয় নাই। পরে হলেও এগুলোর কাজ আস্তে আস্তে শেষ করা হবে। প্রতিবার ফাংশন কল হবার সময় কিন্তু ১ করে কমছে। তার মানে কমতে কমতে এক সময় n এর মান দাঁড়াবে 0. স্ট্যাকের একদম উপরে এই ফাংশনকে রাখা হবে। এখন কিন্তু কোডের ৫ নাম্বার লাইনের চেকিং এ ধরা খেয়ে যেতে হবে। অর্থাৎ আমাদের এই IF এর মান সত্য হয়ে যাবে। সত্য হলে এক্সিকিউট হবে return; এর মানে হচ্ছে এই ফাংশন কলের কাজ এখানেই শেষ। ফাংশন বডির পরের লাইনগুলো আর এক্সিকিউট হবে না।

এই ফাংশনের কাজ শেষ এর মানে হচ্ছে একে call stack থেকে বের করে দাও। বের করে দিলে স্ট্যাকের একদম উপরে এখন কোন ফাংশন আছে? 0 এর আগের স্টেটটা আছে তাই না? অর্থাৎ এমন একটা printSeries() আছে যার n এর মান 1. যেহেতু এটা স্ট্যাকের উপরে আছে তাই এখন এর বাকি কাজগুলো শেষ করতে হবে। printSeries() ফাংশনের বডি হচ্ছে 4 থেকে 11 নাম্বার লাইন পর্যন্ত। স্ট্যাকের উপরে থাকা ফাংশন কিন্তু ৮ নাম্বার লাইনের কাজ শেষ করে রেখেছে। কারণ ৮ নাম্বার লাইনে এসেই সে printSeries(0) কল করেছিল। অতএব সে এখন ৯-১১ নাম্বার লাইনের কাজগুলো করবে। ১০ নাম্বার লাইনে দেখতে পাচ্ছি n এর মান প্রিন্ট করতে বলা হয়েছে। এই ফাংশনের n এর মান হচ্ছে 1. তাই সে 1 প্রিন্ট করবে। প্রিন্ট হবার পর এই ফাংশনের আর কোন কাজ বাকি থাকবে না। সুতরাং এই ফাংশন ইন্সটেন্সকেও স্ট্যাক থেকে বহিস্কার করা হবে!

এখন স্ট্যাকের উপরে আছে printSeries(2) এই ফাংশনটা। এই ফাংশনও কিন্তু ৮ নাম্বার লাইনের কাজ সেরে ফেলেছিল আগেই printSeries(1) কল দেয়ার মাধ্যমে। এখন বাকি কাজ করবে ১০ নাম্বার লাইনে n এর মান 2 প্রিন্ট করার মাধ্যমে। এরপর একেও স্ট্যাক থেকে বিদায় করা হবে। এভাবে এক সময় একে একে ১০ পর্যন্ত প্রিন্ট করা হবে। ১০ প্রিন্ট হবার পর সেটাকে বিদায় করা হবে। এখন স্ট্যাকের উপরের পজিশনে কে থাকবে? আমাদের মেইন ফাংশন! মেইন ফাংশনের কাছে যখন রিটার্ন করা হবে তখন কিন্তু স্ট্যাকে একটাই ফাংশন থাকবে। সেটা মেইন ফাংশনই! মেইনে রিটার্ন করে বাকি থাকা কাজগুলো করবে। অর্থাৎ ১৯ নাম্বার লাইনে থাকা printf() এর কাজ করবে। এভাবেই ১ থেকে ১০ পর্যন্ত প্রিন্ট করা হয়েছে।

ব্যাপারটা কি খুব বেশি গোলমেলে? মনে হয় না! যদি বুঝে গিয়ে থাকো তাহলে তোমার রিকার্সিভ ফাংশন বুঝা হয়ে গেছে! অভিনন্দন তোমাকে! :)

Recursion বা রিকার্সিভ ফাংশন এর সংজ্ঞা হিসেবে বলা হয় “এটা এক ধরনের ফাংশন যে কিনা নিজেই নিজেকে কল করে একেকটা স্বতন্ত্র ফাংশনের instance তৈরি করে।” অর্থাৎ, নিজের মত বৈশিষ্ট্যমন্ডিত ও একই রকম কর্মক্ষম আরো ফাংশনের কপি বানাতে পারে এমন ফাংশনই হচ্ছে রিকার্সিভ ফাংশন। রিকার্সিভ ফাংশন উদ্দেশ্য হচ্ছে আমরা যেই কাজটা করতে চাই বা যেই প্রবলেমটা সলভ করতে চাই সেটাকে ছোট ছোট প্রবলেমে ভাগ করা। প্রতিটা ছোট প্রবলেমকে সলভ করা (ছোট প্রবলেম সলভ করা সহজ তাই না?)। এরপর ছোট প্রবলেমের সলিউশনগুলোকে মার্জ করা বা ছোট প্রবলেমগুলোর সলিউশনের উপর ভিত্তি করে মূল সলিউশন বের করা।

আমাদের প্রবলেম ছিল ১ থেকে ১০ প্রিন্ট করা। ফাংশনে পাঠানো হয়েছিল ১০। আমরা এটাকে ছোট অংশে কিভাবে ভাংতে পারি? আমি বলতে পারি যে, আমি ১০ প্রিন্ট করব। বাকিগুলা প্রিন্ট করব না। ১ থেকে ৯ পর্যন্ত প্রিন্ট করার দায়িত্ব আমি তোমাকে দিলাম। তুমি করলা কী, শুধু ৯ প্রিন্ট করলা। ১ থেকে ৮ প্রিন্ট করার দায়িত্ব রামকে দিলা। রাম ৮ প্রিন্ট করে ১ থেকে ৭ এর দায়িত্ব দিল সামকে। সাম ৭ প্রিন্ট করে ১ থেকে ৬ এর দায়িত্ব দিল যদুকে। যদু ৬ প্রিন্ট করে ৫ পাঠালো মধুর কাছে। এভাবে আমি ছোট্ট একটা কাজ করে বাকি কাজগুলো রাম-সাম-যদু-মধুকে দিয়ে করিয়ে নিলাম অর্থাৎ আমার বড় প্রবলেমটাকে আমি ছোট ছোট টুকরা করে ভাগ করে দিলাম। ছোট ছোট অংশ সলভ হল, তার ফলে আমার বড় প্রবলেমটাই আলটিমেটলি সলভ হল! এটাই রিকার্সিভের মজা!

লুপ দিয়ে করা যায় এমন সব প্রবলেমই রিকার্সন দিয়ে করা যায়। তাহলে লুপ ব্যবহার না করে রিকার্শন কেন ব্যবহার করব? কারণ রিকার্সনের ক্ষেত্রে আমাদের কোড অনেক সময়ই কম লিখতে হয়। রিকার্সন ফাংশন কল হওয়া কখন থামাতে হবে সেটা বের করে প্রবলেমটা ছেড়ে দেয়া যায় ফাংশনের উপর। আমাদের কাজ খানিকটা কমিয়ে দেয়। পরবর্তীতে বিভিন্ন অ্যালগরদিম ইমপ্লিমেন্ট করার সময়ও রিকার্সিভ ফাংশন প্রয়োজন হবে ঝামেলা কমানোর জন্য। রিকার্সন কল হওয়া কখন থামাতে হবে সেটা সব চেয়ে জরুরি বিষয়। যেই case এর জন্য ফাংশল কল হওয়া বন্ধ হয়ে যায় বা return; স্টেটমেন্ট কাজ করে সেই কেসকে বলা হয় base case. ফাংশন বডির শুরুতেই তাই বেজ কেসের চেক রাখতে হয়। বেজ কেস ঠিক মত চেক না করলে infinite loop এর মধ্যে পড়ে গিয়ে ফাংশন কল হতেই থাকবে। তাই সাধু সাবধান!

আজকে আর কোন জ্ঞান গর্ভ আলোচনা করব না। এবার সময় নিজেদের প্র্যাক্টিস করার। আমি ১ থেকে ১০ প্রিন্ট করেছি। তোমার কাজ এখন ১০ থেকে ১ প্রিন্ট করা। ২-১ জায়গায় একটু চেঞ্জ করলেই কাজ হয়ে যাবে। তুমি কি আসলেই কিছু বুঝেছ? কিসসু না বুঝে থাকলে কমেন্ট করে জানাও। আমি লেখাটাকে আরো মোডিফাই করার চেষ্টা করব। তুমি কি এই প্রথম রিকার্সন বুঝলে? তাহলেও জানাও!

লেখাটি প্রথম প্রকাশিত হয়েছে আমার ব্যক্তিগত ব্লগে

পরের পর্বটি পড়া যাবে এখান থেকে।

আপনার মন্তব্য, পরামর্শ, সমালোচনার জন্য অধীর আগ্রহে অপেক্ষা করছি… :)