पायथन में पुनरावृत्ति को दूर करना

नमस्कार, हेब्र! मैं आपके लिए एरिक लिपर्ट द्वारा लेख "पायथन में एक पुनरावृत्ति को हटाने, भाग 1" का अनुवाद प्रस्तुत करता हूं।

पिछले 20 वर्षों में, मैंने पायथन की सादगी और शक्ति की प्रशंसा की है, हालांकि मैंने कभी भी इसके साथ काम नहीं किया है या विस्तार से अध्ययन नहीं किया है।

हाल ही में, मैंने उसे करीब से देखा है - और यह वास्तव में एक अच्छी भाषा है।

StackOverflow पर हाल के एक सवाल ने मुझे आश्चर्यचकित कर दिया कि एक पुनरावर्ती एल्गोरिदम को पुनरावृत्त में कैसे परिवर्तित किया जाए, और यह पता चला कि पायथन इसके लिए एक बहुत अच्छी भाषा थी।
समस्या का लेखक के सामने समस्या इस प्रकार थी:

• खिलाड़ी एक गिने हुए क्षेत्र पर एक मनमाना सेल में है;
• लक्ष्य सेल नंबर 1 पर लौटना है;
• यदि खिलाड़ी सम वर्ग पर होता है, तो वह एक सिक्का देता है और सेल नंबर 1 पर आधा जाता है;
• यदि खिलाड़ी एक विषम वर्ग पर है, तो वह 5 सिक्कों का भुगतान कर सकता है और सीधे पहले वर्ग में जा सकता है या एक सिक्के का भुगतान कर सकता है और एक वर्ग पर वर्ग नंबर 1 का एक कदम उठा सकता है।

सवाल यह है कि वर्तमान सेल से पहले पर लौटने के लिए आपको कम से कम सिक्कों का भुगतान करने की क्या आवश्यकता है।

कार्य का एक स्पष्ट पुनरावर्ती समाधान है:

