एकाधिक रिटर्न

Question

के साथ रिकर्सन भ्रम मैं अभी भी अपने दिमाग को रिकर्सन के चारों ओर लपेट रहा हूं, और मुझे लगता है कि मुझे मूलभूत जैसे मूलभूत मिलते हैं। लेकिन मैं आगे स्पष्टीकरण चाहते हैं जब वापसी कथन निम्नलिखित स्निपेट पर की तरह एक छोटे से अधिक जटिल है:

/** 
* @param n >= 0 
* @return the nth Fibonacci number 
*/ 
public static int fibonacci(int n) { 
    if (n == 0 || n == 1) { 
     return 1; // base cases 
    } else { 
     return fibonacci(n-1) + fibonacci(n-2); // recursive step 
    } 
} 

वापसी बयान में फाइबोनैचि (n-1) पूरी तरह से के माध्यम से पुनरावृत्ति होना होता है, नीचे जाने से पहले फाइबोनैकी (एन -2) चरण (क्या यह समझ में आता है)? यदि ऐसा है, तो यह कल्पना करना बहुत मुश्किल लगता है।

Answer 1

हां, एक आमंत्रण दूसरे तरीके से निष्पादित होने से पहले सभी तरह से नीचे और वापस लौट जाएगा। fibonacci(n-1)fibonacci(n-2) से पहले चला जाता है:

जावा में मंगलाचरण के आदेश अच्छी तरह से परिभाषित है।

संपादित करें: के बाद से सवाल मूल रूप से शामिल [C++] टैग, यहाँ है सी ++ कहानी का हिस्सा: दो आमंत्रण में से एक अभी भी पहले एक दूसरे को चलाने के लिए शुरू होता है पूरा करने के लिए है, लेकिन जो एक, fibonacci(n-1) या fibonacci(n-2), निर्दिष्ट नहीं है।

चूंकि फ़ंक्शन का कोई दुष्प्रभाव नहीं है, इससे कोई फर्क नहीं पड़ता कि दो आमंत्रणों में से कौन सा पहले भाग लेता है। रिकर्सन को समझने के लिए महत्वपूर्ण एकमात्र चीज यह है कि वर्तमान स्तर पर रिटर्न पर आमंत्रण से पहले दोनों आमंत्रणों को पूरा करना होगा, और उनके परिणामों को एक साथ जोड़ा जाना चाहिए।

Answer 2

यह इस तरह से काम करता है:

फाइबोनैचि कार्यक्रम:

public int fibonacci(int n) { 
    if(n == 0) 
     return 0; 
    else if(n == 1) 
     return 1; 
    else 
     return fibonacci(n - 1) + fibonacci(n - 2); 
} 

स्पष्टीकरण: फाइबोनैचि अनुक्रम में प्रत्येक आइटम पिछले दो का योग है। तो, रिकर्सिव एल्गोरिदम के अनुसार।

तो,

fibonacci(5) = fibonacci(4) + fibonacci(3) 

fibonacci(3) = fibonacci(2) + fibonacci(1) 

fibonacci(4) = fibonacci(3) + fibonacci(2) 

fibonacci(2) = fibonacci(1) + fibonacci(0) 

अब आप पहले से ही fibonacci(1)==1 and fibonacci(0) == 0 पता है। तो, आप बाद में अन्य मूल्यों की गणना कर सकते हैं।

अब,

fibonacci(2) = 1+0 = 1 
fibonacci(3) = 1+1 = 2 
fibonacci(4) = 2+1 = 3 
fibonacci(5) = 3+2 = 5 

Answer 3

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

finobacci(0); // ==> 1 (since n is zero, the base case is to return 1) 
fibonacci(1); // ==> 1 (since n is one, the base case is to return 1) 

अब कोशिश 2 जो आधार मामला नहीं है देता है:

fibonacci(2);    // == (since it's not the base case) 
fibonacci(1) + fibonacci(0); // == (both calls to fibonacci we already haver done above) 
1 + 1      // ==> 2 

वास्तविकता में

तो क्या होता है कि कॉल प्रतीक्षा करता है fibonacci2 जबकि करने के लिए दो पुनरावर्ती कॉल की प्रत्येक खत्म, बस है एक फ़ंक्शन की तरह System.out.println तब तक प्रतीक्षा करेगा जब तक कि वह अगली पंक्ति तक जारी रखने से पहले तर्क मुद्रित न करे। रिकर्सन विशेष नहीं है।

ट्रिविया: यह फिबोनैकी से मूल श्रृंखला है। आधुनिक गणितज्ञ n के साथ श्रृंखला शुरू करते हैं क्योंकि आधार केस परिणाम 1, 1, 2, 3, ... की बजाय श्रृंखला 0, 1, 1, 2, ... बनाता है।

Answer 4

एकाधिक रिकर्सन में प्रोग्राम बेस केस तक पहुंचने तक अपने पहले कॉल के साथ कॉल करता है, इस मामले में फाइबोनैकी (एन -1); उसके बाद रिकर्सन फाइबोनैकी (एन -2) के दूसरे भाग में मूल्य को कॉल करना जारी रखने के लिए रिकर्सन बंद हो जाता है और अपना मूल्य वापस कर देता है।

यदि आप प्रोग्राम में एकाधिक रिकर्सन को कल्पना नहीं करते हैं, तो यह fibonacci recursion tree सहायक हो सकता है।