সূচিপত্র 

পর্বের শুরুতেই আমরা উদ্ভট একটা প্রোগ্রাম দেখবো। কোডটি রান করার দরকার নেই!

#include <stdio.h>
int main() {
    printf("Hello world.\n");
    main(); // eta khub baaje ekta ovvash.. dekhcho dekho, nije korio na kokhono :p 
}

সবই ঠিক ছিল শুধুমাত্র ৫ নাম্বার লাইনে main() লেখাটা ছাড়া। বল তো এখন কী হবে? কোনো অনুমান? তোমার উত্তর নিশ্চয় নিচের দু’টির মধ্যে একটি।

(১) কম্পাইলেশন এরর দেখাবে কিংবা,

(২) ৫ নাম্বার লাইনে এসে কম্পাইলার আবার ২ নাম্বার লাইনে ফিরে যাবে। অর্থাৎ বারবার Hello world প্রিন্ট হতে থাকবে।

যদি তোমার উত্তর দ্বিতীয়টি হয়, তাহলে অভিনন্দন। এই যে এখানে একটি ফাংশনের মধ্যেই সে ফাংশনটিকে আবার ডাক(call) দিলাম, এ ব্যাপারটিই হল রিকার্শন। অর্থাৎ, রিকার্শন মানে হল নিজের নাম ধরে ডাকাডাকি!

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

#include <stdio.h>
int i=0;
int main() {
    printf("Hello world.\n");
    i++;
    if (i<10) main();
    else return 0;
}

এবার কিন্তু আর ইনফিনিট লুপের সৃষ্টি হবে না! বরং, কম্পিউটার ১০ বার প্রিন্ট করেই থেমে যাবে।

এখানে আমরা যে শর্ত জুড়ে দিলাম, সেটাকে বলা হয় Base Case।

if (i<10) main();
else return 0;

এখন প্রশ্ন হল, রিকার্শন জিনিসটা কখন লাগবে! সহজভাবে বললে এটা আমাদের তখন ব্যবহার করতে হবে, যখন বিভিন্ন শর্তসাপেক্ষে একই কাজ বারবার করতে হয়। লুপের একটা বিকল্প হতে পারে রিকার্শন। যেমন, আমরা ফিবোনাচ্চি সিরিজের কথা বিবেচনা করতে পারি। এই সিরিজটা কীভাবে তৈরি হয় বল তো? এটার মূল লজিক হল, এই সিরিজের প্রতিটা সদস্য এর পূর্ববর্তী দু’টি সদস্যের যোগফল।

এখন প্রশ্ন হল এক্ষেত্রে Base Case (এটা কী বুঝতে না পারলে শুরু থেকে আবার পড়!)? এটা বুঝতে হলে আমাদের চিন্তা করে দেখতে হবে, এমন কোনো সদস্য এই সিরিজে আছে কি না, যা ধ্রুবক অর্থাৎ, কোনো শর্তসাপেক্ষ নয়। অন্য সব সদস্যের ক্ষেত্রে একটি শর্ত (= আগের দু’টির যোগফল) থাকলেও এর ক্ষেত্রে নেই। একটু চিন্তা কর তো।

উত্তর হল, এমন দু’টি সদস্য আমাদের কাছে আছে। ফিবোনাচ্চি সিরিজের প্রথম এবং দ্বিতীয় সদস্য হল যথাক্রমে 0 এবং 1। এ দু’টি সদস্য কনভেনশন অনুসারে ঠিক করা। কারণ এদের ক্ষেত্রে “আগের দু’টি সংখ্যা যোগ” করা যায় না। এর পরবর্তী সকল সদস্য উল্লিখিত শর্ত দিয়ে বের করা সম্ভব। তাহলে এখন যদি আমাদেরকে প্রথম ২০ টি সদস্য বের করতে বলা হয়, আমরা সে কাজটি করে ফেলতে পারি লুপ ব্যবহার করে।