def cost(s): if s <= 1: return 0 if s % 2 == 0: return 1 + cost(s // 2) return min(1 + cost(s - 1), 5) 

हालांकि, यह कार्यक्रम दुर्घटनाग्रस्त हो गया, पुनरावृत्ति की अधिकतम गहराई तक पहुंच गया, इस तथ्य के कारण सबसे अधिक संभावना है कि प्रश्न के लेखक ने बहुत बड़ी संख्या के साथ प्रयोग किया।
इसलिए, सवाल उठता है: पायथन में पुनरावृत्ति एल्गोरिदम को पुनरावृत्ति में कैसे बदलना है?

शुरू करने से पहले, मैं यह नोट करना चाहता हूं कि निश्चित रूप से इस विशिष्ट समस्या के तेजी से समाधान हैं, अपने आप में यह बहुत दिलचस्प नहीं है।

बल्कि, यह कार्य केवल एक प्रारंभिक बिंदु के रूप में कार्य करता है कि कैसे, सामान्य मामले में, पायथन कार्यक्रम में एकल पुनरावर्ती कॉल से छुटकारा पाने के लिए।

मुद्दा यह है कि आप किसी भी सरल पुनरावर्ती पद्धति को बदल सकते हैं और पुनरावृत्ति से छुटकारा पा सकते हैं, और यह केवल एक उदाहरण है जो हाथ में था।

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

मैं यहाँ क्या दिखाना चाहता हूँ कि कैसे छोटे और सुरक्षित परिवर्तनों के अनुक्रम का उपयोग करके पुनरावृत्ति से छुटकारा पाया जाता है, फ़ंक्शन को एक ऐसे रूप में ले जाता है जिसमें पुनरावृत्ति को पुनरावृत्ति के साथ बदलना आसान होता है।

शुरू करने के लिए, आइए देखें कि कार्यक्रम को इस रूप में कैसे लाया जाए।

हमारे रूपांतरण के पहले चरण में, मैं चाहता हूं कि पुनरावर्ती कॉल से पहले की गई गणनाओं को तर्क की गणना के लिए कम किया जाए, और गणनाओं के बाद, पुनरावर्ती कॉल को एक अलग तरीके से किया जाना चाहिए जो पुनरावर्ती कॉल के परिणाम को स्वीकार करता है।

 def add_one(n): return n + 1 def get_min(n): return min(n + 1, 5) def cost(s): if s <= 1: return 0 if s % 2 == 0: argument = s // 2 result = cost(argument) return add_one(result) argument = s - 1 result = cost(argument) return get_min(result) 

दूसरा चरण जो मैं करना चाहता हूं वह एक अलग फ़ंक्शन में तर्क की गणना है:

 # ... def get_argument(s): if s % 2 == 0: return s // 2 return s - 1 def cost(s): if s <= 1: return 0 argument = get_argument(s) result = cost(argument) if s % 2 == 0: return add_one(result) return get_min(result) 

तीसरे चरण में, मैं एक सहायक फ़ंक्शन जोड़ना चाहता हूं जो पुनरावृत्ति से लौटने के बाद जारी होने वाले फ़ंक्शन का चयन करेगा।

ध्यान दें कि सहायक फ़ंक्शन एक फ़ंक्शन देता है।

 #... def get_after(s): if s % 2 == 0: return add_one return get_min def cost(s): if s <= 1: return 0 argument = get_argument(s) after = get_after(s) # after  ! result = cost(argument) return after(result) 

अब हम इसे और अधिक सामान्य और संक्षिप्त रूप में लिखते हैं:

 #... def is_base_case(s): return s <= 1 def base_case_value(s): return 0 def cost(s): if is_base_case(s): return base_case_value(s) argument = get_argument(s) after = get_after(s) return after(cost(argument)) 

यह देखा जा सकता है कि किए गए प्रत्येक परिवर्तन ने कार्यक्रम के अर्थ को बनाए रखा।

अब संख्या की समता के लिए चेक दो बार किया जाता है, हालांकि परिवर्तनों से पहले एक चेक था।

यदि हम चाहें, तो हम दो सहायक कार्यों को एक में जोड़कर इस समस्या को हल कर सकते हैं जो एक टपल लौटाता है।

लेकिन चलो इस कार्य के हिस्से के रूप में इसके बारे में चिंता न करें।

हमने अपनी पुनरावर्ती पद्धति को सबसे सामान्य रूप में कम कर दिया है।

• आधार मामले में:
  
  • लौटाए जाने वाले मूल्य की गणना करें;
  • इसे वापस करो।
• एक गैर-बुनियादी मामले में:
  
  • पुनरावर्ती तर्क की गणना करें;
  • पुनरावर्ती कॉल करें;
  • वापसी मूल्य की गणना करें;
  • इसे वापस करो।

इस कदम पर आपको जो कुछ महत्वपूर्ण है उस पर ध्यान देने की आवश्यकता है, इसके after cost कॉल्स स्वयं नहीं होनी चाहिए।

मेरे द्वारा यहां दिखाया गया तरीका एकल पुनरावर्ती कॉल को निकालता है।

यदि आपके पास 2 या अधिक पुनरावर्ती हैं, तो हमें एक अलग समाधान की आवश्यकता है।

एक बार जब हम अपने पुनरावर्ती एल्गोरिथ्म को इस रूप में ले आते हैं, तो इसे पुनरावृति में बदलना पहले से ही आसान है।

चाल की कल्पना करना है कि एक पुनरावर्ती कार्यक्रम में क्या होता है।

हम एक पुनरावर्ती वंश कैसे करते हैं: हम पुनरावर्ती कॉल से पहले get_argument कहते हैं और पुनरावृत्ति से लौटने के बाद फ़ंक्शन को कॉल करते हैं।

यही है, get_argument के लिए सभी कॉल के बाद सभी कॉल करने से पहले होते हैं।
इसलिए, हम इसे 2 चक्रों में बदल सकते हैं: पहली कॉल get_argument और कार्य के बाद की सूची बनाती है, और दूसरी कॉल सभी कार्यों के बाद होती है:

 #... def cost(s): #     "after".    #       # ,    . afters = [ ] while not is_base_case(s): argument = get_argument(s) after = get_after(s) afters.append(after) s = argument #       "after" : result = base_case_value(s) while len(afters) != 0: after = afters.pop() result = after(result) return result 

कोई और अधिक पुनरावृत्ति!

यह जादू की तरह दिखता है, लेकिन हम यहां जो कुछ भी करते हैं वह वही है जो प्रोग्राम के पुनरावर्ती संस्करण और उसी क्रम में होता है।

यह उदाहरण इस विचार को दर्शाता है कि मैं अक्सर कॉल स्टैक के बारे में दोहराता हूं: इसका उद्देश्य यह बताना है कि आगे क्या होगा, और न कि पहले से क्या हुआ है!

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

स्टैक के बाद स्टोर करने के लिए एक अक्षम और बोझिल तरीके के रूप में कॉल स्टैक का उपयोग करने के बजाय, हम बस फ़ंक्शन स्टैक को स्टोर कर सकते हैं।

अगली बार हम पायथन में पुनरावृत्ति को दूर करने के लिए और अधिक जटिल तरीके से देखेंगे।