রিকার্সন মধ্যে

রিকার্সন সম্পর্কে

রিকার্সন হলো একটি ফাংশনের ভেতরে কোড বারবার চালানোর একটি উপায়, যেখানে ফাংশনটি নিজেই নিজেকে কল করে। যে ফাংশনগুলো নিজেদের কল করে, তাদের রিকার্সিভ ফাংশন বলা হয়। রিকার্সনকে লুপ করা বা ইটারেশন করার আরেকটি উপায় হিসেবে দেখা যেতে পারে। আর লুপ করার মতোই, রিকার্সিভ এক্সিকিউশন কখন থামাতে হবে তা নির্ধারণ করতে একটি বুলিয়ান এক্সপ্রেশন বা True/False টেস্ট ব্যবহার করা হয়।

লুপ করার বিপরীতে, Python-এ সমাপ্তি ছাড়া রিকার্সন অসীমভাবে চলতে পারে না। প্রতিটি ফাংশন কলে ব্যবহৃত মানগুলো Python ইন্টারপ্রেটার স্ট্যাকের নিজস্ব ফ্রেমে রাখা হয়। যদি মোট ফাংশন কলের সংখ্যা স্ট্যাকের জায়গার চেয়ে বেশি জায়গা নেয়, তাহলে সেটি একটি এরর তৈরি করবে।

লুপিং বনাম রিকার্সিভ ইমপ্লিমেন্টেশন

লুপিং আর রিকার্সন হয়তো একই রকম লাগতে পারে, কারণ দুটোই ইটারেটিভ। তবে কোডের স্তরে এবং ইমপ্লিমেন্টেশনের স্তরে, দুটো দেখতে আলাদা। লুপিং কল স্ট্যাক-এর একই ফ্রেমের ভেতরে ঘটতে পারে। এটি সাধারণত এক বা একাধিক ভ্যারিয়েবলের মান হালনাগাদ করে করা হয়, যাতে প্রতিটি ইটারেশনের জন্য ধাপে ধাপে স্টেট বজায় থাকে। এটি একটি কার্যকর ইমপ্লিমেন্টেশন, তবে কোডের দিকে তাকালে এটি কিছুটা এলোমেলো লাগতে পারে।

রিকার্সন ভ্যারিয়েবল স্টেট হালনাগাদ করার বদলে, একই ফাংশনের পরবর্তী কলের (ইটারেশনের) আর্গুমেন্ট হিসেবে সরাসরি হালনাগাদ করা মান পাঠাতে পারে। এতে ফাংশনের বডি পরিষ্কার হয় এবং প্রতিটি হালনাগাদ কীভাবে হচ্ছে তা স্পষ্ট হয়। তবে এটি কম কার্যকর ইমপ্লিমেন্টেশনও বটে, কারণ একই ফাংশনের প্রতিটি কল স্ট্যাকে আরেকটি ফ্রেম যোগ করে।

রিকার্সন: কেন আর কেন নয়?

স্ট্যাক এরর বা ওভারফ্লো হওয়ার ঝুঁকি থাকলে, কেউ কেন একটি সমস্যা সমাধানে রিকার্সিভ কৌশল ব্যবহার করবে? পাঠযোগ্যতা, অনুসরণযোগ্যতা এবং উদ্দেশ্য। এমন পরিস্থিতি থাকতে পারে যেখানে একটি সমাধান লুপিংয়ের মাধ্যমে প্রকাশ করার চেয়ে রিকার্সনের মাধ্যমে প্রকাশ করলে বেশি পাঠযোগ্য এবং/অথবা যুক্তি দিয়ে বোঝা সহজ হয়। ডেটা ব্যবহার বা পরিবর্তন, জটিলতা ব্যবস্থাপনা, দায়িত্ব অর্পণ, কিংবা কাজের চাপ গুছিয়ে রাখার ক্ষেত্রে প্রোগ্রামের সীমাবদ্ধতাও থাকতে পারে।

