রিকার্সিভ ফাংশনের সৌন্দর্য – ৪ [Fibonacci Series]

রিকার্সিভ ফাংশনের সাহায্যে Fibonacci Series এর n-তম পদ বের করার পদ্ধতি এই পোস্টে দেখানো হবে। শুরুতে একদম সোজাসাপ্টা ইমপ্লিমেন্টেশন দেখাব সহজে বুঝার সুবিধার্থে। এরপর আমরা দেখব Dynamic Programming (DP) এর কনসেপ্ট কাজে লাগিয়ে কিভাবে এই কোডটাকে ইমপ্রুভ করে execution time কমানো যায়। সব শেষে এই improved program এর কয়েকটা ভার্সন দেখব কোডের সাইজ একটু কমিয়ে আনার জন্য। রিকার্সিভ ফাংশনের সৌন্দর্য সিরিজের প্রথম, দ্বিতীয় ও তৃতীয় পোস্টটা পড়া থাকলে, নতুনদের জন্য আজকের এই লেখাটি বুঝতে বেশি সুবিধা হবে।

ফিবোনাচ্চি ধারা (Fibonacci Series) কী?

এটা অসীম সংখ্যক সংখ্যার একটা সিরিজ বা ধারা। যেই সিরিজের প্রথম পদটি হচ্ছে ‘0’ (zero) এবং দ্বিতীয় পদটি ‘1’ (one). আর পরবর্তী যে কোনো পদ তার আগের দুইটি পদের যোগফলের সমান। অর্থাৎ, ফিবোনাচ্চি সিরিজের পাশাপাশি যে কোনো দুইটি পদ যোগ করলে এর পরের পদটি পাওয়া যায়।

ফিবোনাচ্চি ধারার প্রথম দুইটি পদের কথা উপরের সংজ্ঞার মাধ্যমে আমরা জানতে পারলাম। তাহলে সংজ্ঞানুযায়ী ফিবোনাচ্চি সিরিজের তৃতীয় পদটা কী?

3rd item = 1st item + 2nd item

সুতরাং তৃতীয় পদটি হবে 0+1 = 1.

Fibonacci series এর প্রথম দশটি পদ হচ্ছেঃ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34

তুমি চাইলেই কিন্তু 11th আইটেমটা বের করতে পার। কিভাবে? খুব সোজা! 9th আর 10th আইটেম যোগ করলেই 11th আইটেমটা পাওয়া যাবে। তো 11th আইটেমটা হচ্ছে 21 + 34 = 55

আচ্ছা! তাহলে ফিবোনাচ্চি সিরিজের n-তম পদটা আমরা কিভাবে বের করতে পারি? n-তম পদের আগের দুইটা পদ যদি কোনো ভাবে বের করা যায় তাহলেই কিন্তু n-তম পদটা বের করা যাবে। তাই না? সেটাকেই নিচের মত করে লেখা যায়ঃ

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

ধরো n=11. তাহলে উপরের এই জেনালেল ফর্মুলাতে n এর মান বসিয়ে পাইঃ

F(11) = F(11-1) + F(11-2)

=> F(11) = F(10) + F(9)

=> F(11) = 34 + 21 [10th item = 34, 9th item = 21]

=> F(11) = 55

এভাবে আমরা ফিবোনাচ্চি সিরিজের যে কোনো পদ বের করতে পারি।

C Program for n-th item of Fibonacci Series

আমরা এখন দেখব কিভাবে ফিবোনাচ্চি সিরিজের n-তম বের করা যায়, তার সি প্রোগ্রাম। বুঝতেই পারছ, প্রোগ্রামটি Loop ও Recursive function উভয় মাধ্যমেই করা সম্ভব। আমরা প্রথমে লুপের সাহায্যে এটা বের করব। এরপর রিকার্সিভ ফাংশন দিয়ে বের করা দেখব।

Fibonacci Series – Iterative Way (using Loop)

#include<stdio.h>

int fiboOfNthItem(int n) {

    if(n==1) return 0;
    if(n==2) return 1;

    int a = 0, b = 1, sum, i;

    for(i=3; i<=n; i++) {
        sum = a + b;

        a = b;
        b = sum;
    }

    return sum;
}

int main() {

    int i, n;

    scanf("%d", &n);

    for(i=1; i<=n; i++) {
    	printf("%d ", fiboOfNthItem(i));
    }

    printf("\n");

    return 0;
}

