"आवश्यक" प्रभावशाली भाषाओं में रिकर्सन का उपयोग

Question

मैंने हाल ही में कुछ अलग-अलग स्थानों की टिप्पणियों में देखा है, "मैंने स्कूल में रिकर्सन के बारे में सीखा है, लेकिन तब से इसका उपयोग कभी नहीं किया है या इसके बाद इसकी आवश्यकता महसूस नहीं हुई है । " (रिकर्सन प्रोग्रामर के एक निश्चित समूह के बीच "पुस्तक सीखने" का एक लोकप्रिय उदाहरण प्रतीत होता है।)

अच्छा, यह सच है कि जावा और रूबी [1] जैसी अनिवार्य भाषाओं में, हम आम तौर पर पुनरावृत्ति का उपयोग करते हैं और पुनरावर्तन से बचते हैं, कुछ हिस्सों में स्टैक ओवरफ्लो के जोखिम की वजह से, और कुछ हद तक क्योंकि यह शैली उन भाषाओं में सबसे अधिक प्रोग्रामर के लिए उपयोग की जाती है।

अब मुझे पता है कि, सख्ती से बोलते हुए, ऐसी भाषाओं में रिकर्सन के "आवश्यक" उपयोग नहीं हैं: कोई भी किसी भी तरह से पुनरावृत्ति के साथ रिकर्सन को प्रतिस्थापित कर सकता है, भले ही जटिल चीजें कैसे हों। यहां "जरूरी" से, मैं निम्नलिखित के बारे में बात कर रहा हूं:

क्या आप ऐसी भाषाओं में कोड के किसी भी विशेष उदाहरण के बारे में सोच सकते हैं जहां पुनरावृत्ति पुनरावृत्ति से बेहतर था (स्पष्टता, दक्षता या अन्यथा के कारणों के लिए) आपने वैसे भी रिकर्सन का इस्तेमाल किया, और पुनरावृत्ति में परिवर्तित करना एक बड़ा नुकसान हुआ होगा?

उत्तर में कई बार पेड़ चलने वाले पेड़ों का उल्लेख किया गया है: यह आपके विशेष उपयोग के बारे में बिल्कुल सही था जिसने लाइब्रेरी-परिभाषित इटरेटर का उपयोग करने से बेहतर रिकर्सन किया था, क्या यह उपलब्ध था?

[1]: हाँ, मुझे पता है कि ये वस्तु-उन्मुख भाषाएं भी हैं। हालांकि, यह इस प्रश्न के लिए सीधे प्रासंगिक नहीं है।

Answer 1

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

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

Answer 2

मेरे पास रिपोर्ट की एक सूची है। मैं अपनी कक्षा में इंडेक्सर्स का उपयोग कर रहा हूं जिसमें यह सूची है। इंडेक्सर्स का उपयोग करके उनके स्क्रीन नामों से रिपोर्ट पुनर्प्राप्त की जाती है। इंडेक्सर में, यदि उस स्क्रीन नाम की रिपोर्ट मौजूद नहीं है तो यह रिपोर्ट लोड करती है और रिकर्सली कॉल करती है।

public class ReportDictionary 
    { 
     private static List<Report> _reportList = null; 

     public ReportColumnList this[string screenName] 
     { 
      get 
      { 
       Report rc = _reportList.Find(delegate(Report obj) { return obj.ReportName == screenName; }); 

       if (rc == null) 
       { 
        this.Load(screenName); 
        return this[screenName]; // Recursive call 
       } 
       else 
        return rc.ReportColumnList.Copy(); 
      } 
      private set 
      { 
       this.Add(screenName, value); 
      } 
     } 

    } 

यह कोड की कुछ अतिरिक्त पंक्तियों का उपयोग करके रिकर्सन के बिना किया जा सकता है।

Answer 3

यह आपके द्वारा प्रसंस्करण किए जा रहे डेटा के बारे में है।

मैंने एक स्ट्रिंग को डेटा संरचना में बदलने के लिए एक सरल पार्सर लिखा है, यह शायद जावा में 5 साल के काम में एकमात्र उदाहरण है, लेकिन मुझे लगता है कि यह करने का सही तरीका था।

स्ट्रिंग इस तरह देखा:

"{ index = 1, ID = ['A', 'B', 'C'], data = {" + 
    "count = 112, flags = FLAG_1 | FLAG_2 }}" 

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

Answer 4

जब आप उदाहरण

• एक रिकर्सिव-डिसेंट पार्सर
• एक डोम पेड़ चलने का उपयोग कर एक व्याकरण पार्स करने के लिए वृक्ष संरचना के किसी भी प्रकार चल रहे हैं,

(जैसे HTML या XML पार्स)

भी, प्रत्येक toString() विधि जो ऑब्जेक्ट सदस्यों के toString() को कॉल करती है उसे भी रिकर्सिव माना जा सकता है। सभी ऑब्जेक्ट serializing एल्गोरिदम रिकर्सिव हैं।

Answer 5

सबसे प्रसिद्ध उदाहरण शायद सीएआर द्वारा विकसित क्विकॉर्ट एल्गोरिदम है। होरे।

एक और उदाहरण फ़ाइल खोजने के लिए एक निर्देशिका वृक्ष को पार कर रहा है।

Answer 6

रिकर्सन के "आवश्यक" उपयोग नहीं हैं। सभी रिकर्सिव एल्गोरिदम को पुनरावृत्त में परिवर्तित किया जा सकता है। मुझे लगता है कि एक ढेर जरूरी है, लेकिन मुझे अपने सिर के ऊपर से सटीक निर्माण याद नहीं है।

व्यावहारिक रूप से, बोल अगर आप प्रत्यावर्तन उपयोग नहीं कर रहे निम्नलिखित (यहां तक ​​कि जरूरी भाषाओं में) आप एक छोटे से पागल हो रहे हैं:

1. ट्री ट्रेवर्सल
2. रेखांकन
3. Lexing/पार्सिंग
4. छंटनी

Answer 7

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

एक अच्छा उदाहरण एक ज्ञात ऑपरेटिंग सिस्टम पर निर्देशिका संरचना को पार कर रहा है। आप आमतौर पर जानते हैं कि यह कितना गहरा हो सकता है (अधिकतम पथ लंबाई सीमित है) और इसलिए एक स्टैक ओवरफ्लो नहीं होगा। बाहरी ढेर के साथ पुनरावृत्ति के माध्यम से ऐसा करना इतना सुविधाजनक नहीं है।

Answer 8

मेरी राय में, डेटा संरचना भी पुनरावर्ती होने पर रिकर्सिव एल्गोरिदम एक प्राकृतिक फिट है।

def traverse(node, function): 
    function(this) 
    for each childnode in children: 
     traverse(childnode, function) 

मैं नहीं देख सकता कि मैं इसे क्यों लिखना चाहता हूं।

Answer 9

यह "कुछ भी पेड़" कहा गया था। मैं बहुत सावधान रह सकता हूं, और मुझे पता है कि आजकल ढेर बड़े हैं, लेकिन मैं अभी भी एक ठेठ पेड़ पर रिकर्सन का उपयोग नहीं करूंगा। हालांकि, मैं इसे balanced tree पर करता हूं।