जावा

Question

में रिकर्सन से बाहर निकलना रिकर्सन 'विभाजन और जीत' शैली की तरह है, यह छोटा (वृक्ष डेटा संरचना) प्राप्त करते समय विभाजित होता है, और यदि उल्लंघन का पाया जाता है, तो मैं इसे पूरी तरह से तोड़ना चाहता हूं, जिसका अर्थ है ब्रेक सभी पुनरावर्ती पथ, और सच वापसी। क्या यह संभव है?

Answer 1

आप एक त्रुटि कोड वापस कर सकते हैं, या कुछ वैश्विक चर को संशोधित कर सकते हैं ताकि प्रत्येक पुनरावर्ती उदाहरण "खुद को मारने" के लिए जानता हो।

इस तरह का कुछ।

int foo(bar){ 
    int to_the_next; 

     if (go_recursive){ 
      to_the_next = foo(whisky_bar); 

      if (to_the_next ==DIE) return DIE; 
     } 

     if (something_unexpected_happened) return DIE; 

     process;//may include some other recursive calls, etc etc 
} 

Answer 2

आप एक चर को संग्रहीत करके ऐसा कुछ कर सकते हैं जो ट्रैक करता है कि रिकर्स को तोड़ना चाहिए या नहीं। दुर्भाग्यवश आपको इसे हर रिकर्सन की जांच करनी होगी लेकिन आप इसे कर सकते हैं।

Answer 3

यदि यह एक एकल धागा रिकर्सन कर रहा है तो आप अपवाद फेंक सकते हैं। बिट बदसूरत हालांकि - एक गोटो के रूप में अपवाद का उपयोग करने के प्रकार।

boolean myPublicWrapperMethod(...) { 
    try { 
     return myPrivateRecursiveFunction(...); 
    } catch (MySpecificException e) { 
     return true; 
    } 
} 

एक बेहतर दृष्टिकोण प्रत्यावर्तन को खत्म करने और एक ढेर संग्रह एक वर्ग का प्रतिनिधित्व क्या पुनरावर्ती राज्य हो गया होता पकड़े उपयोग करते हैं, एक पाश में पुनरावृति और सिर्फ सच वापसी जब आप चाहते हैं होगा।

Answer 4

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

public abstract class Tree { 

    protected abstract boolean headIsViolation(); 

    protected abstract boolean isLeaf(); 

    public Tree getLeft(); 

    public Tree getRight(); 

    // Recursive 
    public boolean checkViolation() { 
     if(this.isLeaf()) { 
      return this.headIsViolation(); 
     } 

     // If needed, you could pass some sort of 'calculation state' 
     // object through the recursive calls and evaluate the violation 
     // through that object if the current node is insufficient 
     if(this.headIsViolation()) { 
      // Terminate the recursion 
      return true; 
     } 

     // Fortunately, Java short-circuits || 
     // So if the left child is in violation, the right child will 
     // not even be checked 
     return this.getLeft().checkViolation() || this.getRight().checkViolation(); 
    } 
} 

Answer 5

कोई फर्क नहीं पड़ता कि आप क्या करते हैं, तो आप स्टैक करने के लिए जा रहे हैं।

1. जादू वापसी मान
2. एक अपवाद (के रूप में thaggie ने उल्लेख किया) फेंक

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

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

यह निश्चित रूप से एक प्रदर्शन समस्या की तरह दिखता था, इसलिए मैंने जादू वापसी मूल्य का उपयोग करने के लिए चीजों को बदलने के लिए कुछ समायोजन किए। और क्या आपको पता है? डीबगर में चलते समय कोड 40% तेज था। लेकिन जब मैंने गैर-डिबगिंग पर स्विच किया, तो कोड 1% से भी कम था।

मैं अभी भी इस मामले में प्रवाह नियंत्रण के अपवादों का उपयोग करने के फैसले के बारे में पागल नहीं हूं (मेरा मतलब है, अपवाद सभी उस समय फेंक दिया जाता है)। लेकिन यह निश्चित रूप से लगभग अचूक प्रदर्शन अंतर के बाद इसे फिर से लागू करने के लिए मेरे समय के लायक नहीं है।

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

Answer 6

आप जो पूछ रहे हैं वह रिकर्सन की परिभाषा है।

किसी बिंदु पर सभी पुनरावर्ती पथ तोड़ना चाहिए। अन्यथा यह एक अनंत रिकर्सन होगा और stack overflow exception होता है।

तो आपको डिज़ाइन उस तरह रिकर्सन फ़ंक्शन चाहिए। एक उदाहरण binary search in a sorted array:

BinarySearch(A[0..N-1], value, low, high) { 
     if (high < low) 
      return -1 // not found 
     mid = low + ((high - low)/2) // Note: not (low + high)/2 !! 
     if (A[mid] > value) 
      return BinarySearch(A, value, low, mid-1) 
     else if (A[mid] < value) 
      return BinarySearch(A, value, mid+1, high) 
     else 
      return mid // found 
} 

Answer 7

मैं अपवाद हैंडलिंग की अनुशंसा करता हूं। यही कारण है कि स्पष्ट करता है, कि प्रत्यावर्तन कुछ उल्लंघन (या अन्य अपवाद) की वजह से रद्द कर दिया गया:

public void outer() { 
    try { 
    int i = recurse(0); 
    } catch (OuchException ouch) { 
    // handle the exception here 
    } 
} 

private int recurse(int i) throws OuchException { 

    // for tree-like structures 
    if (thisIsALeaf) { 
     return i; 
    } 

    // the violation test 
    if (itHurts) 
     throw new OuchException("That really hurts"); 

    // we also can encapsulate other exceptions 
    try { 
     someMethod(); 
    } catch (Exception oops) { 
     throw new OuchException(oops); 
    } 

    // recurse 
    return recurse(i++); 
}

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

Answer 8

मैं वैश्विक चर का उपयोग कर सभी रिकर्सिव कॉल से बाहर निकलने में सक्षम था।

boolean skipRecursivePaths = false; 
private callAgain(){ 

if(callAgain){ 
    if(getOutCompletely){ 

    skipRecursivePaths = true; 
    } 
    if(skipRecursivePaths){ 
    return; 
    } 
} 

Answer 9

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

throw new RuntimeException("Help! Somebody debug me! I'm crashing!"); 

बेशक

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

getMemoryInfo.availMem(). 

है कि गणना की तुलना मान लीजिए कि आप प्रत्यावर्तन का उपयोग कर रहे n खोजना है !. पूरे ढेर धारण करने के लिए स्मृति में

public long fact(int n) 
{ 
    long val = 1; 
    for (int i = 1, i<=n,i++) 
     return val *= fact(i); 
    return val; 
} 

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

Answer 10

बेहतर कोई वैश्विक राज्य

if(stop[0]) return; 

Answer 11

शायद तुम प्रत्यावर्तन से बचने और एक ढेर के साथ इसे बदलना चाहते है एक बूलियन सरणी

कि जिस तरह से है। यह आपको एक पुनरावर्ती ऑपरेशन जैसा कुछ करने में सक्षम होने के दौरान, ऑपरेशन से बाहर निकलने का नियंत्रण देता है। वास्तव में आप बस अपने आप से पुनरावृत्ति का अनुकरण करते हैं।

मैं यहाँ एक अच्छा स्पष्टीकरण पाया: http://haacked.com/archive/2007/03/04/Replacing_Recursion_With_a_Stack.aspx/