আমরা এখানে একটা ফাংশন বানিয়েছি। যেই ফাংশনে n এর মান পাঠালে ফাংশনটি ফিবোনাচ্চি সিরিজের n-তম পদটি return করে। main() ফাংশন থেকে আমরা n এর মান ইউজারের থেকে ইনপুট নিচ্ছি। এরপর লুপ চালিয়ে n সংখ্যক বার fiboOfNthItem() ফাংশনটি কল করেছি। লুপটি চলছে 1 থেকে n পর্যন্ত। ফলে 1 থেকে n পর্যন্ত সবগুলো পদ পাশাপাশি প্রিন্ট করে দেখানো হচ্ছে। ফিবোনাচ্চি সিরিজের সংখ্যাগুলো বের করার মূল কাজটা হচ্ছে আমাদের ফাংশনের ভিতরে।

ফাংশনের শুরুতে আমরা চেক করেছি n=1 বা n=2 কিনা। এটা কেন করলাম? কারণ আমরা ফিবোনাচ্চি সিরিজের প্রথম দুইটা পদ জানি। আর এগুলো ফিক্সড। তাই সিরিজের ১ম আর ২য় পদ বের করার জন্য n=1 OR n=2 দিয়ে ফাংশন কল করলে আমরা কোনো হিসাব নিকাশ ছাড়াই বলে দিব ১ম পদ 0, ২য় পদ 1. যদি ফাংশনের শুরুতে থাকা প্রথম দুইটা IF checking এর কোনোটা সত্য হয় তাহলে ঐ লাইনেই ফাংশনটা integer result রিটার্ন করবে। ফাংশনের পরের লাইনগুলো আর execute হবে না।

যদি n এর মান ২ এর চেয়ে বড় কোনো নাম্বার পাঠানো হয় তাহলে কী ঘটবে? তখন ফাংশনের প্রথম দুইটা IF block মিথ্যা হবার কারণে কোনো কিছু রিটার্ন করবে না। ফলে পরের লাইনগুলো এক্সিকিউট হবে। আর লুপ এর ভিতর a, b এর যোগফল swap করে করে নির্দিষ্ট ফিবোনাচ্চি পদটা বের করা হবে।

• দুটি সংখ্যা Swap করার তিনটি পদ্ধতি সম্পর্কে জানা যাবে এখান থেকে

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

Fibonacci Series – Recursive Way (simple implementation)

Iterative way তে যেই কোড ছিল সেই কোডের fiboOfNthItem() ফাংশনের ভিতরের কোড সামান্য পরিবর্তন করা হয়েছে। main() function টা একই থাকায় সেটাকে আর উল্লেখ করলাম না।

int fiboOfNthItem(int n) {

    if(n==1) return 0;
    if(n==2) return 1;

    return fiboOfNthItem(n-1) + fiboOfNthItem(n-2);
}

আগের কোডের ফাংশনের শুরুর ২ টা লাইন এখানেও অপরিবর্তিত রয়েছে। কারণ এক্ষেত্রেও আমরা জানি ফিবোনাচ্চি সিরিজের ১ নাম্বার পদ ০, আর ২ নাম্বার পদ ১। তাই n এর মান 1 বা 2 পেলে ফাংশন চোখ বন্ধ করে রেজাল্টটা রিটার্ন করে দিবে। এই দুইটা IF block এর চেকিং হচ্ছে আমাদের রিকার্সিভ ফাংশনের base case. অর্থাৎ যেই case টি সত্য হলে ফাংশনটি আবার নিজেকে কল করবে না বরং ফাংশনের কাজ শেষ করবে।

কিন্তু যদি ৩ বা ৪ দিয়ে ফাংশন কল করা হয় তখন কী ঘটবে? তখনই আমাদের ফাংশন রিকার্সিভ ওয়েতে আমাদেরকে কাঙ্খিত রেজাল্ট এনে দিবে।

এবার নজর দেয়া যাক ফাংশনের তৃতীয় লাইনে। প্রথম দুইটা লাইনের IF block মিথ্যা হলেও তৃতীয় লাইনটা এক্সিকিউট হবার সুযোগ পাবে। এই লাইনে কী করা হচ্ছে? রিটার্ন করা হচ্ছে F(n-1) ও F(n-2) এর মান। অর্থাৎ এই লাইনে এসে এই ফাংশন আবার নিজেই নিজেকে কল করছে অন্য আরেকটি ভ্যালু দিয়ে!

