रिकर्सन रन-टाइम मेमोरी का अप्रत्याशित उपयोग कैसे करता है?

Question

Code Complete 2 से हवाला देते हुए,

int Factorial(int number) { 
    if (number == 1) { 
     return 1; 
    } 
    else { 
     return number * Factorial(number - 1); 
    } 
} 

इसके अलावा धीमी^[1] और रन-टाइम स्मृति का इस्तेमाल कर रही अप्रत्याशित^[2], पुनरावर्ती संस्करण होने के इस दिनचर्या के को पुनरावृत्त संस्करण, से समझने के लिए कठिन है जो निम्नानुसार है:

int Factorial(int number) { 
    int intermediateResult = 1; 
    for (int factor = 2; factor <= number; factor++) { 
     intermediateResult = intermediateResult * factor; 
    } 
    return intermediateResult; 
} 

मुझे लगता है कि धीमा हिस्सा अनावश्यक फ़ंक्शन कॉल ओवरहेड्स की वजह से है।

लेकिन रिकर्सन रन-टाइम मेमोरी का उपयोग अप्रत्याशित कैसे करता है?

क्या हम हमेशा यह अनुमान नहीं लगा सकते कि कितनी मेमोरी की आवश्यकता होगी (जैसा कि हम जानते हैं कि रिकर्सन कब खत्म होना चाहिए)? मुझे लगता है कि यह पुनरावृत्ति के मामले के रूप में अप्रत्याशित होगा, लेकिन अब और नहीं।

Answer 1

तथ्य के कारण रिकर्सिव विधियों ने बार-बार उन्हें बुलाया, बहुत सारी स्टैक मेमोरी की आवश्यकता है। चूंकि ढेर सीमित है, इसलिए स्टैक मेमोरी पार हो जाने पर त्रुटियां उत्पन्न होंगी।

Answer 2

यदि रिकर्सन स्तर बहुत गहरा हो जाता है, तो आप कॉल स्टैक को उड़ा देंगे और प्रक्रिया में बहुत सारी मेमोरी खाएंगे। ऐसा तब हो सकता है जब आपका number एक "बड़ा पर्याप्त" मान हो। क्या आप इससे भी बदतर कर सकते हैं? हां, यदि आपका फ़ंक्शन प्रत्येक रिकर्सन कॉल के साथ अधिक ऑब्जेक्ट आवंटित करता है।

Answer 3

क्या हम हमेशा यह अनुमान नहीं लगा सकते कि कितनी मेमोरी की आवश्यकता होगी (जैसा कि हम जानते हैं कि रिकर्सन कब खत्म होना चाहिए)? मुझे लगता है कि यह पुनरावृत्ति के मामले के रूप में अप्रत्याशित होगा, लेकिन अब और नहीं।

नहीं, सामान्य मामले में नहीं। अधिक पृष्ठभूमि के लिए halting problem के बारे में चर्चा देखें। अब, यहां पोस्ट की गई समस्याओं में से एक का एक पुनरावर्ती संस्करण है:

void u(int x) { 
    if (x != 1) { 
     u((x % 2 == 0) ? x/2 : 3*x+1); 
    } 
} 

यह पूंछ-पुनरावर्ती भी है। चूंकि आप भविष्यवाणी नहीं कर सकते हैं कि यह सामान्य रूप से समाप्त हो जाएगा, तो आप भविष्यवाणी कैसे कर सकते हैं कि कितनी मेमोरी की आवश्यकता है?