মডিউল ১৭_৩ঃ Fibonacci Series

আমরা এখন এক বিশেষ ধরনের সিরিজ এর সম্পর্কে জানবো এবং এটাকে কিভাবে রিকারশিবলি চিন্তা করা যায় সেটা নিয়ে দেখবো।

Fibonacci series টা হচ্ছে এটাঃ

0, 1, 1, 2, 3, 5, 8, 13, 21, 34 …....

লক্ষ্য করো ১ম দুটি সংখ্যা ছাড়া প্রতিটি সংখ্যা হলো আগের দুটি সংখ্যার যোগফল। মানে ০ আর ১ কে ফিক্স রেখে তারপরের সংখ্যা গুলো তার আগের সংখ্যা গুলোর যোগফল।

০+১ = ১,

১+১ = ২

২+১ = ৩

৩+২ = ৫

৫+৩ = ৮

৮+৫ = ১৩

.........

.........

তাহলে আমরা একটু যদি চিন্তা করে দেখি তাহলে n তম fibonacci নাম্বার হবে n-1 তম নাম্বার আর n-2 তম নাম্বারের সমষ্টি।

তাহলে আমরা ফাংশনের ভাষায় বলতে পারি যে fn(n) = fn(n-1) + fn(n-2)। আবার খেয়াল করে দেখো প্রথম দুইটা সংখ্যা ফিক্সড। মানে

fn(0) = 0

fn(1) = 1

fn(n) = fn(n-1)+fn(n-2) [যদি n>2]

তাহলে আমরা একটা রিকারশিভ সল্যুশন এখন বিল্ড করে ফেলতে পারি। আমরা রিকারশান কে বলে দিব যে n এর মান যদি ০ বা ১ হয় তাহলে n কে রিটার্ন করতে আর নাহলে তাকে বলবো যে n-1 আর n-2 এর সল্যুশন বের করতে।

// Some code
ll fibo(ll n)
{
    if (n == 0 || n == 1)
    {
        return n;
    }
    ll ans = fibo(n - 1) + fibo(n - 2);
    return ans;
}