मेरे पास रिकर्सन पर एक प्रश्न है। जब भी रिकर्सन में आधार स्थिति हिट होती है तो हम रिकर्सिव कॉल करना बंद कर देते हैं और फिर स्टैक में विधि कॉल निष्पादित होती रहती है और मेमोरी स्टैक से एक-एक करके पॉप आउट हो जाती है।

मेरा सवाल यह है कि एक बार जब हम उस मूल स्थिति को मार देते हैं और अब कोई पुनरावर्ती कॉल नहीं है, तो जब हम स्टैक में पहली विधि कॉल निष्पादित करते हैं, तो प्रक्रिया को कैसे पता चलता है कि उसे विधि को फिर से कॉल करने की आवश्यकता नहीं है और उसे निष्पादित करना है इसे और इसे स्टैक मेमोरी से बाहर कर दिया?

उदाहरण के लिए, आइए इस पीस कोड पर एक नजर डालते हैं

private static String reverse(String str) {
    if(str.equals("")) {
        return "";
    }
    return reverse(str.substring(1)) + str.charAt(0);
}

इनपुट: my name is slim shady

आउटपुट: ydahs mils si eman ym

जब हम स्ट्रिंग रिवर्सल करते हैं, तो अब आधार स्थिति यह है कि यदि स्ट्रिंग खाली है तो उसी विधि को कॉल करने की कोई आवश्यकता नहीं है, लेकिन एक बार जब हम उस आधार स्थिति को हिट करते हैं तो स्टैक reverse("o") + "l" पर विधि कॉल होती है। इस छवि की तरह

enter image description here

प्रक्रिया कैसे जानती है कि उसे उस विधि को निष्पादित करना है और एक और पुनरावर्ती कॉल करने के बजाय पॉप आउट करना है? क्योंकि यह विधि reverse("o") + "l" इसे निष्पादित करने और इसे स्मृति से बाहर निकालने के बजाय किसी अन्य कॉल की तरह दिखती है।

1
Lokesh Pandey 5 सितंबर 2021, 05:25

2 जवाब

सबसे बढ़िया उत्तर

स्टैक पर कोड के टुकड़े होने के बारे में मत सोचो, लेकिन एक प्रोग्राम काउंटर जो विधि में एक विशेष बिंदु पर निष्पादन फिर से शुरू करेगा।

हम reverse(str.substring(1)) + str.charAt(0) को इस तरह विभाजित कर सकते हैं (जो मोटे तौर पर इसे संकलित करने के बाद जैसा दिखेगा):

tmp = reverse(str.substring(1));
tmp = tmp + str.charAt(0);
return tmp;

जब reverse() को कॉल किया जाता है, तो स्टैक पर पुश किया गया प्रोग्राम काउंटर tmp = tmp + str.charAt(0); पर इंगित करेगा, इसलिए जब पुनरावर्ती कॉल वापस आती है तो निष्पादन फिर से शुरू हो जाएगा।

1
tgdavies 5 सितंबर 2021, 02:44

मुझे लगता है कि आप इस बारे में सोच रहे हैं कि कैसे प्रत्येक रिकर्सिव कॉल को स्टैक पर गलत तरीके से धक्का दिया जाता है। चूंकि आपके प्रश्न का तात्पर्य है कि प्रत्येक रिकर्सिव कॉल में अभी भी एक और रिकर्सिव कॉल करने का विकल्प होता है।

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

जब आप बेस केस को हिट करते हैं, तो एक वेरिएबल वापस आ जाता है जिसका अर्थ है कि वर्तमान स्टैक फ्रेम को पॉप किया जा सकता है और स्टैक पॉइंटर को घटाया जा सकता है। चूंकि हमारे पास रिकर्सिव कॉल का रिटर्न वैल्यू है, पिछली रिकर्सिव कॉल (जिसमें पहले से ही ने अपनी रिकर्सिव कॉल की है) इसके अतिरिक्त ऑपरेशन को पूरा कर सकती है और वापस आ सकती है।

तो आपके प्रश्न का उत्तर प्रत्येक राज्य को बनाना और सहेजना है, जो इसे समाप्त करने के लिए अगले पुनरावर्ती राज्यों पर निर्भर है।

1
Vincent 5 सितंबर 2021, 02:38