ধরা যাক, আমরা সিরিজের চতুর্থ পদের মান জানতে চাই। main() function থেকে কল করা হলো fiboOfNthItem(4) [উপরের ছবির node-1 এটা]. n এর মান ১ বা ২ না হওয়ায় ফাংশনের প্রথম দুইটা লাইন থেকে কিছুই রিটার্ন করা হবে না। তৃতীয় লাইনে এসে রিটার্ন করা হবে fiboOfNthItem(n-1) ও fiboOfNthItem(n-2) এর যোগফল। এর মানে দাঁড়াচ্ছে মেইন ফাংশন প্রথমে fiboOfNthItem() ফাংশনের কাছে জানতে চাচ্ছে “ও বাপু! ফিবোনাচ্চি সিরিজের 4 নাম্বার পদটা কী?” ফাংশনের ভিতরে প্রথম আর দ্বিতীয় পদ ছাড়া আর কোনো পদের হদিস নাই! তাই ফাংশনটা মেইন ফাংশনের কাছে রিটার্ন করে দিল fiboOfNthItem(n-1) + fiboOfNthItem(n-2). অর্থাৎ সে বলতে চাচ্ছে 4 নাম্বার পদের মান সরাসরি আমি জানি না। তবে এইটুকু জানি এর মান হবে এর আগের দুই পদের মানের যোগফলের সমান। (সে মনে মনে বলছে) আমাকে যদি কেউ 4 নাম্বার পদের আগের দুইটা পদ এনে দেয় তাহলেই আমি মেইন ফাংশনকে 4 নাম্বার পদটা রিটার্ন করব। সে যখন এসব বলতে বলতে return fiboOfNthItem(n-1) + fiboOfNthItem(n-2);  এক্সিকিউট করল তখন কিন্তু actually মেইন ফাংশনের কাছে কোনো ভ্যালু রিটার্ন হয় নাই। কারণ এই এক্সিকিউশনের মধ্যে দুইটা ফাংশন কল করা হয়েছে। 4 দিয়ে কল করা এই ফাংশন থেকে অরিজিনাল রেজাল্ট তখনই রিটার্ন হবে যখন fiboOfNthItem(3) [here, n=4-1=3] ও  fiboOfNthItem(2) [here, n=4-2=2] উভয় ফাংশনই তাদের রেজাল্ট রিটার্ন করবে এবং রেজাল্ট দুটিকে যোগ করা হবে।

তো যেহেতু ফাংশনের তৃতীয় লাইনে এসে আবার ঐ ফাংশনটাকেই অন্য দুইটা ভ্যালু দিয়ে কল করে রেজাল্ট জানতে চাওয়া হয়েছে তাই এখন পরের ফাংশন কলগুলো বেশি প্রায়োরিটি পাবে। কারণ ফাংশনগুলো যখন কল করা হয় তখন সেগুলোকে একটা স্ট্যাকের মধ্যে রাখা হয়। এ ব্যাপারে আগের পোস্টগুলোতে বিস্তারিত বলা হয়েছে। তৃতীয় লাইন থেকে যখন কল করা হলো fiboOfNthItem(n-1) তখন আসলে ফাংশন প্যারামিটারে কী পাঠানো হয়েছ? এই ফাংশন কলের প্যারামিটার হিসাবে পাঠানো হয়েছে 4-1 = 3. অর্থাৎ এই কলের মাধ্যমে ফিবোনাচ্চি সিরিজের ৩ নাম্বার পদ জানতে চাওয়া হয়েছে (খেয়াল করো ছবিতে দেখানো node-2 এর প্রতি)। এই ফাংশন যখন এক্সিকিউট হওয়া শুরু হলো তখনও দেখবে প্রথম দুইটা IF block মিথ্যা। তাই এই [node-2] ফাংশনের তৃতীয় লাইনে এসে আবার কল করা হবে ফাংশন দুটিকে। ৩ নাম্বার পদটা জানার জন্য দরকার হবে ১ ও ২ নাম্বার পদ। তাই এই ফাংশনের তৃতীয় লাইনে কল করা হচ্ছে fiboOfNthItem(3-1) + fiboOfNthItem(3-2). লক্ষ্য করো node-3 ও node-4 এর দিকে। এই ফাংশন দুটি যখন এক্সিকিউট হওয়া শুরু হবে তখন কী ঘটবে? প্রথমটার ক্ষেত্রে সত্য হবে দ্বিতীয় IF আর দ্বিতীয়টার ক্ষেত্রে সত্য হবে function এর প্রথম IF. কারণ প্রথম ফাংশনে প্যারামিটার পাঠানো হয়েছে ২ আর পরেরটায় ১. তাহলে এরা দুইজন আলাদা আলাদা ভাবে রিটার্ন করবে যথাক্রমে 1 ও 0. এই যে দুইটা মান পাওয়া গেল এটা কার ফলাফল? এটা হচ্ছে দ্বিতীয় দফায় [node-2] fiboOfNthItem(3) কল করার ফলাফল। তার মানে হচ্ছে fiboOfNthItem(4)  কল করার সময় যে তৃতীয় লাইনটা এক্সিকিউট হচ্ছিল তার প্রথম ফাংশনের রেজাল্ট পাওয়া গেল 1+0 = 1. এই ভাবে দ্বিতীয় ফাংশনটি কল করা হয়েছিল fiboOfNthItem(2) দিয়ে (node-5)। এটার ফলাফল আসার পর দুটিকে যোগ করে fiboOfNthItem(4) এর রেজাল্ট হিসাবে মেইন ফাংশনের কাছে রিটার্ন করা হবে।