#include <stdio.h>
int main() {
    // prothomei amra fibonacci shonkhar ekta array nibo
    int fibonacci[20];
    // erpor amra amader jana duti shodossho boshiye dibo
    fibonacci[0] = 0;
    fibonacci[1] = 1;
    // erpor amra ekta loop chaliye baki shodossho gula ber korbo
    int i;
    for (i=2; i<20; i++) {
        fibonacci[i] = fibonacci[i-1] + fibonacci[i-2];
        // karon proti ta shodossho tar aager duita shodossher jogfoler shoman
    }
    // ebar print kore dekhi shob thik ache naki!
    int j;
    for (j=0;j<20; j++) {
        printf("%2d. %d\n", j+1, fibonacci[j]);
        // %2d keno likhechi sheta output dekhe na bujhle google theke jene nao ;)
    }
    return 0;
}

কোডটি ঠিক মতই কাজ করার কথা্‌, এবং করবেও। আউটপুটঃ

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

আমাদের প্রথম দু’টি সদস্যের মান আমরা জানি। তাই ওগুলো সেট করে দিব আমরা মেইন ফাংশনেই।

#include <stdio.h>
int fibonacci[20];
int i; // bolo to global e keno? 
int fibo() {
    
}
int main() {
    fibonacci[0] = 0;
    fibonacci[1] = 1;
    for (i=2; i<20; i++) {
        fibo();
    }
    int j;
    for (j=0; j<20; j++) {
        printf("%2d. %d\n", i+1, fibonacci[i]);
    }
    return 0;
}

প্রতিটা ফিবোনাচির মান = তার আগের দু’টি সদস্যের যোগফল

তাহলে আমরা ফাংশনের ভেতরের অংশটাও লিখে ফেলিঃ

#include <stdio.h>
int fibonacci[20];
int i; // bolo to global e keno?
int fibo() {
    fibonacci[i] = fibonacci[i-1] + fibonacci[i-2];
}
int main() {
    fibonacci[0] = 0;
    fibonacci[1] = 1;
    for (i=2; i<20; i++) {
        fibo();
    }
    int j;
    for (j=0; j<20; j++) {
        printf("%2d. %d\n", j+1, fibonacci[j]);
    }
    return 0;
}

/* গ্লোবাল স্কোপে করতে হচ্ছে, কারণ না হলে ফাংশনটি এসব ভ্যারিয়েবল এক্সেস করতে পারবে না! */

আমাদের কাজ প্রায় শেষের দিকে, তবে আমরা রিকার্শনটাই করি নাই এখনো। :p তবে চিন্তার কিছুই নেই, কারণ আমাদের কাজ প্রায় হয়েই গেছে! আমাদের এবার প্রথম লুপে যে কাজটা হচ্ছে, সেটা আমাদের fibo ফাংশনের মধ্যে একটা শর্ত সহ জুড়ে দিতে হবে। শর্ত তো লুপের মধ্যে আছে! শর্ত হল, যতক্ষন i-এর মান 20-এর নিচে থাকবে। তাহলে আমরা মেইন ফাংশনের প্রথম লুপটা আস্তে করে সরিয়ে দিয়ে শর্তটা fibo ফাংশনে লাগিয়ে দি।

#include <stdio.h>
int fibonacci[20];
int i; // bolo to global e keno?
int fibo() {
    fibonacci[i] = fibonacci[i-1] + fibonacci[i-2];
    i++;
    if (i<20) fibo();
}
int main() {
    fibonacci[0] = 0;
    fibonacci[1] = 1;

    int j;
    for (j=0; j<20; j++) {
        printf("%2d. %d\n", j+1, fibonacci[j]);
    }
    return 0;
}

তাও তো কাজ হচ্ছে না! 🙁 আরে হবে কীভাবে? আমরা তো মেইন ফাংশনের মধ্যে fibo ফাংশনটাকে ডাকই দিলাম না, সে নিজেকে ডাকাডাকির সুযোগ পাবে কোথা থেকে! তাহলে আমরা পুরো কোডটি লিখে ফেলি।

