পাঠ ২৯ · ৪৪-এর মধ্যে · মডিউল ৬
Home / Courses / Discrete Mathematics / রিকারেন্স রিলেশন পরিচিতি

রিকারেন্স রিলেশন — সংজ্ঞা ও উদাহরণ

Recurrence relations — definitions & examples
৭ মিনিট পড়া মধ্যবর্তী · Intermediate Python কোডসহ সম্পূর্ণ বাংলায়

এই পাঠে যা শিখবেন

  • রিকারেন্স রিলেশনের আনুষ্ঠানিক সংজ্ঞা — রিকার্সিভ অংশ ও বেস কেসের ভূমিকা
  • ফিবোনাচি, ফ্যাক্টোরিয়াল ও চক্রবৃদ্ধি সুদ — তিনটি ভিন্ন ধরনের রিকারেন্স
  • লিনিয়ার হোমোজিনিয়াস রিকারেন্সের সাধারণ রূপ ও "অর্ডার" ধারণা
  • কেন রিকারেন্স রিলেশন সরাসরি অ্যালগরিদম বিশ্লেষণের ভাষা

১ · রিকারেন্স রিলেশন কী?

একটি রিকারেন্স রিলেশনRecurrence Relationএকটি সিকোয়েন্স $a_0, a_1, a_2, \dots$-এর প্রতিটি পদকে তার পূর্ববর্তী এক বা একাধিক পদের ফাংশন হিসেবে সংজ্ঞায়িত করার একটি সমীকরণ, সাথে কিছু নির্দিষ্ট শুরুর মান (বেস কেস)। হলো একটি সিকোয়েন্স $a_0, a_1, a_2, \dots$-কে সংজ্ঞায়িত করার একটি উপায় — সরাসরি সূত্র দিয়ে নয়, বরং প্রতিটি পদকে তার আগের পদ(গুলো)-এর ফাংশন হিসেবে বলে দিয়ে। কিন্তু শুধু এই "নিয়ম" যথেষ্ট নয় — সিকোয়েন্সটি শুরু করার জন্য কিছু বেস কেসBase Caseরিকারেন্সের সবচেয়ে ছোট ইনডেক্সের জন্য সরাসরি দেওয়া মান, যেখান থেকে বাকি সব পদ গণনা শুরু হয়। এটি ছাড়া রিকারেন্স সমাধানযোগ্য নয়। (base case)-ও লাগবে।

দুই অংশের কাঠামো

প্রতিটি রিকারেন্স রিলেশনের ঠিক দুটি অংশ থাকে — (১) রিকার্সিভ সংজ্ঞা, যা $a_n$-কে আগের পদগুলোর সাপেক্ষে বলে দেয়, এবং (২) বেস কেস(গুলো), যা সবচেয়ে ছোট ইনডেক্সের মান সরাসরি নির্দিষ্ট করে। এই দুইয়ের সমন্বয়েই সম্পূর্ণ সিকোয়েন্সটি অনন্যভাবে (uniquely) নির্ধারিত হয়।

২ · পরিচিত উদাহরণ

নিচের তিনটি উদাহরণ আপনি ইতিমধ্যে চেনেন — কিন্তু এবার সেগুলোকে রিকারেন্স রিলেশন হিসেবে দেখুন।

ফিবোনাচি সিকোয়েন্স
$F(n) = F(n-1) + F(n-2)$, বেস কেস $F(0)=0,\ F(1)=1$। প্রতিটি পদ আগের দুটি পদের যোগফল: $0,1,1,2,3,5,8,13,\dots$
ফ্যাক্টোরিয়াল
$n! = n \cdot (n-1)!$, বেস কেস $0!=1$। প্রতিটি পদ আগের পদকে $n$ দিয়ে গুণ করে পাওয়া যায়: $1,1,2,6,24,120,\dots$
চক্রবৃদ্ধি সুদ
$A(n) = A(n-1)(1+r)$, বেস কেস $A(0)=$ প্রাথমিক অর্থ। প্রতি বছর আগের ব্যালেন্সের উপর $(1+r)$ গুণ প্রয়োগ হয়।

