बुनियादी रिकर्सन

public static void main (String[] args) 
{ 
    System.out.println(factorial(5)); 
} 

public int factorial(int n) 
{ 
    if(n <= 1){ 
     return 1; 
    } 
    else{ 
     return n * factorial(n - 1); 
    } 
}

मैंने उपरोक्त सीधे यहां लिखा है, इसलिए संकलित नहीं हो सकता है लेकिन ऐसा लगता है।बुनियादी रिकर्सन

क्या कोई भी बुद्धिमानी से समझा सकता है कि यह कैसे संसाधित करता है कि यह कैसे संग्रहीत किया जाता है? यह 5 * (5-1) की गणना करके शुरू होता है, फिर नीचे 4 * (4-1) फिर 3 * (3-1) ..... जब तक यह 1 तक नहीं पहुंच जाता है जो केवल 1 दाएं वापस आ जाएगा? इसलिए अधूरा होने के लिए खेद मैं सिर्फ पता लगाने के लिए कि यह कैसे काम करता है वास्तव में

धन्यवाद

रुचि होगी लेकिन के रूप में यह इसे बाहर काम करता है - यह अलग-अलग चरणों के लिए मान हो जाता है

5 * (5 -1) 4 * (4-1) ... ... ...

कैसे इन संग्रहीत और फिर वापस लिया गया या मैं कुछ याद आ रही है कर रहे हैं?

स्रोत

2009-12-22 sonny

5 * ((5-1) * (() 4-1) * ((3-1) * ((2-1) * 1))) – jball

शायद यह प्रश्न आपको मदद करता है: http://stackoverflow.com/questions/1949454/-) – Esko

मैं चाहता था टिप्पणी करना पसंद है कि फैक्टोरियल एक * बुरा * रिकर्सन का उदाहरण है। –

कल्पना कीजिए कि आप कंप्यूटर हैं, और किसी को आप उस पर लिखा

factorial(3)

के साथ एक कागज हाथ। फिर आप तर्क को देखते हुए प्रक्रिया निष्पादित करते हैं। चूंकि यह> 1 है, तो आप कागज के एक और टुकड़े पर लिख

factorial(2)

और "अपने आप से यह हाथ", जब तक आप आगे बढ़ने से पहले कि एक के लिए जवाब मिल इंतज़ार कर।

फिर से आप प्रक्रिया को निष्पादित करते हैं।के बाद से 2 अभी भी> है 1 यदि आपने अभी तक कागज का एक और टुकड़ा पर

factorial(1)

लिख सकते हैं और अपने आप को को देते हैं, जब तक आप आगे बढ़ने से पहले यह एक करने के लिए जवाब मिल इंतज़ार कर।

फिर, आप प्रक्रिया को निष्पादित करते हैं। इस बार इनपुट 1 है, इसलिए आप पहली शाखा लेते हैं और वापस आते हैं 1. आविष्कार जो प्रसंस्करण प्रसंस्करण कर रहा था (2) अब एक जवाब है, इसलिए यह उस उत्तर (1) और रिटर्न द्वारा 2 गुणा करता है। अब फैक्टोरियल (3) को संभालने वाला आमंत्रण इसका जवाब प्राप्त करता है (2) और इसे 3 से 6 तक गुणा करता है। फिर वह उस व्यक्ति को जवाब देता है जिसने पूरे ऑपरेशन को शुरू किया।

यदि आप कल्पना करते हैं कि आप काम करते समय पेपर के टुकड़े आपके सामने एक ढेर में रखते हैं, तो यह कंप्यूटर की स्मृति में "ढेर" का दृश्य है। प्रत्येक पुनरावर्ती आमंत्रण पैरामीटर (और किसी भी अस्थायी चर) को अपने स्वयं के पेपर (स्टैक फ्रेम) पर संग्रहीत करता है, जो सचमुच काग़ज़ की तरह पुशडाउन स्टैक के रूप में व्यवस्थित होता है, एक दूसरे के शीर्ष पर।

स्रोत