node-5 এ fiboOfNthItem(2) যখন কল করবে রেজাল্ট কী আসবে? রেজাল্ট আসবে 1; কারণ ফিবোনাচ্চি সিরিজের দ্বিতীয় পদের মান 1.

এখন প্রথম যে ফাংশনটা কল করা হয়েছিল 4 দিয়ে (node-1) সেটার তৃতীয় লাইনে ২টা সংখ্যা এসে উপস্থিত। প্রথমটা হচ্ছে সিরিজের ৩ নাম্বার পদ (যা এসেছে node-2 থেকে), আর দ্বিতীয়টা হচ্ছে সিরিজের ২ নাম্বার পদ (যা এসেছে node-5 থেকে)। এখন এদেরকে যোগ করে 1+1=2 রিটার্ন করা হবে মেইন ফাংশনের কাছে। এটা কততম পদ রিটার্ন হচ্ছে? চতুর্থ পদ! অর্থাৎ এতক্ষণে node-1 এর কাজ সম্পূর্ণ ভাবে শেষ হয়েছে।

রিকার্সিভ ফাংশনের সৌন্দর্য এই সিরিজের আগের লেখাগুলোতে বলা হয়েছে যে রিকার্সিভলি কোনো একটা প্রবলেমকে সলভ করার জন্য আমরা প্রবলেমটাকে ক্ষুদ্র ক্ষুদ্র ভাবে ভাগ করি। ক্ষুদ্র ক্ষুদ্র প্রবলেম সলভ করা সহজ। এই ক্ষুদ্র ক্ষুদ্র সলিউশনগুলোকে একত্রিত করলে পুরো প্রবলেমটাই সলভ হয়ে যায়। একটা উদাহরণ দেয়া যাক। ধরো, তুমি তোমার গ্রামে ১০০ লিটার পানি ধারণ করতে পারে এমন একটা হাউজ/চৌবাচ্চা বানিয়েছ। এটাকে পানি দিয়ে পূর্ণ করতে হবে। এত পানি তোমার কাছে নাই। তুমি ১০০ লিটার পানি বহন করতে পারে এমন একটা গাড়ি ভাড়া করে চেয়ারম্যান সাহেবের কাছে পাঠিয়ে দিলা। চেয়ারম্যান সাহেবের কাছেও এই পানি নাই। তিনি ৫০ লিটারের ২টা গাড়ি ভাড়া করে তার এলাকার দুইজন মেম্বারের কাছে পাঠিয়ে দিলেন। উভয় মেম্বার আবার ২৫ লিটারের ২টা করে গাড়ি ভাড়া করলেন। পাঠিয়ে দিলেন তাদের ২ নেতার কাছে। নেতারা আবার তাদের কাছে আসা পানির ডিমান্ডকে দুই ভাগ করে কর্মীদেরকে সংগ্রহ করতে বললেন। এতে দেখা যাবে কর্মী লেভেলে প্রতি কর্মী হয়ত ৫-৬ লিটার করে পানি এনে নেতার গাড়িতে জমা দিবে। এতে কিছুক্ষণের মধ্যেই নেতাদের ২৫ লিটারের গাড়ি ভরে যাবে। তারা এই পানি এনে ঢেলে দিবে মেম্বারের ৫০ লিটারের গাড়ির ট্যাংক এ। এতে উভয় মেম্বারের ৫০ লিটারের গাড়ি ভরে যাবে। তারা এবার গাড়ি নিয়ে ব্যাক করবে চেয়ারম্যানের কাছে। চেয়ারম্যানের বাড়িতে দাঁড়িয়ে থাকা ১০০ লিটারের গাড়িতে তাদের ৫০ লিটারের দুই গাড়ি পানি ঢালা হবে। এরপর সেই গাড়ি ১০০ লিটার পানি এনে তোমার হাউজে ঢেলে দিবে। দেখো! ১০০ লিটার পানি কিন্তু তোমার ঘুরে ঘুরে সংগ্রহ করতে হয় নাই। ১০০ লিটারের প্রবলেমটাকে আমরা ২০ জন কর্মীর মাঝে ভাগ করে দিয়েছি। ২০ জনকে বলা হয়েছে ৫ লিটার করে পানি আনতে। ৫ লিটার পানি আনা সহজ। ধাপে ধাপে পানি আনার কমান্ডটা ২০ জনের কাছে পৌঁছেছে, একই ভাবে তারা পানি সহ return করেছেও ধাপে ধাপে। এতে ১০ লিটার, ২০ লিটার, ৫০ লিটার এবং ১০০ লিটার পানি পর্যায়ক্রমে জমা হয়েছে। এটাই রিকার্সিভ ওয়েতে একটা প্রবলেমকে ভেঙে ক্ষুদ্র ক্ষুদ্র প্রবলেমে রূপান্তর করা।

