पूंछ-रिकर्सन उन्मूलन क्या है?

Question

स्टीव येगे ने इसे blog post में वर्णित किया और मुझे नहीं पता कि इसका क्या अर्थ है, क्या कोई मुझे भर सकता है?

क्या यह tail call optimization जैसा ही है?

Answer 1

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

मूल रूप से बहुत आखिरी बात एक समारोह अगर Areturn A(params...) है तो आप एक स्टैक फ्रेम के आवंटन को समाप्त कर सकते हैं और इसके बजाय सेट कर सकते हैं उपयुक्त रजिस्टर और सीधे समारोह के शरीर में कूदो।

एक (काल्पनिक) कॉलिंग सम्मेलन पर विचार करें जो ढेर पर सभी मानकों को पास करता है और कुछ रजिस्टर में मूल्य देता है।

कुछ समारोह (एक काल्पनिक विधानसभा भाषा में) करने के लिए नीचे संकलन कर सकते हैं:

function: 
//Reading params B, C, & D off the stack 
pop B 
pop C 
pop D 
//Do something meaningful, including a base case return 
... 
//Pass new values for B, C, & D to a new invocation of function on the stack 
push D* 
push C* 
push B* 
call function 
ret 

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

में परिणामी:

function: 
//Reading params B, C, & D off the stack (but only on the first call) 
pop B 
pop C 
pop D 
function_tail_optimized: 
//Do something meaningful, including a base case return 
... 
//Instead of a new stack frame, load the new values directly into the registers 
load B, B* 
load C, C* 
load D, D* 
//Don't call, instead jump directly back into the function 
jump function_tail_optimized 

अंतिम परिणाम एक समान कार्य है जो विशेष रूप से आदानों कि पुनरावर्ती कॉल की एक बड़ी संख्या में परिणाम के लिए, ढेर अंतरिक्ष के एक बहुत बचाता है।

मेरे उत्तर में बहुत सी कल्पना की आवश्यकता है, लेकिन मुझे लगता है कि आप विचार प्राप्त कर सकते हैं।

Answer 2

here से

:।

"... टेल प्रत्यावर्तन उन्मूलन पूंछ कॉल उन्मूलन के विशेष मामला है, जिसमें पूंछ कॉल समारोह में ही उस मामले में कॉल करने के लिए एक फोन है उचित रजिस्टर या ढेर स्थानों के लिए नई बहस जाने के बाद समारोह के शुरू करने के लिए एक कूद द्वारा प्रतिस्थापित किया जा सकता है ... "

Wikipedia से:

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