Recursion (रिकर्शन)

जब हम प्रोग्राम लिखते हैं, तो आमतौर पर किसी विशेष काम को करने के लिए अलग-अलग फ़ंक्शन को कॉल करते हैं। उदाहरण के लिए, किसी संख्या का वर्गमूल निकालने के लिए हम sqrt को कॉल कर लेते हैं, या अधिकतम/न्यूनतम मान खोजने के लिए max/min फ़ंक्शन को। लेकिन रिकर्शन उस प्रक्रिया को कहते हैं जिसमें वही फ़ंक्शन खुद को ही दोबारा कॉल करता है। यानी, अगर हमने कोई फ़ंक्शन f नाम से परिभाषित किया है और उसी f को उसके शरीर (बॉडी) के अंदर कहीं दोबारा (आमतौर पर भिन्न आर्ग्युमेंट के साथ) कॉल करते हैं, तो यह एक रिकर्सिव कॉल कहलाती है:

def f(n):                                   # f नाम का फ़ंक्शन परिभाषित करें
    print(f'f() called with argument {n}')  # प्रत्येक कॉल पर प्रिंट करें (डेमोंस्ट्रेशन के लिए)
    if n <= 0:                              # अगर n नकारात्मक हो जाए, तो रुक जाएँ
        print('Let\'s stop here...')
    else:                                   # वरना f को एक छोटे מספר पर_CALLBACK_CALL_        
        f(n - 1)

f(10)

f() called with argument 10
f() called with argument 9
f() called with argument 8
f() called with argument 7
f() called with argument 6
f() called with argument 5
f() called with argument 4
f() called with argument 3
f() called with argument 2
f() called with argument 1
f() called with argument 0
Let's stop here...

यह एक छोटा सा उदाहरण है जो दिखाता है कि एक बुनियादी रिकर्सिव फ़ंक्शन कैसे बनाया जा सकता है। व्यावहारिक उपयोग में हम अक्सर फ़ंक्शन के अंदर कुछ गणनाएँ (computation) करके उसके परिणाम लौटाते हैं, बजाय सिर्फ प्रिंट करने के।

एल्गोरिथम से जुड़ी कई समस्याओं में, खासतौर पर जो ग्राफ़, उन्नत सॉर्टिंग एल्गोरिथम या बैक्ट्रैकिंग से जुड़ी हों (जिन्हें हम बाद में कोर्स में देखेंगे), रिकर्शन बहुत मददगार होता है। ऐसी समस्याएँ आम हैं, और कई बार रिकर्सिव समाधान लिखना इटरेटिव (लूप इस्तेमाल करने वाला) समाधान लिखने से कहीं आसान होता है।

किसी बड़े कार्य को हल करने के लिए उसे छोटे-छोटे उपकार्य में बाँटते जाना, जब तक कि हम सबसे छोटे/आसान स्थिति पर न पहुँच जाएँ, “recursive leap of faith” नामक अवधारणा से सबसे अच्छी तरह समझा जा सकता है।

Recursive Leap of Faith

जब हम किसी समस्या के लिए रिकर्सिव समाधान बनाते हैं, तो अक्सर ऐसा फ़ंक्शन बनाते हैं जो अपने अंदर ही खुद को किसी बिंदु पर कॉल करता है। इसी कॉल को रिकर्सिव कॉल कहते हैं।

रिकर्सिव समाधान की खूबी यह है कि आप मानकर चल सकते हैं कि जब फ़ंक्शन किसी सरल आर्ग्युमेंट के साथ कॉल किया जाएगा तो वह सही काम करेगा, और इसके आधार पर आप कठिन मामलों के लिए सही कार्यान्वयन कर सकते हैं। ठीक उसी तरह जैसे sqrt, max, या abs को कॉल करते हुए हम मान लेते हैं कि वे सही काम करेंगे, उसी तरह आप अपने बनने वाले फ़ंक्शन के कुछ छोटे/सरल पैरामीटर पर सही तरह से काम करने की कल्पना करके बड़े इनपुट पर उसी लॉजिक को लागू कर सकते हैं।

रिकर्सिव फ़ंक्शन के अंदर किसी गणना को दिखाने के लिए हम यह उदाहरण देख सकते हैं कि कैसे 0 से n तक (0, 1, 2, …, n) की राशि (sum) को रिकर्सिव तरीक़े से निकाला जाए।

आइए sum फ़ंक्शन को चरणबद्ध तरीके से बनाते हैं। सबसे पहले, यह सुनिश्चित कीजिए कि फ़ंक्शन सबसे सरल केस (जब n = 0 या 1 हो) पर सही ढंग से काम करे:

def sum(n):
    print(f'sum({n})', end=' -> ')
    if n == 0:         # अगर n = 0 है, तो परिणाम 0 होना चाहिए
        return 0       # यहाँ फ़ंक्शन Execution रुक जाता है
    if n == 1:         # अगर n = 1 है, तो परिणाम 1 होना चाहिए
        return 1       # यहाँ फ़ंक्शन Execution रुक जाता है