Fibonacci Series এর রিকার্সিভ কলের পুরো ব্যাপারটা উপরের ছবির সাথে মিলিয়ে শুরু থেকে শেষ পর্যন্ত আবার একটু ভাবো। তাহলে ফাংশন কলগুলো ভিজুয়ালাইজ করতে সহজ হবে। তুমি যদি মনে মনে এই একটা ফাংশন থেকে আবার ঐ ফাংশনকেই আরেকটা ভ্যালু দিয়ে কল করা হচ্ছে, আগের ফাংশন স্ট্যাকে pause হয়ে থাকছে এই বিষয়গুলো ভিজুয়ালাইজ না করতে পার তাহলে ঠিক আয়ত্তে আসবে না বিষয়গুলো। প্রয়োজনে ইউটিউবে সার্চ করতে পার রিকার্সিভ ফাংশনের ভিডিও দেখার জন্য।

Fibonacci Series – Recursive Way (Dynamic Programming implementation)

উপরে যেই রিকার্সিভ ফাংশনটা দেয়া আছে সেই ফাংশনকে কাজে লাগিয়ে ১ থেকে ২০ পর্যন্ত ফিবোনাচ্চি সিরিজ প্রিন্ট করলে তেমন একটা সমস্যা চোখে পড়বে না। কিন্তু তুমি যদি ৪০ বা ৪৫ ইনপুট দাও তাহলে দেখবে আউটপুট আসতে অনেক সময় নিচ্ছে। আমার ল্যাপটপে গড়ে ১৫ সেকেন্ড সময় লাগছে ফিবোনাচ্চি সিরিজের প্রথম ৪৫ টা পদ প্রিন্ট করার জন্য। এর কারণ কী?

কারণ হচ্ছে আমরা ৪৫টি পদ প্রিন্ট করার জন্য মেইন ফাংশন থেকে মোট ৪৫ বার fiboOfNthItem() ফাংশন কল করছি। এতে কী ঘটছে? প্রথম বার ১ম পদ বের করার জন্য ফাংশন কল হয়। প্যারামিটারে পাঠানো হয় 1। এটি বেজ কেস স্যাটিসফাই করে, ফাংশন থেকে মেইন ফাংশনে 0 রিটার্ন করা হয়, এইক্ষেত্রে রিকার্সিভ কল হয় না। পাওয়া গেল প্রথম পদ। এরপর প্যারামিটারে 2 পাঠানো হয়। এটিও বেজ কেস স্যাটিসফাই করে। নতুন করে রিকার্সিভ কল না হয়ে রেজাল্ট হিসাবে 1 রিটার্ন করে। এরপর 3 পাঠানো হয় মেইন ফাংশন থেকে প্যারামিটার হিসাবে। ফলে বেজ কেস স্যাটিসফাই করে না। তৃতীয় লাইনে নতুন করে দুইবার ফাংশন কল হয়। রেজাল্ট রিটার্ন করা হয় মেইন ফাংশনে। এভাবে প্যারামিটারে পাঠানো হয় 4, 5, 6, … 45. প্রতিবারই রিকার্সিভ ফাংশনের শুরু থেকে ক্যালকুলেট করে করে আসে। সেটা কী রকম?

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

