पायथन में रिकर्सन की मूल बातें

Question

"एक पुनरावर्ती फ़ंक्शन लिखें," सूचीसम "जो पूर्णांक की एक सूची लेता है और सूची में सभी पूर्णांकों का योग देता है"।

उदाहरण:

>>>> listSum([1,3,4,5,6]) 
19 

मुझे पता है लेकिन पुनरावर्ती तरीके से नहीं इस एक और तरीका है कैसे करना है।

def listSum(ls): 
    i = 0 
    s = 0 
    while i < len(ls): 
     s = s + ls[i] 
     i = i + 1 
    print s 

मुझे ऐसा करने का मूल तरीका चाहिए क्योंकि विशेष अंतर्निहित कार्यों की अनुमति नहीं है।

Answer 1

जब भी आप इस तरह की एक समस्या का सामना, एक ही समारोह के साथ समारोह का परिणाम व्यक्त करने के लिए प्रयास करें।

अपने मामले में, आप सूची में शेष तत्वों के साथ एक ही फ़ंक्शन को कॉल करने के परिणाम के साथ पहला नंबर जोड़कर परिणाम प्राप्त कर सकते हैं।

उदाहरण के लिए,

listSum([1, 3, 4, 5, 6]) = 1 + listSum([3, 4, 5, 6]) 
         = 1 + (3 + listSum([4, 5, 6])) 
         = 1 + (3 + (4 + listSum([5, 6]))) 
         = 1 + (3 + (4 + (5 + listSum([6])))) 
         = 1 + (3 + (4 + (5 + (6 + listSum([]))))) 

अब, क्या listSum([]) का परिणाम होना चाहिए? यह 0 होना चाहिए। इसे आपके रिकर्सन के आधार स्थिति कहा जाता है। जब आधार की स्थिति पूरी हो जाती है, तो रिकर्सन समाप्त हो जाएगा। अब, इसे लागू करने का प्रयास करें।

यहां मुख्य बात सूची को विभाजित करना है। ऐसा करने के लिए आप slicing का उपयोग कर सकते हैं।

सरल संस्करण

>>> def listSum(ls): 
...  # Base condition 
...  if not ls: 
...   return 0 
... 
...  # First element + result of calling `listsum` with rest of the elements 
...  return ls[0] + listSum(ls[1:]) 
>>> 
>>> listSum([1, 3, 4, 5, 6]) 
19 

---

पूंछ Recursion

कॉल एक बार जब आप समझ कैसे ऊपर प्रत्यावर्तन काम करता है, तो आप इसे एक छोटा सा बेहतर बनाने की कोशिश कर सकते हैं। अब, वास्तविक परिणाम खोजने के लिए, हम पिछले कार्य के मूल्य के आधार पर भी हैं। return कथन तुरंत तब तक मूल्य वापस नहीं कर सकता जब तक रिकर्सिव कॉल नतीजे न आए। हम समारोह पैरामीटर के लिए वर्तमान गुजर, इस

>>> def listSum(ls, result): 
...  if not ls: 
...   return result 
...  return listSum(ls[1:], result + ls[0]) 
... 
>>> listSum([1, 3, 4, 5, 6], 0) 
19 

यहाँ की तरह, इस से बचने कर सकते हैं, हम क्या योग की प्रारंभिक मान पैरामीटर हैं, जो शून्य listSum([1, 3, 4, 5, 6], 0) में है में होना गुजरती हैं। फिर, जब आधार की स्थिति पूरी हो जाती है, तो हम वास्तव में result पैरामीटर में योग जमा कर रहे हैं, इसलिए हम इसे वापस कर देते हैं। अब, अंतिम return कथन में listSum(ls[1:], result + ls[0]) है, जहां हम वर्तमान result पर पहला तत्व जोड़ते हैं और इसे फिर से रिकर्सिव कॉल पर पास करते हैं।

यह Tail Call को समझने का एक अच्छा समय हो सकता है।यह पायथन के लिए प्रासंगिक नहीं होगा, क्योंकि यह टेल कॉल ऑप्टिमाइज़ेशन नहीं करता है।

