রিকার্শন ইমপ্লিমেন্টেশন

১ · বেস কেস ও রিকার্সিভ কেস

একটি সঠিক রিকার্সিভ ফাংশনে দুটি অংশ থাকতেই হয়। বেস কেসBase Caseএমন একটি শর্ত যার অধীনে ফাংশন আর কোনো রিকার্সিভ কল না করেই সরাসরি রিটার্ন করে — "থামার বিন্দু"। হলো এমন একটি শর্ত, যার অধীনে ফাংশন সরাসরি রিটার্ন করে — আর কোনো রিকার্সিভ কল ছাড়াই ("থামার বিন্দু")। রিকার্সিভ কেসRecursive Caseফাংশন নিজেকে একবার বা একাধিকবার, সাধারণত সমস্যার একটি "ছোট" সংস্করণে, আবার কল করে — এবং সেই কলের ফলাফল দিয়ে নিজের ফলাফল তৈরি করে। ফাংশন নিজেকে একবার বা একাধিকবার — সাধারণত মূল সমস্যার একটি "ছোট"/সরলতর সংস্করণে — আবার কল করে, এবং সেই রিকার্সিভ কলের ফলাফল দিয়ে নিজের ফলাফল তৈরি করে। একটি সঠিকভাবে-পৌঁছানো-যায়-এমন বেস কেস ছাড়া রিকার্শন কখনো থামে না — একটি সত্যিকারের, সাধারণ বাগ: ইনফিনিট রিকার্শন, যার সরাসরি পরিণতি হলো স্ট্যাক ক্রমাগত বেড়ে গিয়ে "স্ট্যাক ওভারফ্লো" — M11/L48-এর কল-স্ট্যাক-বৃদ্ধির মডেল দিয়েই এটি সরাসরি ব্যাখ্যা করা যায়: প্রতিটি রিকার্সিভ কল আরেকটি অ্যাক্টিভেশন রেকর্ড push করে, আর বাস্তব সিস্টেমে স্ট্যাকের সাইজ সবসময় ফিনিট।

২ · স্ট্যাক ডেপথ = পেন্ডিং কলের সংখ্যা

M11/L48-এর কল-স্ট্যাক ভিজুয়ালাইজেশনের সরাসরি প্রয়োগ হিসেবে: স্ট্যাক ডেপথ মানে এই মুহূর্তে কতগুলো কল pending (এখনো রিটার্ন করেনি, নিজের রিকার্সিভ কলের ফলাফলের জন্য অপেক্ষা করছে)। factorial(5) কল করলে, সবচেয়ে গভীর বিন্দুতে একইসাথে ৫টি আলাদা অ্যাক্টিভেশন রেকর্ড স্ট্যাকে থাকবে — factorial(5), factorial(4), factorial(3), factorial(2), factorial(1) — প্রতিটি তার নিজের রিকার্সিভ কল রিটার্ন না করা পর্যন্ত অপেক্ষমাণ।

৩ · Tail Recursion ও Tail-Call Optimization

একটি রিকার্সিভ কলকে tail callTail Callএকটি কল, যদি এটি ফাংশনের একেবারে শেষ অপারেশন হয় — কলের ফলাফল ছাড়া আর কিছুই করার বাকি থাকে না, সরাসরি রিটার্ন করা ছাড়া। বলা হয় যদি এটি ফাংশনের একদম শেষ অপারেশন হয় — কলের ফলাফল নিয়ে সরাসরি রিটার্ন করা ছাড়া আর কিছুই বাকি না থাকে। কিছু ভাষার ইমপ্লিমেন্টেশন tail call-কে অপ্টিমাইজ করতে পারে (Tail-Call Optimization, TCO) — নতুন অ্যাক্টিভেশন রেকর্ড push না করে বর্তমান ফ্রেমটিই পুনর্ব্যবহার করে — tail-recursive ফাংশনের জন্য স্ট্যাক-ডেপথ-বৃদ্ধির সমস্যা সম্পূর্ণ এড়িয়ে যায়। সততার সাথে বলা দরকার — সব ভাষা/ইমপ্লিমেন্টেশন এই অপ্টিমাইজেশন করে না; স্ট্যান্ডার্ড Python নিজেই TCO বাস্তবায়ন করে না, একটি সত্যিকারের, বাস্তব সীমাবদ্ধতা যা স্পষ্টভাবে জানা দরকার।

৪ · কোড: গভীরতা-ট্র্যাকিং factorial ও Tail-Recursive সংস্করণ

নিচে দুটো factorial বাস্তবায়ন আছে। প্রথমটি একটি সাধারণ (non-tail-recursive) রিকার্সিভ সংস্করণ, একটি ছোট CallStack দিয়ে সর্বোচ্চ গভীরতা ট্র্যাক করা হয়েছে। দ্বিতীয়টি একটি accumulator-ভিত্তিক, সত্যিকারের tail-recursive সংস্করণ — যেখানে রিকার্সিভ কলটিই একদম শেষ অপারেশন।

class CallStack:
    """M11/L48-এর মডেলের একটি হালকা সংস্করণ -- শুধু গভীরতা ট্র্যাক করে।"""
    def __init__(self):
        self.depth = 0
        self.max_depth = 0

    def push(self):
        self.depth += 1
        self.max_depth = max(self.max_depth, self.depth)

    def pop(self):
        self.depth -= 1


stack = CallStack()


def factorial(n):
    """সাধারণ, non-tail-recursive সংস্করণ -- রিটার্নের ঠিক আগে গুণটা এখনো বাকি থাকে।"""
    stack.push()
    if n <= 1:
        result = 1
    else:
        result = n * factorial(n - 1)   # গুণ করাটা এই কলের ফলাফল আসার পরে হয় -- tail call নয়
    stack.pop()
    return result


result = factorial(5)
print(f"factorial(5) = {result}")
print(f"রিকার্শনের সর্বোচ্চ স্ট্যাক গভীরতা (max_depth) = {stack.max_depth}")
assert stack.max_depth == 5
assert stack.depth == 0
assert result == 120
print(f"যাচাই: max_depth == 5 -> {stack.max_depth == 5},  factorial(5) == 120 -> {result == 120}")


def factorial_tail(n, accumulator=1):
    """সত্যিকারের tail-recursive সংস্করণ -- রিকার্সিভ কলটিই একেবারে শেষ অপারেশন।"""
    if n <= 1:
        return accumulator
    return factorial_tail(n - 1, n * accumulator)   # এখানে ফেরার আগে আর কিছুই করার বাকি নেই


tail_result = factorial_tail(5)
print(f"\nfactorial_tail(5) = {tail_result}")
assert tail_result == result
print(f"যাচাই: tail_result == result -> {tail_result == result}  (উভয় সংস্করণ অভিন্ন ফলাফল দিয়েছে)")

print("\nদ্রষ্টব্য: স্ট্যান্ডার্ড Python TCO বাস্তবায়ন করে না -- তাই factorial_tail-ও রানটাইমে")
print("factorial-এর মতোই ৫টি ফ্রেম push করবে। পার্থক্যটা শুধুই গঠনে (structural),")
print("রানটাইম আচরণে নয় -- একটি TCO-সমর্থনকারী ভাষায় এই গঠনগত পার্থক্যটিই কাজে লাগত।")