রিকার্সনের উপযোগী সমস্যাগুলোর মধ্যে আছে জটিল কিন্তু পুনরাবৃত্তিমূলক সমস্যা, যেগুলো সময়ের সাথে ছোট হতে থাকে, বিশেষ করে ডিভাইড অ্যান্ড কনকার অ্যালগরিদম এবং কিউমুলেটিভ অ্যালগরিদম। তবে, স্ট্যাকে কতগুলো ফ্রেম থাকতে পারবে সেই Python-এর সীমাবদ্ধতার কারণে, সব সমস্যা সম্পূর্ণ রিকার্সিভ কৌশল থেকে উপকৃত হবে না। রিকার্সনের জন্য কম উপযোগী সমস্যাগুলোর মধ্যে আছে এমন সমস্যা যেগুলোর একটি স্থির অবস্থা আছে কিন্তু নির্দিষ্ট সংখ্যক চক্র পুনরাবৃত্তি করতে হয়, অ্যাসিঙ্ক্রোনাসভাবে এক্সিকিউট করতে হয় এমন সমস্যা, এবং অনেক বেশি ইটারেশনের প্রয়োজন হয় এমন পরিস্থিতি।

লুপিং বনাম রিকার্সিভ কৌশল: ইন্দিরার দুশ্চিন্তা

ইন্দিরার মাসিক সোশ্যাল সিকিউরিটি প্রতি মাসের দ্বিতীয় বুধবার তাঁর ব্যাংক অ্যাকাউন্টে স্বয়ংক্রিয়ভাবে জমা হয়। ইন্দিরা তাঁর চেক বইয়ের হিসাব মেলানো নিয়ে চিন্তিত। তাঁর ভয়, টাকা জমা হওয়ার আগেই তিনি চেক লিখে ফেলবেন। তিনি তাঁর নাতনি আদ্যাকে অনুরোধ করেন, তাঁর অ্যাকাউন্টে টাকা কখন কখন আসবে সেই তারিখের একটি তালিকা দিতে।

আদ্যা সবেমাত্র Python-এ প্রোগ্রামিং শিখছেন, এবং প্রথম যা মনে আসে তার ভিত্তিতে একটি প্রোগ্রাম লেখেন। তিনি জমার তারিখগুলোর একটি list রিটার্ন করতে চান, যাতে সেগুলো প্রিন্ট করা যায়। তিনি এমন একটি ফাংশন লিখতে চান যা যেকোনো বছরের জন্য কাজ করবে। সূচি বদলে গেলে (বা অন্য আত্মীয়রা যদি আদ্যাকে তাদের জমার সূচি হিসাব করতে চান), তিনি সিদ্ধান্ত নেন যে ফাংশনটির বারের জন্য একটি অতিরিক্ত প্যারামিটার নেওয়া দরকার। সবশেষে, আদ্যা সিদ্ধান্ত নেন যে ফাংশনটির জন্য মাসের কোন বারটি তা বোঝাতে একটি প্যারামিটার দরকার: প্রথম, দ্বিতীয়, ইত্যাদি। এই সব প্রয়োজন মেটাতে, তিনি datetime থেকে ইমপোর্ট করা date ক্লাসটি ব্যবহার করার সিদ্ধান্ত নেন। এই সব একসাথে করে, আদ্যা লেখেন:

from datetime import date


def paydates_for_year(year, weekday, ordinal):
    """Returns a list of the matching weekday dates.
    
    Arguments:
        year (int): The year (e.g. 2022).
        weekday (int): The weekday number (e.g. 3 for Wednesday).
        ordinal (int): Which weekday of the month (e.g. 2 for the second day).
    
    Returns:
        output (list): Matching weekday dates.
    """
    
    output = []

    for month in range(1, 13):
        for day_num in range(1, 8):
            if date(year, month, day_num).isoweekday() == weekday:
                output.append(date(year, month, day_num + (ordinal - 1) * 7))
                break
    return output

