c - what - सी में अनंत रिकर्सन



recursion (9)

कारण स्टैक सीमित है और जब भी आप फ़ंक्शन कॉल करते हैं तो यह बछड़ा को बचाता है (आधार सूचक को स्टैक पर दबाकर और मौजूदा स्टैक पॉइंटर को नए बेस पॉइंटर मान की प्रतिलिपि बनाकर) इसलिए खपत करता है कि कॉल की अनंत संख्या से स्टैक अतिप्रवाह हो जाएगा। कॉलिंग सम्मेलन देखें और यहां स्टैक ( http://www.csee.umbc.edu/~chang/cs313.s02/stack.shtml ) पर कैसे प्रतिक्रिया करता है

असीमित पुनरावर्तन के साथ सी प्रोग्राम को देखते हुए:

int main() {

    main();

    return 0;
}

यह एक स्टैक अतिप्रवाह का परिणाम क्यों होगा मैं जानता हूँ कि निम्न परिणाम से सी ++ में अपरिभाषित व्यवहार में यह परिणाम है क्या यह अनंत पुनरावर्ती यूबी है? (और साइड नोड के रूप में कोई C ++ में main() कॉल नहीं कर सकता)। हालांकि, valgrind बताता है कि यह एक स्टैक अतिप्रवाह होता है:

Stack overflow in thread 1: can't grow stack to 0x7fe801ff8

और फिर अंत में एक विभाजन त्रुटि के कारण समाप्त होता है:

==2907== Process terminating with default action of signal 11 (SIGSEGV)
==2907==  Access not within mapped region at address 0x7FE801FF0

क्या यह सी में भी अपरिभाषित व्यवहार है, या क्या यह वास्तव में एक स्टैक ओवरफ्लो की ओर ले जाता है और फिर यह स्टैक अतिप्रवाह में क्यों परिणाम करता है?

संपादित करें

1 मैं जानना चाहता हूं कि सी में अनन्त रिकर्सन की अनुमति है?
2 क्या इसका परिणाम स्टैक अतिप्रवाह में होना चाहिए? (पर्याप्त रूप से उत्तर दिया गया है)


जब भी आप फ़ंक्शन कॉल (मुख्य () सहित) करते हैं, फ़ंक्शन कॉल "info" (जैसे तर्क) स्टैक के शीर्ष पर धकेल दिया जाता है। जब फ़ंक्शन देता है तो यह जानकारी स्टैक बंद हो जाती है। लेकिन जैसा कि आप अपने कोड में देख सकते हैं, आप वापस आने से पहले मुख्य पर एक रिकर्सिव कॉल करते हैं, इसलिए स्टैक बढ़ते रह जाता है जब तक कि इसकी सीमा नहीं होती और इसलिए विभाजन त्रुटि।

स्टैक का आकार अक्सर सीमित होता है और रनटाइम से पहले तय होता है (जैसे आपके ऑपरेटिंग सिस्टम द्वारा)

इसका अर्थ है कि स्टैक अतिप्रवाह मुख्य () तक सीमित नहीं है, लेकिन किसी भी अन्य रिकर्सिव फ़ंक्शन के बिना अपने पेड़ (यानी बेस केस) को समाप्त करने के उचित तरीके के बिना।


पुनरावृत्ति एक प्रकार का पुनरावृत्ति है जो अगले चलने के लिए जाने से पहले स्थानीय राज्य को सुरक्षित रखता है। एक दूसरे के बाद एक दूसरे को बुलाने के लिए सिर्फ नियमित कार्यों की सोच के माध्यम से यह सोचना काफी आसान है:

void iteration_2 (int x) {
    /* ... */
}

void iteration_1 (int x) {
    if (x > 0) return;
    iteration_2(x + 1);
}

void iteration_0 (int x) {
    if (x > 0) return;
    iteration_1(x + 1);
}

प्रत्येक iteration_#() मूल रूप से एक दूसरे के समान है, लेकिन हर एक का अपना x , और प्रत्येक व्यक्ति को यह याद रहता है कि किस फ़ंक्शन ने इसे बुलाया था, इसलिए जब यह फ़ंक्शन कॉल करता है, तो इसे ठीक से कॉलर पर वापस कर सकते हैं। यह धारणा बदलती नहीं है जब कार्यक्रम पुनरावर्ती संस्करण में परिवर्तित हो जाता है:

void iteration (int x) {
    if (x > 0) return;
    iteration(x + 1);
}

अगर रोकथाम की स्थिति ( if फ़ंक्शन से return जाने की जांच हो) हटा दी जाती है तो चलना अनंत हो जाती है पुनरावर्ती से कोई वापसी नहीं है इसलिए प्रत्येक लगातार फंक्शन कॉल (स्थानीय x और कॉलर का पता) के लिए याद किया जाने वाला सूचना उस जानकारी को संग्रहीत करने के लिए ओएस रन होने तक तक सीमित रहता है।

यह एक असीम पुनरावर्ती फ़ंक्शन को लागू करना संभव है जो "स्टैक" को ओवरफ्लो नहीं करता है। पर्याप्त ऑप्टिमाइज़ेशन स्तर पर, कई कंपलर पूंछ रिकर्सिव कॉल के लिए कुछ भी याद रखने के लिए आवश्यक स्मृति को हटाने के लिए अनुकूलन लागू कर सकते हैं । उदाहरण के लिए, प्रोग्राम पर विचार करें:

int iteration () {
    return iteration();
}

जब gcc -O0 साथ संकलित किया जाता है, तो यह हो जाता है:

iteration:
.LFB2:
        pushq   %rbp
.LCFI0:
        movq    %rsp, %rbp
.LCFI1:
        movl    $0, %eax
        call    iteration
        leave
        ret

लेकिन, जब gcc -O2 साथ संकलित किया जाता है, तो रिकर्सिव कॉल को हटा दिया जाता है:

iteration:
.LFB2:
        .p2align 4,,7
.L3:
        jmp     .L3

इस अनंत पुनरावृत्ति का नतीजा एक सरल अनंत लूप है, और "स्टैक" का कोई अतिक्रमण नहीं होगा। अतः अनंत लूप की अनुमति है क्योंकि अनंत लूप की अनुमति है।

हालांकि, आपका कार्यक्रम पूंछ कॉल ऑप्टिमाइज़ेशन के लिए कोई उम्मीदवार नहीं है, क्योंकि रिकर्सिव कॉल आपके फ़ंक्शन का अंतिम कार्य नहीं है। आपके फ़ंक्शन में अभी भी एक return स्टेटमेंट होता है जो पुनरावर्ती कॉल का अनुसरण करता है। चूंकि अभी भी रिकर्सिव कॉल रिटर्न के बाद निष्पादित करने वाला कोड है, इसलिए अनुकूलक रिकर्सिव कॉल के ओवरहेड को नहीं निकाल सकता। यह कॉल को सामान्य रूप से वापस करने की अनुमति देनी चाहिए, ताकि यह कोड निष्पादित हो जाने के बाद हो। इसलिए, आपका कार्यक्रम हमेशा कॉलिंग कोड के रिटर्न पते को संग्रहित करने का जुर्माना देगा।

मानक किसी विशिष्ट पद में "अनंत पुनरावर्तन" से नहीं बोलता है मैंने एक साथ एकत्र किया है जो मुझे आपके प्रश्न से प्रासंगिक मानता है।

  • फ़ंक्शन को फिर से कॉल करने की अनुमति है (सी .1.16.6.2.2 ¶11)

पुनरावर्ती फ़ंक्शन कॉल्स को अन्य कार्यों की किसी भी श्रृंखला के माध्यम से सीधे और अप्रत्यक्ष रूप से अनुमति दी जाएगी।

  • एक बयान में पुनरावर्ती प्रविष्टि स्थानीय चर के नए उदाहरण बनाता है (सी। 11 §6.2.4 ¶5,6,7)

एक ऑब्जेक्ट जिसका पहचान किसी लिंक के साथ घोषित नहीं किया गया है और भंडारण-श्रेणी के विशिष्ट स्थिर स्थान के बिना स्वत: भंडारण अवधि है, जैसा कि कुछ मिश्रित शब्दावली करते हैं ...

ऐसे ऑब्जेक्ट के लिए जिस पर कोई चर लंबाई एरे टाइप नहीं होता है, उसके जीवनकाल ब्लॉक में प्रविष्टि से फैली हुई है, जिसके साथ यह संबंधित है जब तक उस ब्लॉक के निष्पादन को किसी भी तरह से समाप्त नहीं किया जाता है। (एक संलग्न ब्लॉक दर्ज करना या फ़ंक्शन निलंबित करने पर कॉल करना, लेकिन मौजूदा ब्लॉक के निष्पादन को खत्म नहीं करना है।) यदि ब्लॉक को बार-बार प्रवेश किया जाता है, तो ऑब्जेक्ट का नया इंस्टेंस हर बार बनाया जाता है ...

इस तरह के ऑब्जेक्ट के लिए एक वैरिएबल लम्बाई एरे टाइप करता है, इसके लाइफटाइम को ऑब्जेक्ट की घोषणा से लेकर आता है जब तक कि कार्यक्रम के निष्पादन में घोषणा के दायरे को छोड़ दिया जाता है। अगर गुंजाइश को बार-बार प्रवेश किया जाता है, तो हर बार वस्तु का एक नया उदाहरण बनाया जाता है।

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


यह समझना महत्वपूर्ण है कि कैसे सी में कार्यों के कॉलिंग स्टैक की तरह दिखता है:


प्रश्न 1 को संबोधित करते हुए:

मैं जानना चाहूंगा कि सी में अनुमत निरंतर पुनरावर्तन है?

John Regehr द्वारा इस लेख Compilers and Termination Revisited किया गया है कि C standard अनंत पुनरावर्तन की अनुमति देता है या नहीं, और मानक के माध्यम से तलाशी के बाद यह मेरे लिए आश्चर्य की बात नहीं है कि निष्कर्ष यह है कि यह अस्पष्ट है लेख मुख्य जोर असीम छोरों के बारे में है और चाहे वह विभिन्न भाषाओं ( C और C++ सहित) के मानक द्वारा समर्थित है, जो बिना निष्कासन फैलता है जहां तक ​​मैं चर्चा बता सकता हूं, अनंत रिकर्सन पर भी लागू होता है, ज़ाहिर है कि हम एक स्टैक अतिप्रवाह से बच सकते हैं।

C++ विपरीत, जो खंड 1.10 Multi-threaded executions and data races में कहता है 1.10 Multi-threaded executions and data races अनुच्छेद 24 :

The implementation may assume that any thread will eventually do one of the
following:
   terminate,
  [...]

जो C++ में अनंत रिकर्सन को बाहर करने के लिए लगता है draft C99 standard खंड 6.5.2.2 Function calls में बताता है 6.5.2.2 Function calls पैराग्राफ 11 :

पुनरावर्ती फ़ंक्शन कॉल्स को अन्य कार्यों की किसी भी श्रृंखला के माध्यम से सीधे और अप्रत्यक्ष रूप से अनुमति दी जाएगी।

जो पुनरावर्तीकरण पर कोई सीमा नहीं रखता है और इसे खंड 5.1.2.3 Program execution में बताता है 5.1.2.3 Program execution पैराग्राफ 5 :

The least requirements on a conforming implementation are:
 At sequence points, volatile objects are stable in the sense that previous 
  accesses are complete and subsequent accesses have not yet occurred.
 At program termination, all data written into files shall be identical to the
  result that execution of the program according to the abstract semantics would
  have  produced.
 The input and output dynamics of interactive devices shall take place as
  specified in 7.19.3. The intent of these requirements is that unbuffered or     
  line-buffered output appear as soon as possible, to ensure that prompting
  messages actually appear prior to a program waiting for input.

जैसा कि लेख कहते हैं, पहली शर्त को पूरा करने के लिए सीधे आगे होना चाहिए, लेख के अनुसार तीसरी शर्त वास्तव में समाप्ति को कवर नहीं करती है। इसलिए हम दूसरी स्थिति से निपटने के लिए छोड़ देते हैं। अनुच्छेद के अनुसार यह अस्पष्ट है, लेख से उद्धरण इस प्रकार है:

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

तो आपके पास यह है: संकलक विक्रेताओं मानक एक तरह से पढ़ रहे हैं, और अन्य (मेरे जैसे) इसे दूसरी तरफ पढ़ा यह बहुत स्पष्ट है कि मानक दोषपूर्ण है: सी ++ या जावा की तरह, इस व्यवहार की अनुमति है या नहीं, यह स्पष्ट होना चाहिए।

चूंकि ऐसा लगता है कि दूसरी शर्त के दो उचित अभी तक परस्पर विरोधी व्याख्याएं हैं, मानक की कमी है और स्पष्ट रूप से यह परिभाषित करना चाहिए कि इस व्यवहार की अनुमति है या नहीं।


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


इसे सी में अनुमति है, क्योंकि मानक कहते हैं ->

पुनरावर्ती फ़ंक्शन कॉल्स को अन्य कार्यों की किसी भी श्रृंखला के माध्यम से सीधे और अप्रत्यक्ष रूप से अनुमति दी जाएगी।

6.5.2.2 में -> 11

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


मैंने एक हालिया मसौदा सी मानक डॉक्टर की प्रतिलिपि को देखा और किसी भी पुनरावर्ती संदर्भ में अनंत यादों के बारे में बात नहीं की।

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


यहां तक ​​कि अगर फ़ंक्शन स्थानीय चर के लिए स्टैक स्पेस का उपयोग नहीं करता है या तर्क पारित कर रहा है, फिर भी इसे रिटर्न पता और (संभवतः) फ़्रेम के आधार सूचक को स्टोर करने की आवश्यकता है (जीसीसी के साथ, यह -fomit-frame-pointer द्वारा अक्षम किया जा सकता है)।

उच्च पर्याप्त अनुकूलन स्तरों पर, संकलक एक पुनरावर्ती को एक लूप में फिर से लिखने में सक्षम हो सकता है, यदि पूंछ-कॉल अनुकूलन लागू हो, जो स्टैक अतिप्रवाह से बचना होगा।





recursion