লক্ষ্য করুন — এই তিনটির প্রতিটিতেই একই প্যাটার্ন: বর্তমান পদ = আগের পদ(গুলো)-এর কোনো ফাংশন, প্লাস একটি নির্দিষ্ট শুরুর বিন্দু। ফিবোনাচি দুটি আগের পদের উপর নির্ভর করে (তাই দুটি বেস কেস লাগে), অন্য দুটি শুধু একটি আগের পদের উপর নির্ভর করে (তাই একটি বেস কেস যথেষ্ট)।

৩ · লিনিয়ার হোমোজিনিয়াস রিকারেন্স — সাধারণ রূপ

উপরের ফিবোনাচি উদাহরণটি একটি বিশেষ ধরনের রিকারেন্সের অন্তর্ভুক্ত, যাকে বলা হয় লিনিয়ার হোমোজিনিয়াস রিকারেন্সLinear Homogeneous Recurrence with Constant Coefficientsএমন একটি রিকারেন্স যেখানে $a_n$ আগের $k$টি পদের একটি ধ্রুবক-গুণাঙ্কযুক্ত যোগফল মাত্র — কোনো অতিরিক্ত পদ, গুণফল বা ফাংশন ছাড়া। "$k$" হলো এই রিকারেন্সের অর্ডার। (linear homogeneous recurrence with constant coefficients)। এর সাধারণ রূপ —

$$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \dots + c_k a_{n-k}$$

যেখানে $c_1, c_2, \dots, c_k$ ধ্রুবক (constant) সংখ্যা, এবং $k$ হলো এই রিকারেন্সের অর্ডার — অর্থাৎ কতগুলো আগের পদের উপর $a_n$ নির্ভর করে। ফিবোনাচি এর একটি দ্বিতীয়-ক্রম (order 2) উদাহরণ, যেখানে $c_1=1, c_2=1$। "হোমোজিনিয়াস" শব্দটির মানে — সমীকরণের ডান পাশে $a_{n-i}$ ছাড়া অন্য কোনো স্বাধীন পদ (যেমন একটি ধ্রুবক $+5$) নেই। পরের পাঠে (L30) আমরা এই ধরনের রিকারেন্স সমাধান করে সরাসরি একটি বদ্ধ-রূপ (closed-form) সূত্র বের করব — যাতে $a_n$ গণনা করতে আর আগের সব পদ ধাপে ধাপে বসাতে না হয়।

৪ · অ্যালগরিদম বিশ্লেষণের সাথে সংযোগ

DSA কোর্সে আপনি রিকার্সিভ ফাংশন লিখেছেন — কিন্তু সেই ফাংশনগুলোর রানটাইম বর্ণনা করাও আসলে একটি রিকারেন্স রিলেশন লেখার সমতুল্য। যদি $T(n)$ হয় ইনপুট সাইজ $n$-এর জন্য কতগুলো ধাপ লাগে —

সাধারণ লুপ/রিকার্সন
$T(n) = T(n-1) + 1$ — প্রতিটি কল একটি ধাপ কমায়, প্রতি ধাপে সময় লাগে $O(1)$। যেমন একটি সাধারণ রিকার্সিভ কাউন্টডাউন ফাংশন।
মার্জ সর্ট
$T(n) = 2T(n/2) + n$ — ইনপুটকে দুই ভাগে ভাগ করে (প্রতি ভাগে $T(n/2)$), তারপর $n$ সময়ে merge করা হয়।
মূল কথা · Key takeaway

একটি রিকার্সিভ অ্যালগরিদম "কত দ্রুত" চলে তা বোঝার জন্য প্রথমে তার রানটাইমকে একটি রিকারেন্স রিলেশন হিসেবে লিখতে হয়, তারপর সেই রিকারেন্স সমাধান করতে হয় একটি বদ্ধ-রূপ Big-O সূত্র পাওয়ার জন্য। L30-এ ক্যারেক্টারিস্টিক ইকুয়েশন পদ্ধতি ও L31-এ Master Theorem শিখে, আমরা M8/L41-এ ঠিক এই কাজটি করব — real recursive algorithms-এর জটিলতা বের করব।