# find the second Wednesday of the month for all the months in 2022
print(paydates_for_year(2022, 3, 2))

এই প্রথম ইটারেশনটি কাজ করে, তবে আদ্যা ভাবেন, কোডটি কীভাবে রিফ্যাক্টর করে কম লাইন আর কম নেস্টেড লুপ ব্যবহার করা যায়। তিনি আরও পড়েছেন যে স্টেট পরিবর্তন কমানো ভালো, তাই তিনি দেখতে চান, output, month আর day_num-এর মতো কিছু ভ্যারিয়েবলের মান পরিবর্তন এড়ানো যায় কি না।

তিনি রিকার্সন সম্পর্কেও জানেন, এবং ভাবেন কীভাবে তাঁর প্রোগ্রামটি রিকার্সিভ পদ্ধতিতে বদলানো যায়। তাঁর লুপিং ফাংশনে যেসব ভ্যারিয়েবল তৈরি ও পরিবর্তন করা হয়, সেগুলো বদলে আর্গুমেন্ট হিসেবে পাঠানো যেতে পারে। ফাংশনের ভেতরে ভ্যারিয়েবলগুলো পরিবর্তন করার বদলে, তিনি পরবর্তী ফাংশন কলে হালনাগাদ করা মান আর্গুমেন্ট হিসেবে পাঠাতে পারেন। এই ইচ্ছা নিয়ে তিনি এই রিকার্সিভ পদ্ধতিতে পৌঁছান:

from datetime import date


def paydates_for_year_rec(year, weekday, ordinal, month, day_num, output):
    """Returns a list of the matching weekday dates
    
    Arguments:
        year (int): The year (e.g. 2022).
        weekday (int): The weekday number (e.g. 3 for Wednesday).
        ordinal (int): Which weekday of the month (e.g. 2 for the second day).
        month (int): The month number currently being processed.
        day_num (int): The day number of the month currently being processed.
    
    Returns:
        output (list): Matching weekday dates.
    """
    
    if month == 13:
        return output
        
    if date(year, month, day_num).isoweekday() == weekday:
        return paydates_for_year_rec(
                 year, weekday, ordinal, month + 1, 1, output
                 + [date(year, month, day_num + (ordinal - 1) * 7)]
                 )
    
    return paydates_for_year_rec(year, weekday, ordinal, month, day_num + 1, output)

# find the second Wednesday of the month for all the months in 2022
print(paydates_for_year_rec(2022, 3, 2, 1, 1, []))

আদ্যা খুশি যে আর কোনো নেস্টেড লুপ নেই, কোনো পরিবর্তিত স্টেট নেই, এবং কোড ২ লাইন কম!

তিনি একটু চিন্তিত যে রিকার্সিভ পদ্ধতিটি লুপিং পদ্ধতির চেয়ে বেশি ধাপ ব্যবহার করে, তাই এটি কম "পারফরম্যান্ট"। তবে রিকার্সন ব্যবহার করে সমস্যাটি নতুন করে লেখা নিশ্চিতভাবেই তাঁকে কুৎসিত নেস্টেড লুপিং (পারফরম্যান্সের জন্য ঝুঁকি), ব্যাপক স্টেট পরিবর্তন, আর জটিল শর্তভিত্তিক লজিক নিয়ে বিভ্রান্তি সামলাতে সাহায্য করেছে। এটি আরও "পাঠযোগ্য"ও লাগে। তিনি নিশ্চিত যে বিরতির পর এই কোডে ফিরে এলে, তিনি সহজেই পড়ে যেতে পারবেন এবং এটি কী করে তা মনে করতে পারবেন।

