java.lang.StackOverflow रिकर्सन

Question

मेरी समस्या यह है कि मुझे आमतौर पर java.lang.StackOverflow त्रुटि मिलती है जब मैं रिकर्सन का उपयोग करता हूं। मेरा सवाल है - क्यों रिकर्सन स्टॉप ओवरफ्लो को लूप की तुलना में बहुत अधिक कारण बनाता है, और क्या स्टैक ओवरफ़्लो से बचने के लिए रिकर्सन का उपयोग करने का कोई अच्छा तरीका है?

यह problem 107 को हल करने का प्रयास है, यह उनके उदाहरण के लिए अच्छा काम करता है लेकिन समस्या के लिए स्टैक स्पेस से बाहर चला जाता है।

//-1 16 12 21 -1 -1 -1 16 -1 -1 17 20 -1 -1 12 -1 -1 28 -1 31 -1 21 17 28 -1 18 19 23 -1 20 -1 18 -1 -1 11 -1 -1 31 19 -1 -1 27 -1 -1 -1 23 11 27 -1 
public class tries 
{ 
    public static int n=7,min=Integer.MAX_VALUE; 
    public static boolean[][] wasHere=new boolean[n][60000]; 
    public static void main(String[] args) 
    { 
     int[] lines=new int[n]; Arrays.fill(lines, -1000); lines[0]=0; 
     int[][] networkMatrix=new int[n][n]; 
     Scanner reader=new Scanner(System.in); 
     int sum=0; 
     for(int k=0; k<n; k++) 
     { 
      for(int r=0; r<n; r++) 
      { 
       networkMatrix[k][r]=reader.nextInt(); 
       if(networkMatrix[k][r]!=-1) sum+=networkMatrix[k][r]; 
       Arrays.fill(wasHere[k], false); 
      } 
     } 
     recursive(lines,networkMatrix,0,0); 
     System.out.println((sum/2)-min); 
    } 
    public static void recursive(int[] lines, int[][] networkMatrix, int row,int lastRow) 
    {  
     wasHere[row][value((int)use.sumArr(lines))]=true; 
     if(min<sum(lines)) return; 
     if(isAllNotMinus1000(lines)) min=sum(lines); 
     int[][] copyOfMatrix=new int[n][n]; 
     int[] copyOfLines; 
     for(int i=0; i<n; i++) 
     { 
      copyOfLines=Arrays.copyOf(lines, lines.length); 
      for(int k=0; k<n; k++) copyOfMatrix[k]=Arrays.copyOf(networkMatrix[k], networkMatrix[k].length); 
      if(i!=0&&copyOfMatrix[i][row]!=0) copyOfLines[i]=copyOfMatrix[i][row]; 
      copyOfMatrix[i][row]=0; copyOfMatrix[row][i]=0; 
      if(networkMatrix[row][i]==-1) continue; 
      if(wasHere[i][value((int)use.sumArr(copyOfLines))]) continue; 
      if(min<sum(copyOfLines)) continue; 
      recursive(copyOfLines,copyOfMatrix,i,row); 
     } 
    } 
    public static boolean isAllNotMinus1000(int[] lines) 
    { 
     for(int i=0; i<lines.length; i++) {if(lines[i]==-1000) return false;} 
     return true; 
    } 
    public static int value(int n) 
    { 
     if(n<0) return (60000+n); 
     return n; 
    } 
    public static int sum(int[] arr) 
    { 
     int sum=0; 
     for(int i=0; i<arr.length; i++) 
     { 
      if(arr[i]==-1000) continue; 
      sum+=arr[i]; 
     } 
     return sum; 
    } 
} 

Answer 1

क्यों इतना अधिक की तुलना में छोरों

करना प्रत्येक पुनरावर्ती कॉल स्टैक पर कुछ स्थान का उपयोग करता है प्रत्यावर्तन कारण stackoverflow करता है। यदि आपका रिकर्सन बहुत गहरा है, तो इसका परिणाम StackOverflow होगा, जो ढेर में अधिकतम अनुमत गहराई के आधार पर होगा।

रिकर्सन का उपयोग करते समय, आपको बहुत सावधान रहना चाहिए और यह सुनिश्चित करना चाहिए कि आप base case प्रदान करें। रिकर्सन में एक बेस केस वह शर्त है जिस पर रिकर्सन समाप्त होता है, और ढेर खोलने लगते हैं। यह StackOverflow त्रुटि के कारण रिकर्सन का मुख्य कारण है। अगर इसे कोई आधार मामला नहीं मिलता है, तो यह एक अनंत रिकर्सन में जाएगा, जो निश्चित रूप से त्रुटि में होगा, क्योंकि Stack केवल सीमित है।

Answer 2

सही ढंग से उपयोग किए जाने पर, रिकर्सन StackOverflowError का उत्पादन नहीं करेगा। यदि ऐसा होता है, तो आपका बेस केस ट्रिगर नहीं किया जा रहा है, और विधि स्वयं को infinitum विज्ञापन कॉल करती रहती है। प्रत्येक विधि कॉल जो पूरा नहीं होता है, ढेर पर रहता है, और अंत में यह बहती है।

लेकिन लूप में स्वयं द्वारा विधि कॉल शामिल नहीं होते हैं, इसलिए स्टैक पर कुछ भी नहीं बनता है और StackOverflowError का परिणाम नहीं होता है।

