इस लूप को कैसे तोड़ें

Question

मैं प्रोजेक्ट यूलर नंबर 5 पर काम कर रहा हूं। मैंने गुगल नहीं किया है, क्योंकि इससे आमतौर पर उत्तर के साथ SO हो जाएगा। तो, यह मुझे मिला है:

private int Euler5(int dividend, int divisor) 
    { 
     if (divisor < 21) 
     { 
      // if it equals zero, move to the next divisor 
      if (dividend % divisor == 0) 
      { 
       divisor++; 
       return Euler5(dividend, divisor); 
      } 
      else 
      { 
       dividend++; 
       return Euler5(dividend, 1); // move to the dividend 
      } 
     } 
     // oh hey, the divisor is above 20, so what's the dividend 
     return dividend; 
    } 

मेरे दिमाग में, यह समझ में आता है। फिर भी वीएस2012 मुझे एक स्टैक ओवर फ्लोएक्सप्शन बता रहा है कि मैं यह सुनिश्चित करता हूं कि मैं अनंत लूप में नहीं हूं या रिकर्सन का उपयोग कर रहा हूं। मेरा सवाल है, यह एक अनंत लूप क्यों है? मुझे एहसास है कि मैं पूरी तरह मूर्खतापूर्ण कुछ खो रहा हूँ।

संपादित

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

Answer 1

बेशक इस प्रकार का तर्क ढेर को उड़ाने जा रहा है। इस बारे में सोचो, अगर आप सबसे छोटी संख्या 1--10 द्वारा समान रूप से विभाज्य पाने की समस्या को हल करने के लिए इस तर्क लागू करने के लिए कॉल, आप कम से कम 2520 होगी ढेर में गहरी, problem statement प्रति थे:

2520 सबसे छोटी संख्या है जिसे प्रत्येक संख्या द्वारा 1 से 10 तक किसी भी शेष के बिना विभाजित किया जा सकता है।

1--20 के लिए, उत्तर स्पष्ट रूप से बहुत बड़ा है और यह आश्चर्य की बात नहीं है कि आप ढेर उड़ रहे हैं। आपको एक गैर-पुनरावर्ती समाधान मिलना चाहिए।

मेरा सवाल यह है कि यह एक अनंत लूप क्यों है?

यह नहीं है। ढेर आकार में सीमित है। आप बहुत अधिक रिकर्सिव कॉल कर रहे हैं और अंत में अधिकतम स्टैक आकार का उल्लंघन कर रहे हैं।

मुझे एहसास है कि मुझे कुछ पूरी तरह से मूर्खतापूर्ण याद आ रही है।

आप right place पर आए थे।

Answer 2

जेसन के उत्तर के लिए +1, जो स्पष्ट रूप से समस्या को समझाता है।

अब कुछ समाधान के लिए! मुझे एल्गोरिदम से रिकर्सन को हटाने के कम से कम तीन तरीकों से पता है:

1. इसके बजाय पूरी तरह से पुनरावृत्त एल्गोरिदम खोजें (जो कुछ समस्याओं के लिए मुश्किल हो सकता है);
2. लूप के साथ एक समान में रिकर्सिव एल्गोरिदम को ट्रांसफॉर्म करें और कॉल स्टैक के बराबर स्टोर करने के लिए स्टैक < टी> (या किसी प्रकार की सूची) का उपयोग करें। इसकी मूल आवश्यकता के समान अंतरिक्ष आवश्यकता है, लेकिन ढेर ढेर से कहीं अधिक बड़ा हो सकता है!
3. रिकर्सिव एल्गोरिदम का एक विशेष परिवार पूंछ-रिकर्सिव है। जो आसानी से यांत्रिक रूप से ढेर को कभी भी बहने के लिए परिवर्तित नहीं कर सकते हैं। तुम भाग्यशाली हो, यह तुम्हारा मामला है!

एक एल्गोरिद्म जिसका मतलब है कि वे पिछले लौटने से पहले किया बात कर रहे हैं पूंछ पुनरावर्ती है, अगर अपने सभी पुनरावर्ती कॉल पूंछ कॉल हैं। यदि यह आपके लिए अस्पष्ट है, तो Google के साथ बेहतर उदाहरण देखें।

ऐसे एल्गोरिदम आसानी से पैरामीटर को समायोजित करके और वास्तविक कॉल के बजाय गोटो का उपयोग करके परिवर्तित किया जा सकता है। अपना उदाहरण दोबारा देखें:

private int Euler5(int dividend, int divisor) 
{ 
    tail_call: 
    if (divisor < 21) 
    { 
     // if it equals zero, move to the next divisor 
     if (dividend % divisor == 0) 
     { 
      divisor++; 
      goto tail_call; // return Eular5(dividend, divisor); 
     } 
     else 
     { 
      dividend++; 
      // return Eular5(dividend, 1); // move to the dividend 
      divisor = 1; 
      goto tail_call; 
     } 
    } 
    // oh hey, the divisor is above 20, so what's the dividend 
    return dividend; 
} 

ओह हे! यह बिल्कुल वही कार्य है, लेकिन एक निश्चित स्टैक आकार के साथ (कोई कॉल नहीं है, केवल कूदता है)। अब कुछ कहेंगे: "उह ... गेटोस! वे बुरे हैं! मर जाओ, मर जाओ!"। मैं कहूंगा कि यह कुछ वैध उपयोगों में से एक है। आखिरकार यदि आपका कंपाइलर काफी स्मार्ट था, तो यह पूंछ-कॉल अनुकूलन स्वयं करेगा (एफ # वास्तव में करता है, सी # नहीं करता है, जेआईटी x64 पर ऐसा कर सकता है, x86 पर नहीं)।

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

private int Euler5(int dividend, int divisor) 
{ 
    while (divisor < 21) 
    { 
     // if it equals zero, move to the next divisor 
     if (dividend % divisor == 0) 
     { 
      divisor++; 
     } 
     else 
     { 
      dividend++; 
      divisor = 1; 
     } 
    } 
    // oh hey, the divisor is above 20, so what's the dividend 
    return dividend; 
} 

अच्छा!