Python में Recursive Functions को समझें

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

इन्हीं बुनियादी अवधारणाओं में से एक है Recursion, और यह कुछ विशेष प्रकार के फंक्शनों को लिखते समय जानना बेहद ज़रूरी है। आप पहले से जानते होंगे — "जब कोई फंक्शन खुद को कॉल करता है, उसे Recursion कहते हैं।" लेकिन अंदर क्या होता है? Recursion से फिज़िकल मेमोरी पर क्या असर पड़ता है? क्या आप हर फंक्शन को recursive बना सकते हैं? इस ट्यूटोरियल में, आपको इन बुनियादी सवालों के जवाब मिलेंगे।

एक recursive फंक्शन की संरचना:

आपने अपने कंप्यूटर साइंस या इंफॉर्मेशन टेक्नोलॉजी के स्नातक पाठ्यक्रम में Recursion शब्द सुना होगा। इस खंड में, आप उन्हीं अवधारणाओं को एक दिलचस्प तरीके से दोहराएँगे। चलिए शुरू करते हैं।

Recursion की परिभाषा पर वापस चलते हैं: "जब कोई फंक्शन खुद को कॉल करता है, उसे Recursion कहते हैं"। इस परिभाषा को समझने के लिए एक उदाहरण लेते हैं:

void A(n){
    if(n>=1){
        A(n-1);
        print(n);
    }
}

आप देख सकते हैं कि A() फंक्शन खुद को कॉल कर रहा है। यह recursion का उदाहरण है, और A() एक recursive फंक्शन है।

अब एक recursive फंक्शन की कुछ बुनियादी बातें देखते हैं।

Recursive फंक्शन की बुनियाद:

एक recursive फंक्शन में निम्नलिखित दो विशेषताएँ होना आवश्यक है:

• एक recurrence relation
• एक termination condition

इन बिंदुओं को समझने के लिए ऊपर दिया गया कोड स्निपेट देखें। स्पष्ट है, फंक्शन एक विशिष्ट recurrence relation का पालन करता है:

$n\le 1$ यहाँ terminating condition / anchor condition / base condition है, और इसके पूरा होते ही recursion रुक जाता है। इस शर्त को निर्दिष्ट करना अनिवार्य है, वरना फंक्शन अनंत लूप में चला जाएगा।

(कृपया ध्यान दें कि ऊपर दिया गया कोड स्निपेट किसी विशेष प्रोग्रामिंग भाषा का सख्ती से पालन नहीं करता। यहाँ उद्देश्य केवल एक recursive फंक्शन का उदाहरण दिखाना है।)

आप सोच रहे होंगे, जब बेहतर विकल्प उपलब्ध हों तो कोई recursive फंक्शन क्यों लिखे? हाँ, कभी-कभी recursion को ट्रेस करना कठिन हो सकता है, लेकिन अभ्यास हो जाने पर आप पाएँगे कि प्रोग्राम पठनीयता और वेरिएबल्स के संदर्भ में recursion सुंदर होता है। Recursion को चलने के लिए अतिरिक्त वेरिएबल्स की ज़रूरत नहीं होती, लेकिन रुकने के लिए उचित termination condition चाहिए। अक्सर, recursion के लिए termination condition ढूँढना कठिन होता है। फिर भी, "अभ्यास से सिद्धि"। आगे इस ट्यूटोरियल में, आप देखेंगे कि पारंपरिक तरीकों के बजाय recursion से प्रोग्राम कितना सुंदर और छोटा हो सकता है। अब आप एक recursive फंक्शन के मेमोरी रिप्रेज़ेंटेशन का अध्ययन करेंगे।

Recursive फंक्शन का मेमोरी रिप्रेज़ेंटेशन:

इस खंड में, आप अध्ययन करेंगे कि मेमोरी में recursive फंक्शनों को मूल रूप से ट्री और स्टैक के माध्यम से कैसे दर्शाया जाता है। इसे समझने के लिए नीचे दिए गए recursive फंक्शन A() पर विचार करते हैं:

void A(n){
    if(n>=1){
        A(n-1);
        print(n);
    }
}

आप पहले ट्री का उपयोग करके मेमोरी रिप्रेज़ेंटेशन समझेंगे। यह सुनने में कठिन लग सकता है, लेकिन यह काफी सरल है। यदि आप प्रत्येक फंक्शन कॉल को ट्री की तरह लिखें, तो वह कैसा दिखेगा?

कुछ इस तरह?

