C#-এ রিকার্শন ব্যবহার করে ফিবোনাচ্চি সিরিজের nth মান বের করা

ফিবোনাচ্চি সিরিজে প্রতিটি সংখ্যা পূর্ববর্তী দুটি সংখ্যার যোগফল: F(n) = F(n-1) + F(n-2), যেখানে F(0) = 0, F(1) = 1।

নিবিড় রিকার্সিভ ইমপ্লিমেন্টেশন (O(2^n) - খুব ধীর)

using System;

public class Demo
{
    public static void Main(string[] args)
    {
        Demo d = new Demo();
        int val = 7;
        int res = d.DisplayFibonacci(val);
        Console.WriteLine($"{val}th number in fibonacci series = {res}");
    }
    
    public int DisplayFibonacci(int n)
    {
        if (n == 0) return 0;
        if (n == 1) return 1;
        return DisplayFibonacci(n - 1) + DisplayFibonacci(n - 2);
    }
}

আউটপুট

7th number in fibonacci series = 13

সমস্যা: এক্সপোনেনশিয়াল টাইম কমপ্লেক্সিটি

নিবিড় রিকার্শনে একই সাব-প্রব্লেম বারবার ক্যালকুলেট হয়। F(7) এর জন্য F(5) ৫বার, F(4) ৩বার কল হয়।

অপ্টিমাইজড পদ্ধতিগুলো

১. মেমোরাইজেশন (Top-Down DP) - O(n)

using System;
using System.Collections.Generic;

public class FibonacciMemo
{
    private readonly Dictionary<int, long> _memo = new Dictionary<int, long>();
    
    public long Calculate(int n)
    {
        if (n <= 1) return n;
        if (_memo.TryGetValue(n, out long value)) return value;
        
        long result = Calculate(n - 1) + Calculate(n - 2);
        _memo[n] = result;
        return result;
    }
}

// ব্যবহার
var fib = new FibonacciMemo();
Console.WriteLine(fib.Calculate(50)); // 12586269025 (মিলিসেকেন্ডে)

২. বটম-আপ DP (ইটেরেটিভ) - O(n) টাইম, O(1) স্পেস

public static long FibonacciIterative(int n)
{
    if (n <= 1) return n;
    
    long a = 0, b = 1;
    for (int i = 2; i <= n; i++)
    {
        long temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

৩. ম্যাট্রিক্স এক্সপোনেনশিয়েশন - O(log n)

public static long FibonacciMatrix(long n)
{
    if (n <= 1) return n;
    
    // ম্যাট্রিক্স: [[1,1],[1,0]]^n
    long[,] matrix = { { 1, 1 }, { 1, 0 } };
    long[,] result = MatrixPower(matrix, n - 1);
    return result[0, 0];
}

static long[,] MatrixMultiply(long[,] a, long[,] b)
{
    return new long[,]
    {
        { a[0,0]*b[0,0] + a[0,1]*b[1,0], a[0,0]*b[0,1] + a[0,1]*b[1,1] },
        { a[1,0]*b[0,0] + a[1,1]*b[1,0], a[1,0]*b[0,1] + a[1,1]*b[1,1] }
    };
}

static long[,] MatrixPower(long[,] m, long p)
{
    long[,] result = { { 1, 0 }, { 0, 1 } }; // আইডেন্টিটি ম্যাট্রিক্স
    while (p > 0)
    {
        if ((p & 1) == 1) result = MatrixMultiply(result, m);
        m = MatrixMultiply(m, m);
        p >>= 1;
    }
    return result;
}

৪. বিনেটের ফর্মুলা (Closed-form) - O(1) কিন্তু প্রিসিশন ইস্যু

public static long FibonacciBinet(int n)
{
    double phi = (1 + Math.Sqrt(5)) / 2; // গোল্ডেন রেশিও
    return (long)Math.Round(Math.Pow(phi, n) / Math.Sqrt(5));
}
// নোট: n > 70 হলে ডাবল প্রিসিশন ইস্যু দেখাতে পারে

পারফরম্যান্স তুলনা (n=40)

সারসংক্ষেপ

• শিক্ষামূলক: নিবিড় রিকার্শন বুঝতে ভালো
• প্রোডাকশন: ইটেরেটিভ (O(n), O(1) স্পেস) বা মেমোরাইজেশন
• খুব বড় n: ম্যাট্রিক্স এক্সপোনেনশিয়েশন (O(log n))
• বড় সংখ্যা: BigInteger ব্যবহার করুন