এই যে রিকার্সিভ ফাংশনের মানগুলো পরবর্তীতে ব্যবহার করার জন্য স্টোর করে রাখলাম এটার একটা গাল ভরা নাম আছে। তা হচ্ছে Dynamic Programming.

কেতাবী ভাষায় Dynamic Programming এর সংজ্ঞা দেয়া যায় এভাবেঃ

Dynamic Programming is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming. The idea is to simply store the results of subproblems, so that we do not have to re-compute them when needed later. [Source: GeeksForGeeks]

চলো আমরা আগের রিকার্সিভ কোডটাকে refactor করি। আমাদের আইডিয়াটা কী? আইডিয়াটা হচ্ছে প্রতিবার কোনো একটা পদের মান বের হলে সেটাকে array তে সেভ করে রাখব। অ্যারের ১ নাম্বার ইনডেক্সে রাখব ফিবোনাচ্চির প্রথম পদ, ২ নাম্বার ইনডেক্সে রাখব ফিবোনাচ্চির ২য় পদ। এভাবে আপাতত ৪৫ টা পদ সেভ রাখব। এরপর প্রতিবার যখন ফাংশনটা কল করা হবে তখন আগের মতই চেক করব n এর মান 1 বা 2 কিনা। অর্থাৎ প্রথম পদ বা দ্বিতীয় পদ বের করার জন্য ফাংশন কল করা হলে আমরা ডিরেক্ট রেজাল্ট রিটার্ন করব। এই দুইটা বেজ কেসের সাথে আরেকটা base case যোগ হবে। তা হচ্ছে চেক করে দেখা n-তম পদের মান আগের থেকে আমাদের অ্যারেতে আছে কিনা। যদি অ্যারেতে থাকে তাহলে আর নতুন করে ফাংশন কল করব না। অ্যারের মানটা রিটার্ন করে দিব। আর যদি অ্যারেতে সেটা না থাকে তাহলে রিকার্সিভ কল করে n-তম পদটা বের করব। বের করে সেটাকে অ্যারের n-তম ইনডেক্সে assign করব। এরপর মানটা মেইন ফাংশনে রিটার্ন করব। এই আইডিয়াটাই নিচের কোডে ইমপ্লিমেন্ট করা হয়েছে।

#include<stdio.h>

int fiboArray[50]; //global array. so all items are zero by default

int fiboOfNthItem(int n) {

    if(n==1) return 0;
    if(n==2) return 1;

    if(fiboArray[n] > 0)
        return fiboArray[n];

    fiboArray[n] = fiboOfNthItem(n-1) + fiboOfNthItem(n-2); //assign n-th item to n-th position of array for further use

    return fiboArray[n];
}

int main() {

    int i, n;
    fiboArray[2] = 1; //2nd item of Fibonacci series is '1'

    scanf("%d", &n);

    for(i=1; i<=n; i++) {
    	printf("%d ", fiboOfNthItem(i));
    }

    printf("\n");

    return 0;
}

ফিবোনাচ্চি সিরিজটা স্টোর করার জন্য একটা int টাইপের global array নিলাম। আমরা জানি globally কোনো array declare করা হলে by default সেই অ্যারের সকল ইনডেক্স 0 (zero) দিয়ে assign করা থাকে। তাই মেইন ফাংশনের প্রথমেই অ্যারের দ্বিতীয় ইনডেক্সে 1 অ্যাসাইন করে দিলাম। কারণ সিরিজের প্রথম পদ 0 (যা অলরেডি অ্যারের প্রথম ইনডেক্সে রয়েছে), আর দ্বিতীয় পদ 1। তাই fiboArray[2] = 1 লেখা হয়েছে।

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