यहाँ कुछ बिंदु ध्यान देने योग्य हैं:

• फंक्शन को A(3) के साथ कॉल किया गया है और इसके लिए यहाँ 4 (3+1) फंक्शन कॉल्स हुए हैं। इसे सामान्यीकृत करें तो, यदि A(n) कॉल किया जाए तो कुल (n+1) फंक्शन कॉल्स लगेंगे।
• P() कॉल्स, print(n) से उत्पन्न प्रिंट्स हैं।
• फंक्शन A(0) कॉल पर इसलिए रुक गया क्योंकि उसके बाद आने वाला if स्टेटमेंट (A(0) के बाद) को n < 1 मिलेगा, जिससे फंक्शन terminate हो जाएगा।

आपने पहले यह ट्री जैसा रिप्रेज़ेंटेशन इसलिए देखा क्योंकि स्टैक पर recursive फंक्शन को दर्शाने के लिए इसकी ज़रूरत होती है। अब आप यह देखेंगे।

(स्टैक एक डेटा स्ट्रक्चर है जो लास्ट-इन-फर्स्ट-आउट (LIFO) क्रम का पालन करता है)

स्टैक रिप्रेज़ेंटेशन के लिए, आपको ट्री को ऊपर-से-नीचे और बाएँ-से-दाएँ क्रम में ट्रैवर्स करना होगा। नीचे दी गई छवि इसे स्पष्ट करेगी।

इस थोड़े अजीब दिखने वाले (ट्री) को समझते हैं। याद रखें कि एक स्टैक में दो ऑपरेशन्स होते हैं — 1. Push, जिससे आप स्टैक में तत्व डालते हैं, और 2. Pop, जिससे आप स्टैक से तत्व निकालते हैं।

अब, आप ट्री ट्रैवर्सल ऊपर-से-नीचे और बाएँ-से-दाएँ क्रम में शुरू करते हैं:

• जहाँ भी फंक्शन कॉल दिखे, उसे स्टैक पर पुश करें।
• यदि print()/P() कॉल दिखे, तो संबंधित तत्व को उसी क्रम में प्रिंट करें।

नीचे A(3) से A(0) तक के टॉप-डाउन ट्रैवर्सल का परिणामस्वरूप स्टैक के तत्व दिखाए गए हैं:

अब आप ट्रैवर्सल के दूसरे हिस्से, यानी बाएँ-से-दाएँ क्रम को शुरू करते हैं। जब भी आपको किसी फंक्शन कॉल से दूसरी बार सामना हो, आप उसे पॉप करेंगे। चौंकाने वाली बात यह है कि स्टैक का पहला पॉप होने वाला तत्व (A(0)) वही था जो सबसे आख़िर में स्टैक में आया था (LIFO, याद है?). अब रास्ते में आपको तीन P() कॉल्स मिलेंगी — P(1), P(2) और P(3)। आप इन्हें ट्रैवर्सल के क्रम में ही प्रिंट करेंगे। क्रम होगा:

अंत में, जब आप ट्रैवर्सल प्रक्रिया पूरी कर लेंगे, स्टैक पूरी तरह खाली होगा। पॉप ऑपरेशन को और बेहतर समझने के लिए, नीचे पूरी तरह पॉप हो जाने के बाद के स्टैक की छवि दी गई है।

आपने देखा कि एक साधारण recursive फंक्शन को ट्री और स्टैक की मदद से मेमोरी पर कैसे दर्शाया जा सकता है। अब आप देखेंगे कि recursion को कैसे ट्रेस किया जाए।

Recursion को ट्रेस करना:

इस खंड में, आप सीखेंगे कि किसी recursion को व्यवस्थित रूप से कैसे ट्रेस किया जाए। निम्नलिखित recursive फंक्शन पर विचार करें:

void A(n){
    if(n>0){
        print(n-1);
        A(n-1);
    }
}

यहाँ एक महत्वपूर्ण बिंदु यह है कि जब भी कोई फंक्शन कॉल होता है, मेमोरी में एक activation record बनता है, जिसमें उस फंक्शन के local variables और एक instruction pointer होता है (जो यह बताता है कि कॉल वापस आने पर अगला कार्य कौन सा है)। मान लें कि main() नामक फंक्शन ने ऊपर दिए गए A() को A(3) के रूप में कॉल किया। बेहतर समझ के लिए if स्टेटमेंट से A() की पंक्तियों को क्रमांकित करते हैं:

void A(n){
    1. if(n>0)
    2. {
        3. print(n-1);
        4. A(n-1);
    5. }
}