#include <stdio.h>
int fibonacci[20];
int i; // bolo to global e keno?
int fibo() {
    fibonacci[i] = fibonacci[i-1] + fibonacci[i-2];
    i++;
    if (i<20) fibo();
}
int main() {
    fibonacci[0] = 0;
    fibonacci[1] = 1;
    fibo();
    int j;
    for (j=0; j<20; j++) {
        printf("%2d. %d\n", j+1, fibonacci[j]);
    }
    return 0;
}

এবার রান করে দেখ। এখনও হচ্ছে না! :'( কারণ আমরা i-এর মান ইনিশিয়ালাইজ করি নাই! আর কথা বাড়াবো না। এবার নির্ভুল কোডটাই দিবঃ

#include <stdio.h>
int fibonacci[20];
int i=2; // bolo to global e keno?
int fibo() {
    fibonacci[i] = fibonacci[i-1] + fibonacci[i-2];
    i++;
    if (i<20) fibo();
}
int main() {
    fibonacci[0] = 0;
    fibonacci[1] = 1;
    fibo();
    int j;
    for (j=0; j<20; j++) {
        printf("%2d. %d\n", j+1, fibonacci[j]);
    }
    return 0;
}

এবার কোডটা রান করলে fibo ফাংশনটা খুব সুন্দর নিজেকে ১৮ বার ডাকাডাকি শেষে আমরা নিচের আউটপুট দেখবো!

যাক, হল তাহলে শেষ পর্যন্ত! ভুলগুলো এ কারণে করলাম, যাতে ভবিষ্যতে Base Case, ইনিশিয়ালাইজেশন – এসব ব্যাপারে অনেক বেশি সতর্ক হয়ে যাও। 🙂

আমরা খুব সহজ একটি ব্যাপার দেখলাম। এবার আমরা আরেকটু গভীরে যাওয়ার চেষ্টা করবো। আমরা এবার ফ্যাক্টরিয়ালের কাজটা করবো রিকার্শনের মাধ্যমে। আমরা লুপের সাহায্যে করলে ব্যাপারটা হত এরকমঃ

#include <stdio.h>
int main() {
    int i,input;
    scanf("%d", &input);
    int fact = 1;
    for (i=input; i>1;i--) {
        fact = fact*i;
    }
    printf("%d! = %d\n", input, fact);
    return 0;
}

/* তবে খেয়াল রাখবে, খুব অল্পতেই ইন্টিজারের সীমা পাড় হয়ে যাওয়ায় এভাবে খুব বড় কোনো সংখ্যার ফ্যাক্টরিয়াল পরিমাপ করা যাবে না। মাত্র ১২! পর্যন্ত মান ঠিকমত আউটপুট আসবে! long long ব্যবহার করলেও খুব বেশি দূর যাওয়া যাবে না। এজন্য স্ট্রিং দিয়ে গুণ করা শিখতে হবে আমাদের। তবে যাক সে কথা। আমরা মূল আলোচনায় ফিরে আসি। */

আমাদের কোডের লুপের কাজটিই আমরা রিকার্শনের মাধ্যমে করবো। এবং এক্ষেত্রে ফ্যাক্টরিয়ালের মানটি রিটার্ন করে দিব।

আমাদের Base Case হল আমরা ততক্ষণ পর্যন্ত ডাকাডাকি করবো, যতক্ষন না গুণক (যেটা দিয়ে গুণ করবো) ১ হয়।  গুণক ১ হয়ে গেলে তখন আমরা ফ্যাক্টরিয়ালের মানটা রিটার্ন করে দিব। আর আমরা কিন্তু এই গুণকটাই ফাংশনের প্যারামিটার হিসেবে নিব।

তাহলে আমরা কঙ্কালটা বানিয়ে ফেলি!

#include <stdio.h>
int ans;
int facto(int i) {
    ans = ans*i;
    i--;
    if (i==1) return ans; // base case 
    else facto(i); 
}

