রিকারেন্স রিলেশন ও রিকার্সিভ অ্যালগরিদম

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

রিকারেন্স রিলেশনRecurrence Relationএকটি ফাংশনকে তার নিজেরই ছোট ইনপুটের মানের মাধ্যমে সংজ্ঞায়িত করা একটি সমীকরণ, সাথে একটি বা একাধিক বেস কেস। হলো এমন একটি সমীকরণ যা একটি ফাংশনের মান তার নিজেরই ছোট ইনপুটের উপর নির্ভর করে সংজ্ঞায়িত করে। L01-এ আমরা দেখেছি একটি সত্যিকারের অ্যালগরিদমের একটি বৈশিষ্ট্য হলো সসীমতা (finiteness) — একটি রিকারেন্স রিলেশনও এই একই নীতি মেনে চলে: এতে দুটো অংশ বাধ্যতামূলক —

"কঠোরভাবে ছোট" শর্তটি গুরুত্বপূর্ণ — এটি নিশ্চিত করে যে বারবার প্রয়োগ করলে শেষ পর্যন্ত বেস কেসে পৌঁছাতেই হবে, অসীম রিকার্সন ঘটবে না। ক্লাসিক উদাহরণ হলো ফিবোনাচি সংখ্যা:

$$F(n) = \begin{cases} 0 & n = 0 \quad \text{(বেস কেস)}\\ 1 & n = 1 \quad \text{(বেস কেস)}\\ F(n-1) + F(n-2) & n \ge 2 \quad \text{(রিকার্সিভ কেস)}\end{cases}$$

এখানে n=0 ও n=1 বেস কেস — সরাসরি উত্তর দেওয়া হয়েছে। n \ge 2-এর জন্য F(n)-কে সংজ্ঞায়িত করা হয়েছে দুটো ছোট উপসমস্যা F(n-1) ও F(n-2)-এর মাধ্যমে — উভয়ই n-এর চেয়ে ছোট, তাই বারবার প্রয়োগ করলে শেষমেশ F(0) বা F(1)-এ পৌঁছানো নিশ্চিত। ফিবোনাচি ও ফ্যাক্টোরিয়ালের রিকার্সিভ Python ইমপ্লিমেন্টেশন ইতিমধ্যে DSA কোর্সে দেখানো হয়েছে — এই পাঠে আমরা ইমপ্লিমেন্টেশন নয়, বরং এই রিকারেন্স রিলেশনের গাণিতিক কাঠামো ও এর "লুকানো দ্বিতীয় রিকারেন্স" নিয়ে আলোচনা করব।

২ · প্রতিটি রিকার্সিভ অ্যালগরিদমেরই একটি "কল-কাউন্ট" রিকারেন্স থাকে

F(n) নিজে কী মান তা একটি প্রশ্ন। কিন্তু F(n) নেইভভাবে (উপরের সংজ্ঞা অনুযায়ী সরাসরি রিকার্সন দিয়ে, কোনো মেমোয়াইজেশন ছাড়া) গণনা করতে কতগুলো ফাংশন কল লাগবে — এটা সম্পূর্ণ ভিন্ন একটা প্রশ্ন, এবং এর উত্তরও একটা রিকারেন্স রিলেশন দিয়েই দিতে হয়। ধরা যাক T(n) = fib(n) গণনা করতে মোট কতগুলো ফাংশন কল হয় (নিজেরটাসহ):

$$T(n) = \begin{cases} \Theta(1) & n \le 1\\ T(n-1) + T(n-2) + \Theta(1) & n \ge 2\end{cases}$$

লক্ষ্য করুন — T(n)-এর রিকার্সিভ কেসের গঠন F(n)-এর রিকার্সিভ কেসের সাথে প্রায় হুবহু একই রকম (দুটো ছোট উপসমস্যার যোগফল), তাই এটাও এক্সপোনেনশিয়ালি বেড়ে যাওয়ার আশঙ্কা থাকে। নিচের রিকার্সন ট্রি স্কেচটি দেখায় কেন — প্রতিটি নন-বেস-কেস কল থেকে দুটো নতুন কল জন্ম নেয়, ফলে গাছটি প্রতি স্তরে প্রায় দ্বিগুণ চওড়া হতে থাকে।

৩ · সত্যিকারের কোড — প্রতিটি কল গুনে দেখা

নিচের কোড সেলে একটি গ্লোবাল কাউন্টার ব্যবহার করে প্রতিটি fib কলে +১ করা হচ্ছে — অর্থাৎ আমরা উপরের T(n) রিকারেন্সের প্রকৃত মান সরাসরি পরিমাপ করছি (কোনো সূত্র অনুমান করা হচ্ছে না)।

call_count = 0

def fib(n):
    global call_count
    call_count += 1          # প্রতিটি কলেই গোনা হচ্ছে -- এটাই T(n)
    if n <= 1:
        return n              # বেস কেস
    return fib(n - 1) + fib(n - 2)   # রিকার্সিভ কেস

def count_calls(n):
    global call_count
    call_count = 0
    fib(n)
    return call_count

sizes = [5, 10, 15, 20, 25]
counts = [(n, count_calls(n)) for n in sizes]

print(f"{'n':>5} | {'T(n) -- মোট কল সংখ্যা':>22}")
for n, c in counts:
    print(f"{n:>5} | {c:>22}")

print("\nn প্রতি +৫ বাড়লে কল সংখ্যা কত গুণ বাড়ে:")
for i in range(1, len(counts)):
    n_prev, c_prev = counts[i - 1]
    n_cur, c_cur = counts[i]
    print(f"n={n_prev}->{n_cur}: {c_cur / c_prev:.3f}x")