---

सूचकांक संस्करण के आसपास पासिंग

अब, आप सोच सकते हैं कि हम इतने सारे मध्यवर्ती सूची बना रहे हैं। क्या मैं इससे बच सकता हूं?

बेशक, आप कर सकते हैं। आपको बस संसाधित होने के लिए आइटम की अनुक्रमणिका की आवश्यकता है। लेकिन अब, आधार की स्थिति अलग होगी। चूंकि हम इंडेक्स पास करने जा रहे हैं, हम कैसे तय करेंगे कि पूरी सूची कैसे संसाधित की गई है? खैर, अगर सूचकांक सूची की लंबाई के बराबर है, तो हमने इसमें सभी तत्वों को संसाधित किया है।

>>> def listSum(ls, index, result): 
...  # Base condition 
...  if index == len(ls): 
...   return result 
... 
...  # Call with next index and add the current element to result 
...  return listSum(ls, index + 1, result + ls[index]) 
... 
>>> listSum([1, 3, 4, 5, 6], 0, 0) 
19 

---

इनर समारोह संस्करण

आप अब समारोह परिभाषा को देखें, तो आप इसे करने के तीन पैरामीटर गुजर रहे हैं। आइए कहें कि आप इस फ़ंक्शन को एपीआई के रूप में रिलीज़ करने जा रहे हैं। क्या उपयोगकर्ताओं के लिए तीन मानों को पारित करना सुविधाजनक होगा, जब उन्हें वास्तव में एक सूची का योग मिल जाएगा?

नहीं। हम इसके बारे में क्या कर सकते हैं? हम एक और समारोह है, जो वास्तविक listSum कार्य करने के लिए स्थानीय है बना सकते हैं और हम इस

>>> def listSum(ls): 
... 
...  def recursion(index, result): 
...   if index == len(ls): 
...    return result 
...   return recursion(index + 1, result + ls[index]) 
... 
...  return recursion(0, 0) 
... 
>>> listSum([1, 3, 4, 5, 6]) 
19 

अब

, जब listSum कहा जाता है जैसे कि यह करने के लिए सभी कार्यान्वयन से संबंधित मानकों को पारित कर सकते हैं, यह सिर्फ की वापसी मान देता है recursion आंतरिक फ़ंक्शन, जो index और result पैरामीटर स्वीकार करता है। अब हम केवल उन मानों को पार कर रहे हैं, न कि listSum के उपयोगकर्ता। उन्हें सिर्फ संसाधित होने वाली सूची को पास करना होगा।

इस मामले में, यदि आप पैरामीटर देखते हैं, तो हम ls से recursion पास नहीं कर रहे हैं, लेकिन हम इसके अंदर इसका उपयोग कर रहे हैं। बंदरगाह संपत्ति के कारण lsrecursion के अंदर पहुंच योग्य है।

---

डिफ़ॉल्ट पैरामीटर संस्करण

अब, आप इसे सरल रखने के लिए, एक आंतरिक समारोह बनाने के बिना चाहते हैं, तो आप डिफ़ॉल्ट पैरामीटर का उपयोग कर सकते, इस

>>> def listSum(ls, index=0, result=0): 
...  # Base condition 
...  if index == len(ls): 
...   return result 
... 
...  # Call with next index and add the current element to result 
...  return listSum(ls, index + 1, result + ls[index]) 
... 
>>> listSum([1, 3, 4, 5, 6]) 
19 

की तरह अब, अगर कॉलर स्पष्ट रूप से किसी भी मान को पास नहीं करता है, तो 0 दोनों index और result दोनों को असाइन किया जाएगा।

---

रिकर्सिव पावर समस्या

अब, की सुविधा देता है एक अलग समस्या के लिए विचारों को लागू करें। उदाहरण के लिए, power(base, exponent) फ़ंक्शन को लागू करने का प्रयास करें। यह base के मूल्य को exponent पर बढ़ाएगा।

power(2, 5) = 32 
power(5, 2) = 25 
power(3, 4) = 81 