Python
# ফিবোনাচি — রিকারেন্স রিলেশন অনুযায়ী, ইটারেটিভভাবে (দ্রুত, স্ট্যাক-নিরাপদ)
def fibonacci_upto(n):
    seq = [0, 1]
    for i in range(2, n + 1):
        seq.append(seq[i - 1] + seq[i - 2])
    return seq[:n + 1]

seq = fibonacci_upto(15)
print("F(0..15):", seq)
print("F(10) =", seq[10])
assert seq[10] == 55
print("যাচাই সম্পন্ন — F(10) = 55")

    


    

      লক্ষ্য করুন — কোডটি রিকারেন্সের সংজ্ঞা অনুযায়ী প্রতিটি পদ একবার গণনা করে (একটি লুপে), নাইভ রিকার্সিভ
      সংজ্ঞা ব্যবহার করলে যেমন একই মান বারবার গণনা হতো তেমন নয়। এই পার্থক্যটিই M8/L41-এ বিস্তারিত আলোচনা হবে।
    


    
    

      
        
          
            
          
        
        
        F(0)=0
        বেস কেস

        
        F(1)=1
        বেস কেস

        
        F(2)=1
        F(1)+F(0)

        
        F(3)=2
        F(2)+F(1)

        
        F(4)=3
        F(3)+F(2)

        
        
        
        
      
      
বেস কেস থেকে শুরু করে, প্রতিটি নতুন পদ আগের পদগুলো ব্যবহার করে ধাপে ধাপে গণনা হয়।

    


  


  

    
    
  


  

    
 ভাবনার প্রশ্ন

    