fiboOfNthItem() ফাংশনে তৃতীয় একটা base case যোগ করা হয়েছে। চেক করা হচ্ছে fiboArray[n] এর মান 0 এর চেয়ে বড় কিনা। বড় হলে সেই মানটা রিটার্ন করা হচ্ছে। এটা দিয়ে আসলে কী করছি? পুরোর অ্যারের সকল ইনডেক্সে জিরো রাখা আছে, শুধু দ্বিতীয় ইনডেক্সে আছে 1. যদি কোনো পদের মান আমরা বের করি সেটাকে অ্যারের n-তম পদে সেভ করি। ফলে অ্যারের n-তম পদের জিরোটা রিপ্লেস হয়ে যায় n-তম পদের মান দ্বারা। অতএব, অ্যারের ইনডেক্স নাম্বার 2 এর চেয়ে বড় যে কোনো ইনডেক্সে যদি জিরো পাওয়া যায় এর মানে ঐ ইনডেক্সের পদটা এখনো নির্ণয় করা হয় নি। রিকার্সিভ কল করে সেটা নির্ণয় করতে হবে। কিন্তু যদি ঐ ইনডেক্সের মান জিরোর চেয়ে বড় কোনো সংখ্যা হয় তাহলে আমরা বুঝতে পারি এই ইনডেক্সের ভ্যালু এর আগের কোনো একটা ফাংশন কলে একবার বের করা হয়েছে। তাই নতুন করে হিসাব না করে সরাসরি ভ্যালুটা রিটার্ন করে দেই। ফলে আমাদের রিকার্সিভ ফাংশন কলের সংখ্যা অনেক অনেক কমে যায়। আগের approach এ যেমন ২০তম পদ বের করার জন্য আবার ১ থেকে ১৯ পর্যন্ত সকল পদের মান বের করতে হত এখন আর সেটা হবে না। এখন ২০তম পদের মান বের করার জন্য ফাংশন কল হলে ৩ টা বেজ কেসই মিথ্যা হবে। তৃতীয় বেজ কেস মিথ্যা হবে কারণ fiboArray[20] এ পাওয়া যাবে zero. তখন রিকার্সিভ কল করা হবে fiboOfNthItem(18) + fiboOfNthItem(19). এই দুইটা ফাংশন কলেই তৃতীয় বেজ কেস সত্য হবে। কারণ ২০তম পদ বের করার আগেই মেইন ফাংশন থেকে ১৮ ও ১৯তম পদ বের করার জন্য ফাংশন কল করা হয়েছিল। তখনই ১৮ ও ১৯তম পদের মান অ্যারেতে সেভ করে রাখা হয়েছিল। ফলে অ্যারের ১৮ ও ১৯তম ইনডেক্সের ভ্যালু যোগ করে রিটার্ন করে দেয়া হবে। এভাবে ২০তম পদ বের হয়ে সেটা অ্যারের ২০তম পজিশনে বসে যাবে।

DP (dynamic programming) এর কোড আর DP ছাড়া কোড দুটির ফাংশনের ভিতরে একটা printf(“%d\n”, n) দিয়ে n এর মান প্রিন্ট করে দেখতে পার। দেখো n এর মান ২০ এর জন্য কোন ফাংশনটা কয়বার কল হয়। এভাবে কোডের বিভিন্ন জায়গায় বিভিন্ন ভ্যালু বসিয়ে প্রিন্ট করে কোডের ফ্লো বুঝতে পার।

Fibonacci Series – DP implementation with less code

int fiboOfNthItem(int n) {

    if(n==1 || n==2 || fiboArray[n] > 0)
        return fiboArray[n];

    fiboArray[n] = fiboOfNthItem(n-1) + fiboOfNthItem(n-2);

    return fiboArray[n];
}

উপরের কোডে আসলে তেমন কোনো চেঞ্জই নাই। তিনটা বেজ কেস আলাদা IF দিয়ে না লিখে একসাথে লিখে দিয়েছি।

DP implementation with lesser code

int fiboOfNthItem(int n) {

    if(n>2 && fiboArray[n] == 0)
        fiboArray[n] = fiboOfNthItem(n-1) + fiboOfNthItem(n-2);

    return fiboArray[n];
}

এখানে কোড আরেকটু শর্ট করা গেল। কারণ আমরা জানি n এর মান ১ ও ২ এর জন্য ভ্যালু অ্যারেতে সেভ করা আছে। তাই যদি এবং কেবল যদি n এর মান ২ এর চেয়ে বড় হয় এবং সেটা অলরেডি অ্যারেতে না থেকে থাকে তাহলেই রিকার্সিভ কল হবে। অন্যথায় অ্যারের n-তম পজিশনের মানই রিটার্ন করবে।

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