print(sum(1))          # sum(1) -> 1
print(sum(0))          # sum(0) -> 0
print(sum(2))          # sum(2) -> None (क्योंकि हमने अभी वो हिस्सा नहीं लिखा है)

इस हिस्से से हमें इतना मिल जाता है कि sum(0) हमेशा 0 लौटाएगा और sum(1) हमेशा 1। ये दोनों कॉल हमारे फ़ंक्शन के अंदर भी ठीक से चलेंगे, यदि हम sum को इन्हीं वैल्यूज़ के साथ फिर से कॉल करें।

अब हम एक कदम आगे बढ़कर n = 2 और n = 3 के लिए भी sum फ़ंक्शन को तैयार कर सकते हैं, क्योंकि हमें sum(1) और sum(0) के सही परिणाम मिलेंगे:

def sum(n):
    print(f'sum({n})', end=' -> ')
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n == 2:             # अगर n = 2 है, तो sum(1) के परिणाम में 2 जोड़ दें
        return n + sum(1)  # या n + sum(n - 1)
    if n == 3:             # अगर n = 3 है, तो sum(2) के परिणाम में 3 जोड़ दें
        return n + sum(2)  # या n + sum(n - 1)

print(sum(1))          # sum(1) -> 1
print(sum(0))          # sum(0) -> 0
print(sum(2))          # sum(2) -> sum(1) -> 3
print(sum(3))          # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4))          # sum(4) -> None (अभी यह हिस्सा Implement नहीं किया)

इस तरह, यह साफ़ है कि n = 0, 1, 2, 3 के लिए sum फ़ंक्शन सही परिणाम देता है।

अब बाकी मानों के लिए (e.g., n = 4, 5, 6, …) हमें बस इतना करना है कि फ़ंक्शन को बार-बार खुद को कॉल करते हुए इन छोटे मानों तक पहुँचना चाहिए (0, 1, 2, या 3)। उदाहरण के लिए, sum(4) के लिए हम 4 को sum(3) के परिणाम में जोड़ देंगे, sum(5) के लिए 5 को sum(4) के परिणाम में जोड़ेंगे:

def sum(n):
    print(f'sum({n})', end=' -> ')
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return n + sum(1)
    if n == 3:
        return n + sum(2)
    # बाक़ी सभी मामलों (4, 5, 6, ...)
    return n + sum(n - 1)

print(sum(2))          # sum(2) -> sum(1) -> 3
print(sum(3))          # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4))          # sum(4) -> sum(3) -> sum(2) -> sum(1) -> 10
# ...

एक रिकर्सिव फ़ंक्शन के दो प्रमुख हिस्से होते हैं:

1. Base case: वह शर्त जो रिकर्शन को रोकती है। इसके बिना फ़ंक्शन अनंत रूप से खुद को कॉल करता रहेगा और कभी ख़तम नहीं होगा। यहाँ पर हमारा बेस केस n == 0 (और शुरू में हमने n == 1 भी रखा था) है।

2. Recursive step: जहाँ फ़ंक्शन खुद को दोबारा कॉल करता है, आमतौर पर थोड़े बदले हुए आर्ग्युमेंट के साथ। यहाँ sum(n - 1) हमारी रिकर्सिव कॉल है।

क्योंकि n == 1, n == 2, और n == 3 के लिए कॉल ठीक उसी तरह काम करती है जैसे n == 4, 5, … के लिए, इसलिए हम sum फ़ंक्शन को और भी सरल बना सकते हैं ताकि हमारे पास केवल 1 बेस केस (n == 0) रह जाए:

def sum(n):
    print(f'sum({n})', end=' -> ')
    if n == 0:
        return 0
    return n + sum(n - 1)

print(sum(2))          # sum(2) -> sum(1) -> sum(0) -> 3
print(sum(3))          # sum(3) -> sum(2) -> sum(1) -> sum(0) -> 6
print(sum(4))          # sum(4) -> sum(3) -> sum(2) -> sum(1) -> sum(0) -> 10
# ...

इस तरह, “recursive leap of faith” का इस्तेमाल करते हुए हम यह मान लेते हैं कि छोटा/सरल केस सही ढंग से चलता है, और उसी आधार पर हम बड़े केस का हल निकाल लेते हैं। इससे समझ आता है कि रिकर्सिव फ़ंक्शन कैसे काम करते हैं और उन्हें कैसे बनाया जा सकता है।

Challenge

एक रिकर्सिव फ़ंक्शन बनाइए जो n! को से गुणा-भाग करने के बाद सही परिणाम दे।

इनपुट

इनपुट में एक मात्र पूर्णांक n दिया गया है (1 ≤ n ≤ 1000)।

आउटपुट

प्रोग्राम को n! को से मॉड लेकर उसका परिणाम प्रिंट करना चाहिए।

उदाहरण