প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।


    

      
        প্র ০১
        ফিবোনাচি রিকারেন্সের দুটি বেস কেস লাগে, কিন্তু ফ্যাক্টোরিয়ালের একটিই যথেষ্ট — কেন এই পার্থক্য?
      
      

        

          একটি রিকারেন্সের জন্য কতগুলো বেস কেস লাগবে তা নির্ভর করে $a_n$ গণনা করতে কতগুলো আগের পদ প্রয়োজন তার
          উপর। ফিবোনাচিতে $F(n)$ নির্ভর করে $F(n-1)$ এবং $F(n-2)$ — অর্থাৎ দুটি ভিন্ন আগের পদের উপর। তাই সিকোয়েন্সটি
          অনন্যভাবে শুরু করতে দুটি মান ($F(0)$ ও $F(1)$) সরাসরি দিতে হয়। ফ্যাক্টোরিয়ালে $n!$ শুধু $(n-1)!$-এর উপর
          নির্ভর করে — একটি মাত্র আগের পদ — তাই একটি বেস কেস ($0!=1$) যথেষ্ট। সাধারণভাবে, একটি "$k$-তম ক্রমের" (order $k$)
          রিকারেন্সের ঠিক $k$টি বেস কেস লাগে।
        

      

    


    

      
        প্র ০২
        $T(n) = T(n-1) + 1$ এবং $T(n) = 2T(n/2) + n$ — এই দুই রিকারেন্সের গঠনগত পার্থক্য কী, এবং তা কেন গুরুত্বপূর্ণ?
      
      

        

          প্রথমটিতে $T(n)$ নির্ভর করে ঠিক একটি ছোট সাব-প্রবলেমের উপর ($T(n-1)$) — এটি একটি সাধারণ,
          একরৈখিক রিকার্সন মডেল করে (যেমন একটি লুপ)। দ্বিতীয়টিতে $T(n)$ নির্ভর করে দুটি সাব-প্রবলেমের
          উপর ($T(n/2)$ দুইবার), এবং প্রতিটি সাব-প্রবলেম মূল ইনপুটের অর্ধেক আকারের — এটি "ডিভাইড-অ্যান্ড-কনকার" (divide
          and conquer) প্যাটার্ন মডেল করে, যেমন মার্জ সর্ট। এই গঠনগত পার্থক্যই ঠিক করে দেয় চূড়ান্ত জটিলতা কেমন হবে —
          প্রথমটি $O(n)$-এ সমাধান হয়, দ্বিতীয়টি (L31-এ Master Theorem দিয়ে) $O(n \log n)$-এ সমাধান হয়।
        

      

    


    

      
        প্র ০৩
        কোড সেলে ফিবোনাচি ইটারেটিভভাবে (লুপ দিয়ে) গণনা করা হয়েছে, নাইভ রিকার্সিভ সংজ্ঞা দিয়ে সরাসরি নয় কেন?
      
      

        

          রিকারেন্সের সংজ্ঞা এবং তা গণনা করার সবচেয়ে ভালো পদ্ধতি — এই দুটি ভিন্ন জিনিস। নাইভ রিকার্সিভ
          কোড ($F(n) = F(n-1)+F(n-2)$ সরাসরি ফাংশন কল দিয়ে লেখা) একই $F(k)$ মান বহুবার পুনরায় গণনা করে — যার ফলে
          এক্সপোনেনশিয়াল সময় লাগে (M8/L41-এ এর সঠিক জটিলতা $\Theta(\varphi^n)$ দেখানো হবে)। ইটারেটিভ পদ্ধতি প্রতিটি
          মান ঠিক একবার গণনা করে সংরক্ষণ করে রাখে, তাই এটি অনেক দ্রুত — এটি একই রিকারেন্স রিলেশনের একটি ভিন্ন,
          কার্যকর বাস্তবায়ন মাত্র।
        

      

    

  


  

    
 অনুশীলন

    
    
      
  1. 
        হাতে গণনা করুন: রিকারেন্স $a_n = a_{n-1} + n$, বেস কেস $a_0=0$ ব্যবহার করে $a_1, a_2, a_3, a_4$ হাতে হিসাব করুন।
        
    
          
          
    
            
    
              $a_1 = a_0+1 = 0+1 = 1$। $a_2 = a_1+2 = 1+2 = 3$। $a_3 = a_2+3 = 3+3 = 6$। $a_4 = a_3+4 = 6+4 = 10$।
              (লক্ষ্য করুন — এই সিকোয়েন্স $0,1,3,6,10,\dots$ আসলে $a_n = n(n+1)/2$, যা L06-এ প্রমাণিত ইনডাকশন সূত্রের
              সাথে মিলে যায়!)
            
    
          
    
        
    
      
    2. 
      
  2. 
        কোড পরিবর্তন করুন: উপরের কোড সেলে fibonacci_upto ফাংশনটিকে পরিবর্তন করে এমন একটি ফাংশন লিখুন যা $a_n = a_{n-1} + 2$, $a_0 = 5$ রিকারেন্স অনুযায়ী প্রথম ১০টি পদ প্রিন্ট করে।
        
    
          
          
    
            
    
              সম্ভাব্য সমাধান:
            
    
            
    def linear_seq(n0, step, count):
    seq = [n0]
    for i in range(1, count):
        seq.append(seq[i - 1] + step)
    return seq

print(linear_seq(5, 2, 10))  # [5, 7, 9, 11, 13, 15, 17, 19, 21, 23]
    
            
    
              এটি একটি লিনিয়ার (কিন্তু নন-হোমোজিনিয়াস, কারণ $+2$ ধ্রুবকটি যোগ হচ্ছে) রিকারেন্সের উদাহরণ — L30-এ আমরা
              শুধু হোমোজিনিয়াস কেসের উপর মনোযোগ দেব, তবে ধারণাটি একই।
            
    
          
    
        
    
      
    3. 
    

  


  

    
 আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ

    
  







  
  
     এই পাঠে ভুল পেয়েছেন? জানান
  





  
    
 আগের পাঠ

    
RSA এনক্রিপশন — নাম্বার থিওরির বাস্তব প্রয়োগ