Answer 3

हर बार जब आप कोई विधि कॉल करते हैं, तो आप स्टैक से "फ्रेम" का उपभोग करते हैं, यह फ्रेम विधि रिटर्न तक जारी नहीं होता है, यह लूप के साथ समान नहीं होता है।

Answer 4

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

हालांकि, ऐसी स्थितियां हैं जहां एक विधि एक स्टैक ओवरफ्लो भी उत्पन्न कर सकती है यदि इसे सही ढंग से कार्यान्वित किया गया हो। उदाहरण के लिए:

• तेजी से बढ़ रहा है (कहें, घातीय) रिकर्सन। उदाहरण के लिए: फाइबोनैचि समारोह
• एक बहुत बड़ी इनपुट डेटा की भोली पुनरावर्ती कार्यान्वयन, है कि अंततः ढेर अंतरिक्ष कारण होगा
खत्म होने की

निष्कर्ष: किसी भी यह सब विशेष मामले पर निर्भर करता है, यह असंभव है एक ढेर अतिप्रवाह का कारण बनता है इसके बारे में सामान्यीकृत करें।

Answer 5

रिकर्सन स्टैक ओवरफ़्लो का कारण बनता है क्योंकि सभी पिछली कॉल स्मृति में हैं। इसलिए आपकी विधि स्वयं को नए पैरामीटर के साथ कॉल करती है, फिर वह स्वयं को कॉल करती है। इसलिए ये सभी कॉल ढेर हो जाते हैं और सामान्य रूप से स्मृति से बाहर हो सकते हैं। लूप सामान्य रूप से परिणामों को कुछ चरों में संग्रहीत करते हैं और विधियों को कॉल करने के तरीकों को कॉल करते हैं, प्रत्येक कॉल के बाद, कॉलर विधियां समाप्त होती हैं और परिणाम लौटाती हैं।

Answer 6

प्रत्येक रिकर्सिव कॉल स्टैक पर कुछ जगह का उपयोग करता है (उस कॉल के लिए विशिष्ट कुछ भी घर, जैसे कि तर्क, स्थानीय चर, इत्यादि)। इस प्रकार, यदि आप बहुत अधिक रिकर्सिव कॉल करते हैं (या तो आधार केस प्रदान करने या बस बहुत सी रिकर्सिव कॉल करने की कोशिश करके), तो इसके लिए जगह प्रदान करने के लिए पर्याप्त जगह नहीं है, और आप StackOverflow के साथ समाप्त होते हैं ।

कारण है कि छोरों इस समस्या नहीं है कि एक पाश के प्रत्येक यात्रा की अपनी अनूठी अंतरिक्ष का उपयोग नहीं करता है (अर्थात, अगर मैं पाश n बार, मैं n+1 सेंट पाश करने के लिए अतिरिक्त जगह की जरूरत नहीं है)।

Answer 7

रिकर्सन स्टैक ओवरफ़्लो का कारण बनने का कारण यह है कि जब हम रिकर्सन रोकना बंद कर देते हैं, तो हम स्थापित करने में विफल रहते हैं, और इस प्रकार फ़ंक्शन/विधि स्वयं को "हमेशा के लिए" कॉल करेगी (जब तक यह त्रुटि का कारण न हो)।

bool flag = true; 
while (flag == true){ 
    count++; 
} 

के बाद से flag हमेशा सच हो जाएगा, जबकि पाश जब तक यह आप ढेर अतिप्रवाह त्रुटि देता है कभी बंद नहीं करेंगे: यदि आप निम्नलिखित के रूप में कुछ है आप भले ही आप छोरों का उपयोग कर रहे एक ही समस्या है,।

Answer 8

आप जो भी रिकर्सन नीचे जाते हैं, आप रनटाइम स्टैक में राज्य की जानकारी जोड़ते हैं। यह जानकारी एक सक्रियण रिकॉर्ड में संग्रहीत होती है और इसमें ऐसी जानकारी होती है जैसे कि वेरिएबल्स दायरे में हैं और उनके मूल्य क्या हैं। प्रत्येक बार जब आप लूप करते हैं तो लूप के पास अतिरिक्त सक्रियण रिकॉर्ड नहीं होते हैं, इसलिए वे कम स्मृति लेते हैं।

कुछ स्थितियों में आपका रिकॉर्शन इतना गहरा हो सकता है कि यह ढेर को बहने का कारण बनता है लेकिन ऐसा होने से रोकने में मदद करने के तरीके हैं। जब प्रत्यावर्तन के साथ काम कर, मैं आमतौर पर इस प्रारूप का पालन करें:

public obj MyMethod(string params) { 
    if (base-case) { 
     do something... 
    } else { 
     do something else... 
     obj result = MyMethod(parameters here); 
     do something else if needed.. 
    } 
} 

Recursion सुपर प्रभावी हो सकता है और कहा कि नहीं कर सकते हैं लूप काम करते हैं। कभी-कभी आप उस बिंदु पर पहुंच जाते हैं जहां रिकर्सन स्पष्ट निर्णय है। जो आपको एक अच्छा प्रोग्रामर बनाता है वह इसका उपयोग करने में सक्षम होता है जब यह पूरी तरह से obvoius नहीं है।