अब, हम इसे फिर से कैसे कर सकते हैं? आइए समझने की कोशिश करें कि ये परिणाम कैसे प्राप्त किए जाते हैं।

power(2, 5) = 2 * 2 * 2 * 2 * 2 = 32 
power(5, 2) = 5 * 5    = 25 
power(3, 4) = 3 * 3 * 3 * 3  = 81 

हमम, इसलिए हमें विचार मिलता है। base अपने आप से गुणा हुआ, exponent बार परिणाम देता है। ठीक है, हम इसके साथ कैसे संपर्क करते हैं। आइए एक ही फ़ंक्शन के साथ समाधान को परिभाषित करने का प्रयास करें।

power(2, 5) = 2 * power(2, 4) 
      = 2 * (2 * power(2, 3)) 
      = 2 * (2 * (2 * power(2, 2))) 
      = 2 * (2 * (2 * (2 * power(2, 1)))) 

यदि कुछ भी शक्ति में उठाया गया तो परिणाम क्या होना चाहिए? परिणाम एक ही नंबर होगा, है ना? हमें हमारे रिकर्सन के लिए हमारी आधार स्थिति मिली :-)

  = 2 * (2 * (2 * (2 * 2))) 
      = 2 * (2 * (2 * 4)) 
      = 2 * (2 * 8) 
      = 2 * 16 
      = 32 

ठीक है, इसे लागू करने दें।

>>> def power(base, exponent): 
...  # Base condition, if `exponent` is lesser than or equal to 1, return `base` 
...  if exponent <= 1: 
...   return base 
... 
...  return base * power(base, exponent - 1) 
... 
>>> power(2, 5) 
32 
>>> power(5, 2) 
25 
>>> power(3, 4) 
81 

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

>>> def power(base, exponent, result=1): 
...  # Since we start with `1`, base condition would be exponent reaching 0 
...  if exponent <= 0: 
...   return result 
... 
...  return power(base, exponent - 1, result * base) 
... 
>>> power(2, 5) 
32 
>>> power(5, 2) 
25 
>>> power(3, 4) 
81 

अब, हम हर पुनरावर्ती कॉल और base के साथ कई result में exponent मूल्य को कम करने और यह पुनरावर्ती power कॉल करने के लिए गुजरती हैं। हम मूल्य 1 से शुरू करते हैं, क्योंकि हम विपरीत में समस्या का सामना कर रहे हैं। प्रत्यावर्तन की तरह इस

power(2, 5, 1) = power(2, 4, 1 * 2) 
       = power(2, 4, 2) 
       = power(2, 3, 2 * 2) 
       = power(2, 3, 4) 
       = power(2, 2, 4 * 2) 
       = power(2, 2, 8) 
       = power(2, 1, 8 * 2) 
       = power(2, 1, 16) 
       = power(2, 0, 16 * 2) 
       = power(2, 0, 32) 

के बाद से exponent शून्य, आधार की स्थिति उत्पन्न होने हो जाता है क्या होगा और result लौटा दी जाएगी, तो हम मिल 32 :-)

Answer 2

प्रारंभिक निकास पुनरावर्ती कार्यों के लिए विशिष्ट है। seq खाली होने पर गलत है (इसलिए जब कोई संख्या योग में नहीं छोड़ी जाती है)।

स्लाइस सिंटैक्स वर्तमान चरण में पूर्णांक के बिना पूर्ण रूप से बुलाए जाने वाले फ़ंक्शन को अनुक्रमित करने की अनुमति देता है।

def listSum(seq): 
    if not seq: 
     return 0 
    return seq[0] + listSum(seq[1:]) 

print listSum([1,3,4,5,6]) # prints 19 

Answer 3

def listSum(L): 
    """Returns a sum of integers for a list containing 
    integers. 
    input: list of integers 
    output: listSum returns a sum of all the integers 
    in L. 
    """ 
    if L == []: 
     return [] 
    if len(L) == 1: 
     return L[0] 
    else: 
     return L[0] + listSum(L[1:]) 
print listSum([1, 3, 4, 5, 6]) 
print listSum([]) 
print listSum([8])