रिकर्शन में

रिकर्शन के बारे में

रिकर्शन एक तरीका है जिसमें एक फंक्शन खुद को कॉल करके अपने अंदर का कोड बार-बार चलाता है। जो फंक्शन खुद को कॉल करते हैं, उन्हें रिकर्सिव फंक्शन कहते हैं। रिकर्शन को लूप चलाने या दोहराने का एक और तरीका माना जा सकता है। और लूप की तरह ही, यह तय करने के लिए कि रिकर्शन कब रुके, एक बूलियन एक्सप्रेशन या 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, []))

आद्या खुश है कि अब कोई नेस्टेड लूप नहीं है, कोई स्थिति नहीं बदलती, और कोड की 2 लाइनें कम हैं!

उसे थोड़ी चिंता है कि रिकर्शन वाला तरीका लूप वाले तरीके से ज़्यादा कदम लेता है, इसलिए वह कम "परफॉर्मेंट" है। लेकिन समस्या को रिकर्शन से दोबारा लिखने से उसे बदसूरत नेस्टेड लूपिंग (प्रदर्शन के लिए एक खतरा), बड़े पैमाने पर स्थिति बदलने, और जटिल शर्त वाले लॉजिक की उलझन से निपटने में ज़रूर मदद मिली है। यह कोड पढ़ने में भी ज़्यादा "आसान" लगता है। उसे यकीन है कि कुछ समय बाद जब वह इस कोड पर वापस आएगी, तो वह इसे पढ़कर आसानी से याद कर पाएगी कि यह क्या करता है।

आगे चलकर आद्या शायद पहले समस्याओं को रिकर्शन से हल करने की कोशिश करे। जब नेस्टिंग, स्थिति बदलना और जटिलता कम हो, तो उसे शुरू में समस्या को साफ-साफ कदमों में समझना आसान लग सकता है। बुनियादी लॉजिक तैयार करने के बाद वह अपने शुरुआती रिकर्शन वाले कदमों को ज़्यादा परफॉर्मेंट लूपिंग वाले तरीके में बदलने पर ध्यान दे सकती है।

और भी आगे, जब वह 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 में रिकर्शन की एक सीमा होती है, जो डिफॉल्ट रूप से एक हज़ार फ्रेम है। जब इंटरप्रेटर को पता चलता है कि रिकर्शन की सीमा पार हो गई है, तो Python एक RecursionError एक्सेप्शन देता है। रिकर्शन की सीमा बढ़ाने के लिए sys.setrecursionlimit मेथड इस्तेमाल की जा सकती है, लेकिन ऐसा करने पर रनटाइम में सेगमेंटेशन फॉल्ट होने का खतरा रहता है, जो प्रोग्राम को, और शायद ऑपरेटिंग सिस्टम को भी, क्रैश कर देगा।

संसाधन

Python में रिकर्शन के इस्तेमाल के बारे में और जानने के लिए आप इनसे शुरू कर सकते हैं:

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