ভবিষ্যতে, আদ্যা হয়তো প্রথমে সমস্যাগুলো রিকার্সিভভাবে সমাধান করার চেষ্টা করবেন। নেস্টিং, পরিবর্তন আর জটিলতা কম থাকলে, প্রথমে স্পষ্ট ধাপে সমস্যাটি নিয়ে এগোনো তাঁর কাছে সহজ লাগতে পারে। মূল লজিক বের করার পর, তিনি তাঁর শুরুর রিকার্সিভ ধাপগুলোকে আরও পারফরম্যান্ট লুপিং পদ্ধতিতে অপ্টিমাইজ করার দিকে মন দিতে পারেন।

আরও পরে, যখন তিনি tuples সম্পর্কে শিখবেন, আদ্যা আরও "অপ্টিমাইজ" করার উপায় ভাবতে পারেন, যেমন Calendar.itermonthdates-এর সাথে একটি list comprehension ব্যবহার করা, বা নির্দিষ্ট কিছু মান মেমোয়াইজ করা।

রিকার্সিভ প্রকরণ: টেইল কল

টেইল কল হলো যখন একটি ফাংশনের শেষ স্টেটমেন্ট কেবল নিজেকেই কল করে, আর কিছু নয়। এই উদাহরণটি টেইল কল নয়, কারণ ফাংশনটি নিজেকে কল করার ফলাফলের সাথে 1 যোগ করে:

def print_increment(step, max_value):
    if step > max_value:
        return 1
    print(f'The step is {step}')
    return 1 + print_increment(step + 1, max_value)


def main():
    retval = print_increment(1, 2)
    print(f'retval is {retval} after recursion')

if __name__ == "__main__":
    main()

এটি প্রিন্ট করবে:

The step is 1
The step is 2
retval is 3 after recursion

এটিকে টেইল কলে রিফ্যাক্টর করতে, retval-কে print_increment-এর একটি প্যারামিটার বানান।

def print_increment(step, max_value, retval):
    if step > max_value:
        return retval
    print(f'The step is {step}')
    return print_increment(step + 1, max_value, retval + 1)


def main():
    retval = print_increment(1, 2, 1)
    print(f'retval is {retval} after recursion')

if __name__ == "__main__":
    main()

টেইল কল নয় এমন রিকার্সিভ কলের চেয়ে টেইল কল হয়তো আরও সহজে বোঝা যেতে পারে। তবে, রিকার্সন ব্যবহার করার সময় সবসময় জানা জরুরি যে এত বেশি ইটারেশন হবে না যাতে স্ট্যাক ওভারফ্লো হয়।

Python-এ রিকার্সনের সীমা

কিছু ভাষা টেইল কল অপ্টিমাইজ করতে পারে, যাতে প্রতিটি রিকার্সিভ কল স্ট্যাকে অতিরিক্ত ফ্রেম যোগ করার বদলে ফাংশনের প্রথম কলের স্ট্যাক ফ্রেম পুনরায় ব্যবহার করে (লুপ কীভাবে একটি ফ্রেম পুনরায় ব্যবহার করে, তার মতোই)। Python সেই ভাষাগুলোর একটি নয়। স্ট্যাক ওভারফ্লো ঠেকাতে, Python-এর একটি রিকার্সন সীমা আছে, যার ডিফল্ট এক হাজার ফ্রেম। ইন্টারপ্রেটার বুঝতে পারলে যে রিকার্সন সীমা ছাড়িয়ে গেছে, তখন একটি RecursionError এক্সসেপশন উত্থাপিত হয়। রিকার্সন সীমা বাড়াতে sys.setrecursionlimit মেথড ব্যবহার করা সম্ভব, তবে তা করলে রানটাইমে সেগমেন্টেশন ফল্ট হওয়ার ঝুঁকি থাকে, যা প্রোগ্রাম, আর সম্ভবত অপারেটিং সিস্টেমও ক্র্যাশ করাতে পারে।

রিসোর্স

Python-এ রিকার্সন ব্যবহার সম্পর্কে আরও জানতে আপনি শুরু করতে পারেন এগুলো দিয়ে

• python-programming: recursion
• Real Python: python-recursion
• Real Python: python-thinking-recursively