Activation records कुछ इस प्रकार दिखेंगे:

जैसा पहले उल्लेख किया, फंक्शनों के पास अपने local variables और instruction pointers (यहाँ लाइन नंबर) की प्रतियाँ होती हैं। A(0) के बाद A() फंक्शन terminate हो जाएगा और पॉपिंग होने लगेगी। ध्यान दें, यहाँ हॉरिज़ॉन्टल स्टैक दिखाया गया है, जो ट्यूटोरियल में पहले देखे गए स्टैक्स के समान ही है। जब records स्टैक पर पुश हो रहे होंगे, उसी दौरान प्रिंट भी होंगे और निम्न तत्व प्रिंट होंगे:

Instruction pointers यहाँ महत्वपूर्ण हैं क्योंकि अक्सर recursive फंक्शन में नियंत्रण उसी फंक्शन में जाता है, लेकिन वेरिएबल का मान अलग होता है। सब कुछ समन्वय में रखने के लिए ये pointers बहुत मदद करते हैं। आप इसी प्रक्रिया का पालन कर ट्री रिप्रेज़ेंटेशन का उपयोग करते हुए recursion को ट्रेस कर सकते हैं।

अब आप सीखेंगे कि किसी recursive फंक्शन का space-time विश्लेषण कैसे किया जाए।

Recursive फंक्शन का space-time विश्लेषण:

DataCamp पर Asymptotic Analysis in Python पर एक शानदार लेख है, और इस खंड को पढ़ने से पहले उसे देखना अनुशंसित है। जल्दी से दोहरा लें कि किसी फंक्शन के space और time विश्लेषण (जिन्हें क्रमशः space complexity और time complexity भी कहा जाता है) का क्या अभिप्राय है:

किसी दिए गए इनपुट पर, एक फंक्शन को कुछ आउटपुट पैदा करना होता है। ऐसा करने में फंक्शन कितना समय लेता है? Time-complexity इस समय का अनुमान देती है, और इसे फंक्शन का runtime भी कहते हैं। इसी प्रकार, space-complexity फंक्शन की स्पेस (मेमोरी) आवश्यकताओं का अनुमान देती है, यानी किसी दिए गए इनपुट के लिए। लेकिन इनकी ज़रूरत क्यों है?

• अलग-अलग आकार के इनपुट पर फंक्शन को चलाने के बजाय, आप आसानी से अनुमान लगा सकते हैं कि विभिन्न आकारों के इनपुट पर फंक्शन कैसा व्यवहार कर सकता है।
• यदि आपके पास दो फंक्शन हैं जो एक ही उद्देश्य पूरा कर रहे हैं, तो आप किसे चुनेंगे? निर्णय लेने के लिए आप किन मापदंडों पर विचार करेंगे? जी हाँ, आप उनके space और time complexities का विश्लेषण कर उनकी तुलना करेंगे और देखेंगे कि कौन बेहतर प्रदर्शन कर रहा है।

अब एक सरल recursive फंक्शन लेते हैं और उसकी space और time complexity का विश्लेषण करते हैं।

void A(n){
    if(n>1) // Anchor condition
    {
       return A(n-1);
    }
}

पहले time complexity का विश्लेषण करते हैं। मान लें कि ऊपर दिए गए A() फंक्शन का कुल समय $T(n)$ है। अब $T(n)$, n को 1 से बड़ा होने की जाँच करने में लगने वाले समय और A(n-1) के निष्पादन में लगने वाले समय का योग है। इसलिए, $T(n)$ को इस प्रकार लिखा जा सकता है —

यहाँ 1 तुलना में लगा समय है (आप कोई भी स्थिरांक रख सकते हैं)। अब, A(n-1) के निष्पादन में (यानी $T(n)$ के संदर्भ में) कितना समय लगेगा?

इसी प्रकार,

आदि।

यदि आप इन समीकरणों पर ध्यान दें, तो ये सभी जुड़े हुए हैं। हैं ना? यदि आप इन्हें क्रमशः प्रतिस्थापित करें, तो मिलेगा —

$T(n)$ = 1 + (1 + $T(n-2)$) = 2 + $T(n-2)$ = 3 + $T(n-3)$ = .... = k + $T(n-k)$ (फंक्शन को k चरण चलाने के बाद)

अब, आपको निर्धारित करना है कि फंक्शन किस बिंदु पर रुकने वाला है। दी हुई anchor condition के अनुसार, आप लिख सकते हैं —