2009-12-22 22:06:10

इसलिए यह काम करने से पहले बहुत नीचे तक काम करता है फिर से शीर्ष पर वापस जाने के तरीके और यह एक ढेर में संग्रहीत है? – sonny

अब तक यह वास्तव में रिकर्सन के "रिकर्सन" भाग को समझाते हुए सबसे नज़दीक है। :) – GrayWizardx

'स्टैक' में 'स्टैक' में नहीं है। प्रत्येक एप्लिकेशन जो गतिशील रूप से स्मृति आवंटित कर सकता है (भाषा की परवाह किए बिना बहुत अधिक) में एक ढेर और ढेर होता है। कभी-कभी ढेर के आकार पर एक सीमा होती है, और ढेर पर हमेशा एक सीमा होती है। –

.... फिर 3 * (3-1) ..... जब तक यह 1 तक नहीं पहुंच जाता है जो सिर्फ 1 सही होगा?

सही है, लेकिन यह रिटर्न कि '1' के बगल में करने के लिए पिछले मंगलाचरण है, जो दो से गुणा करेंगे, लौटने '2' ... के बगल में करने के लिए अगले करने के लिए पिछले है, जो तीन गुना बढ़ेगा .....

स्रोत

2009-12-22 22:00:25 Javier

हाँ आपके पास कोड में यह सही है, यह पहले n का मान जांचता है यदि यह 1 से कम या उसके बराबर है, जिसे आपके बेस केस के रूप में जाना जाता है। वे महत्वपूर्ण हैं, जब वे रुकने के लिए आपके रिकर्सिव फ़ंक्शन को बताते हैं। if (n <= 1) जहां यह रिटर्न 1

तो n का मूल्य से कम या बराबर नहीं है, यह रिटर्न factorial की पुनरावर्ती कॉल द्वारा लेकिन जब तक यह यह तक पहुँचता मूल्य n-1 साथ गुणा n का मूल्य आधार मामला है

आपका आधार मामले 0! और 1! के भाज्य definiton जो दोनों 1.

के बराबर हो सकता है कि इस चित्र को समझने के लिए कॉल काम सहायक हो सकते हैं द्वारा स्थापित किया गया था।

5 * fact(5-1) -> 
      4 * fact(4-1) -> 
        3 * fact(3-1) -> 
           2 * fact(1) 
             1

कौन सा रूप 5! या 5 x 4 x 3 x 2 x 1

आशा इस मदद करता ही है।

स्रोत

2009-12-22 22:01:15

क्या आप पूछ रहे हैं कि रिकर्सन आंतरिक रूप से कैसे काम करता है? एक वाक्य का जवाब यह है कि प्रत्येक धागे में "कॉल स्टैक" होता है और हर बार एक विधि कहलाती है, इस स्टैक पर एक नई प्रविष्टि धकेलती है, जिसमें किस विधि के बारे में जानकारी है, और तर्क क्या थे। जब विधि समाप्त हो जाती है तो यह उसी वापसी पर वापस लौटाती है और कॉलिंग विधि इसे खींचती है। तो उसकी ऊंचाई पर अपने ढेर की तरह

भाज्य दिखेगा (1) भाज्य से बुलाया (2) भाज्य से बुलाया (3) भाज्य से बुलाया (4) भाज्य (5)

से बुलाया कॉल स्टैक्स पर Wikipedia article पहली नज़र में बहुत अच्छी तरह से लगता है।

स्रोत

2009-12-22 22:06:48 Dan