int main() {
    int input;
    scanf("%d", &input);
    ans = 1;
    printf("%d! = %d\n", input, facto(input));
    return 0;
}

ধর এই কোডটা রান করলা এবং ইনপুট দিলা ৫। যা হবে তা হলঃ

• প্রথমে facto ফাংশনে প্যারামিটার যাবে ৫, তখন ans-er মান আছে ১। প্রথমেই ans ৫ দিয়ে গুণ হয়ে যাবে। এরপর প্যারামিটারের মান এক কমবে। এখন i=4, ans=5। যেহেতু i-এর মান ১ না, সেহেতু facto ফাংশন নিজেকেই নিজে ডাক দিবে আবার।
• এবার facto ফাংশনে প্যারামিটার যাবে ৪, এবং কাজ শেষে ans=5*4=20, i=4-1=3। এবং i=১ না হওয়ায় facto ফাংশন আবার নিজেকে ডাক দিবে।
• এবার প্যারামিটার হিসেবে যাচ্ছে ৩। কাজ শেষে ans = 20*3=60, i = 3-1=2। এখনো হয় নি, তাই আবার ডাকাডাকি!
• এবার প্যারামিটার হল ২। কাজ শেষে ans = 120, i=1। এবার যেহেতু i-এর মান 1 হয়ে গিয়েছে, তাই আর কোনো ডাকাডাকি হবে না। ফাংশনটি এবার ডাকাডাকি না করে ans-এর মানটি রিটার্ন করে দিবে! কাজ শেষ!

তবে আমরা যা করেছি, তা না করে অন্যভাবেও কাজটি করা যেত। আমরা জানি 1! = 1। তাহলে আমরা কোডটা লিখতে পারতাম এভাবেঃ

#include <stdio.h>
int ans;
int facto(int i) {
    if (i==1) return 1;
    else return i*facto(i-1);
}

int main() {
    int input;
    scanf("%d", &input);
    ans = 1;
    printf("%d! = %d\n", input, facto(input));
    return 0;
}

এখানে কী হচ্ছে বুঝতে পারছো? :p এবার যদি ৫ ইনপুট দেওয়া হয়, তাহলে

• প্রথমেই প্যারামিটার হিসেবে যাচ্ছে 5। এবং সেটি গিয়ে জিজ্ঞেস করছে প্যারামিটার ১ কি না, ১ না হওয়ায় সেটি বলছে 5*facto(5-1) রিটার্ন করে দিতে।
• কিন্তু এই 5*facto(5-1) এর মধ্যে আরও একবার facto ফাংশনটার ডাক পড়ে গেছে। এবার প্যারামিটার হিসেবে যাচ্ছে 4। সেটি ১ না হওয়ায় ফাংশনটি এবার রিটার্ন করছে 4*facto(4-1)
• এরপরের ডাকে রিটার্ন হচ্ছে 3*facto(3-1)
• এরপরের ডাকে রিটার্ন হচ্ছে 2*facto(2-1)
• এরপরের ডাকে যেহেতু প্যারামিটার ১ হয়ে গিয়েছে, তাই রিটার্ন হচ্ছে ১।

তাহলে পুরো ব্যাপারটা দাঁড়াচ্ছে এমনঃ

ব্যাপারটা না বুঝলে এভাবে সিম্যুলেট করতে পারঃ

এরপরও বুঝতে সমস্যা হলে কমেন্ট সেকশনে জানাও! 🙂

রিকার্শন নিয়ে মোটামুটি ধারণা আমরা পেয়েছি এই পর্বে। তবে জেনে-না জেনে কারণে-অকারণে রিকার্শন ব্যবহার না করাই শ্রেয়!

আর রিকার্শন নিয়ে আরও ভাল মত বুঝতে নিচের লেখাটি পড়তে পারঃ

• রিকার্শনের মাধ্যমে মড্যুলার এক্সপনেন্সিয়েশন