मान लें कि k चरणों के बाद फंक्शन रुक जाता है। यदि ऐसा है, तो अवश्य —

$n - k = 1 => k = n - 1$

अब $T(n) = k + T(n-k)$ में k (= n -1) का मान रखें:

$T(n) = (n-1) + T(n-(n-1))$
$=> T(n) = (n-1) + T(1)$
$=> T(n) = n-1 + 1 = n$ // T(1) के लिए केवल तुलना आवश्यक है

Asymptotic analysis के नियम से, $T(n) = n$ को $T(n) = \mathcal{O}(n)$ लिखा जा सकता है। इसका अर्थ है कि फंक्शन की (worst) time complexity $\mathcal{O}(n)$ है।

यहाँ थोड़ा ठहरें और इस प्रक्रिया के हर चरण को ध्यान से देखें। अत्यधिक अनुशंसा है कि आप इसे कागज़-कलम पर करके हर हिस्से को समझें।

फंक्शन का space complexity विश्लेषण सरल है। यह एक in-memory फंक्शन है और किसी अतिरिक्त वेरिएबल का उपयोग नहीं करता। इसलिए, आप निष्कर्ष निकाल सकते हैं कि फंक्शन का space complexity $\mathcal{O}(n)$ है।

अब आप इन सबको साथ रखते हुए Python में एक सरल recursive फंक्शन लागू करेंगे।

Python में एक सरल recursive फंक्शन लागू करना:

आप एक recursive फंक्शन लिखेंगे जो दिए गए संख्या का factorial निकाले। फिर आप उसी फंक्शन का iterative संस्करण लिखेंगे। चलिए शुरू करते हैं।

# Recursive function factorial_recursion()

def factorial_recursion(n):  
   if n == 1:  
       return n  
   else:  
       return n*factorial_recursion(n-1)

# Call the function

num = 7
print("The factorial of ",num," is ",factorial_recursion(num))

The factorial of  7  is  5040

Recursive फंक्शन लिखने के दो मुख्य घटक याद हैं?

• Recurrence relation
• Termination condition

इस मामले में, recurrence relation होगा —

$f(n) = n!$
$f(n) = n * f(n-1)$ आदि।

Termination condition तब है जब n बराबर 1 हो।

सरल है, है ना?

अब, आप उसी फंक्शन का iterative संस्करण लागू करेंगे।

def factorial_iterative(num):
    factorial = 1
    if num < 0:
        print("Sorry, factorial does not exist for negative numbers")
    elif num == 0:
        print("The factorial of 0 is 1")
    else:
        for i in range(1,num + 1):
           factorial = factorial*i
        print("The factorial of",num,"is",factorial)

factorial_iterative(7)

The factorial of 7 is 5040

आप दोनों संस्करणों के बीच का अंतर साफ़ देख सकते हैं। Recursive संस्करण, iterative संस्करण की तुलना में कहीं अधिक सुंदर है। है ना?

बधाई!

आप अंत तक पहुँच गए हैं। इस ट्यूटोरियल में आपने recursive फंक्शन्स का व्यापक अध्ययन किया। एकदम बुनियाद से लेकर recursive फंक्शन की space और time complexities के विश्लेषण तक, आपने सब कवर किया। आपने यह भी देखा कि कैसे recursion कुछ विशिष्ट गुणों वाली समस्याओं को हल करने में फायदेमंद हो सकता है। अब आप recursion का उपयोग करके (जिनमें recurrence relation और termination condition हो) समस्याएँ हल करने की स्थिति में होने चाहिए। आप recursion का उपयोग करके किसी रेंज में Fibonacci Numbers निकालने की समस्या हल करना चाहेंगे।

मैं आग्रह करूँगा कि आप Binary Search, Merge Sort, Tower of Hanoi आदि जैसी सामान्य समस्याएँ recursion से हल करें और उनका space-time विश्लेषण भी करें। यह निश्चित ही आपको बेहतर प्रोग्रामर बनाएगा।

प्रारंभिक स्तर पर, आपने जो कवर किया, वह पर्याप्त है। लेकिन यदि आप recursion पर और पढ़ना चाहते हैं, तो निम्न लिंक देखें:

• प्रो. ग्रिमसन द्वारा Recursion और Dictionaries
• Recursive फंक्शन के प्रदर्शन को बेहतर करने के लिए Dynamic Programming

यदि आप Python के बारे में और सीखना चाहते हैं, तो DataCamp का मुफ़्त Intro to Python for Data Science कोर्स करें।