फैक्टोरियल, एन = 5 के प्रारंभिक कॉल में, और स्टैक पर धक्का दिया जाता है।
फिर अन्य ट्रिगर किया गया है इसलिएफैक्टोरियल तक पारित किया गया है, और स्टैक पर धक्का दिया गया है।
फिर अन्यथा ट्रिगर किया गया है इसलिएफैक्टोरियल पास हो गया है, और स्टैक पर धक्का दिया गया है।
फिर दूसरा ट्रिगर किया गया है इसलिए 2 फैक्टोरियल पास हो गया है, और स्टैक पर धक्का दिया गया है।
फिर अन्यथा ट्रिगर किया गया है इसलिए 1 फैक्टोरियल पास हो गया है, और स्टैक पर धक्का दिया गया है।
फिर अन्यथा ट्रिगर किया गया हैफैक्टोरियल पास हो गया है, और स्टैक पर धक्का दिया गया है।
यदि ट्रिगर हो जाता है और 1 कॉलिंग फैक्टोरियल में वापस आ गया है।
यदि ट्रिगर हो जाता है और 2 * 1 कॉलिंग फैक्टोरियल में वापस आ जाता है।
यदि ट्रिगर हो जाता है और 3 * 2 कॉलिंग फैक्टोरियल में लौट आया है।
अगर ट्रिगर हो जाता है और 4 * 3 कॉलिंग फैक्टोरियल में वापस आ जाता है।
यदि ट्रिगर हो जाता है और 5 * 4 कॉलिंग फैक्टोरियल में लौट आया है।

ढेर भी साफ हो जाता है, हालांकि यह टाइप करने के लिए बहुत कठिन हो जाता है। अनिवार्य रूप से एक विधि कॉल में सभी मूल्यों को ढेर पर धकेल दिया जाता है, और विधियों की वापसी पर ढेर से पॉप अप किया जाता है। यह उन्हें रिकर्सिव कॉल के बीच अलग रखता है।

स्रोत

2009-12-22 22:08:10

Plz लाइन 5 और लाइन 6 की व्याख्या करता है, जैसे कि 1 को फैक्टोरियल में पारित किया जाता है, 'अगर' ट्रिगर होता है और यह 1 लौटाता है और 'अन्य' ट्रिगर नहीं होता है, जबकि आप लाइन 6 में उल्लेख करते हैं कि 0 फैक्टोरियल को पास किया जाता है जो मेरी समझ में नहीं मिलता है बिलकुल पारित – Zaki

कोड में, अंतिम वापसी एन <1 तक नहीं होती है, इसलिए 0 पास हो जाता है। मेरे पास बहुत अधिक है अगर ट्रिगर हो जाता है। यह "विधि रिटर्न" होना चाहिए। यह रिकर्सन के साथ समस्या है, बहुत अधिक प्रतिलिपि और पेस्ट त्रुटियों :) –

यह नोट करना महत्वपूर्ण है कि "प्रत्यावर्तन" अलग ढंग से जावा में (एक प्रक्रियात्मक भाषा) काम करता है की तुलना में यह में हास्केल या एफ # (कार्यात्मक भाषाओं) का कहना है कि नहीं करता है।

जावा में जब हम अभिव्यक्ति पेड़ का मूल्यांकन करने और यह के प्रत्येक भाग को हल करने जब तक हम अभिव्यक्ति के प्रत्येक भाग का मूल्य निर्धारित द्वारा प्रत्यावर्तन हम ऐसा आह्वान। अगर हमें किसी अन्य कार्य को आमंत्रित करने की आवश्यकता है तो हम उस बिंदु पर सभी मध्यवर्ती मूल्यों के लिए एक प्लेसहोल्डर डालते हैं और फिर नए फ़ंक्शन के लिए एक नया अभिव्यक्ति वृक्ष बनाना शुरू करते हैं।

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

पहले मामले में हम स्टैक के शीर्ष से प्रत्येक अभिव्यक्ति पेड़ को हल करना शुरू करते हैं, जब तक कि उनकी कोई स्टैक प्रविष्टियां नहीं छोड़ी जाती हैं, तब तक हमारे रास्ते पर काम करना शुरू होता है, जिस बिंदु पर अभिव्यक्ति वृक्ष अंतिम मूल्य लौटाता है।

जिम की जवाब इस के लिए एक उत्कृष्ट शारीरिक रूपक है।

स्रोत

2009-12-22 22:15:20 GrayWizardx

यह लगता है कि वास्तव में प्रत्यावर्तन के कौन से भाग आप के साथ परेशानी हो रही है मुश्किल है, लेकिन मैं अपने प्रश्न के इस हिस्से से दूर जाने के लिए जा रहा हूँ:

जब तक यह जो सिर्फ वापस आ जाएगी 1 से 1 हो जाता है सही?

मैं तुम्हें मतलब है, अनुमान लगा रहा हूँ "अगर यह सिर्फ 1 वापस आ जाएगी, क्यों 1 समारोह के नहीं परिणाम है?"

पर विचार करें कि जब आप एक समारोह से लौट (इस मामले में, भाज्य) जिनके भी मूल रूप से यह करने के लिए कहा करने के लिए एक मूल्य के लिए लौट रहे हैं।

अगर मैं कहता हूँ "दे मुझे भाज्य (5)" तो भाज्य (5) मुझे मान प्रदान करेगा, लेकिन इससे पहले यह मेरे मूल्य लौट सकते हैं यह भाज्य (4) अपने मूल्य के लिए, भाज्य (पूछने के लिए है 5) अनिवार्य रूप से कहता है "मुझे फैक्टोरियल (4) दें ताकि मैं इसे 5 तक गुणा कर सकूं और उसे उस व्यक्ति को वापस दे सकूं जिसने फैक्टरियल (5) पूछा।" अब फैक्टोरियल (4) अपने मूल्य को फैक्टोरियल (5) में वापस कर देगा जो इसे एन से गुणा कर सकता है और अपना मूल्य वापस मेरे पास वापस कर सकता है। याद रखें, I फैक्टरियल (4) के मूल्य के लिए नहीं पूछा था, मुझे भी परवाह नहीं है, और यह मेरे पास वापस नहीं आया, यह फैक्टोरियल (5) पर वापस चला गया।

जब तक आप फैक्टोरियल (1) मारा, तब तक आप फैक्टोरियल (2), फैक्टोरियल (3), फैक्टोरियल (4) और फैक्टोरियल (5) सभी को जवाब देने का इंतजार करेंगे। फैक्टोरियल (1) अपने मूल्य (जो आपके आधार मामले की वजह से 1 है) को फैक्टोरियल (2) में वापस कर देगा, जो आखिरकार फैक्टोरियल (3) पर लौट सकता है और इसी तरह, जिस पर रिकर्सन पूरा हो जाएगा और आप फैक्टोरियल (5) वापस मूल्य प्राप्त करें।

स्रोत

2009-12-22 22:27:38

एक व्यावहारिक दृष्टिकोण है जो एक अच्छा आईडीई (ग्रहण, NetBeans, IntelliJ) की आवश्यकता है:

लाइन जो return 1 और आवेदन डिबग पढ़ता करने के लिए एक ब्रेकपाइंट जोड़ें। जब यह रुक जाता है, तो स्टैक ट्रेस देखें। आप देखेंगे कि फैक्टोरियल विधि को कई बार बुलाया गया है।

ग्रहण डीबग व्यू निलंबित धागा और छह प्रविष्टियों के साथ एक ढेर दिखाता है, प्रत्येक पंक्ति कोड की एक पंक्ति का प्रतिनिधित्व करती है जहां एक और विधि कहा जाता है (शीर्ष प्रविष्टि को छोड़कर - यह ब्रेकपॉइंट है)। फैक्टोरियल पांच बार प्रकट होता है, आप प्रत्येक पंक्ति का चयन कर सकते हैं और वेरिएबल व्यू में एन के मान को देख सकते हैं (यह मूल है और किसी अन्य तरीके से अन्य आईडीई पर काम करना चाहिए)।

कि एक और विचार कैसे पुनरावर्ती विधि काम कॉल देना चाहिए (और क्यों आप स्मृति त्रुटि से बाहर प्राप्त जब आप ठीक ढंग से बाहर निकलने का मानदंड निर्धारित नहीं है,)

स्रोत

2009-12-22 22:32:24

बुनियादी रिकर्सन

उत्तर

संबंधित मुद्दे