पहचानने के लिए कि क्या है, और पूंछ रिकर्सन क्या नहीं है?

Question

कभी-कभी यह काफी आसान होता है (यदि स्वयं कॉल अंतिम बयान है, तो यह पूंछ रिकर्सन है), लेकिन अभी भी ऐसे मामले हैं जो मुझे भ्रमित करते हैं। एक प्रोफेसर ने मुझे बताया कि "यदि स्वयं कॉल के बाद निष्पादित करने के लिए कोई निर्देश नहीं है, तो यह पूंछ रिकर्सन है"। इन उदाहरणों के बारे में कैसे (इस तथ्य को नजरअंदाज करें कि वे अधिक समझ नहीं लेते हैं):

ए) यह एक पूंछ रिकर्सिव होना चाहिए, यह देखते हुए कि स्वयं कॉल अंतिम विवरण कैसे है, और उसके बाद निष्पादित करने के लिए कुछ भी नहीं बचा है ।

function foo(n) 
{ 
    if(n == 0) 
     return 0; 
    else 
     return foo(n-2); 
} 

बी) लेकिन इस बारे में कैसे? यह पूंछ कॉल होना चाहिए, क्योंकि यदि स्थिति सत्य है, तो इसे छोड़कर कुछ भी निष्पादित नहीं किया जाएगा, लेकिन यह अंतिम बयान नहीं है?

function foo(n) 
{ 
    if(n != 0) 
     return foo(n-2); 
    else 
     return 0; 
} 

सी) इस बारे में कैसे? दोनों मामलों में, स्वयं कॉल निष्पादित अंतिम बात होगी:

function foo(n) 
{ 
    if(n == 0) 
     return 0; 
    else  
    { 
     if(n > 100) 
      return foo(n - 2); 
     else 
      return foo(n - 1); 
    } 
} 

Answer 1

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

आमतौर पर जब कोई फ़ंक्शन कॉल किया जाता है, तो कॉलिंग कोड किसी भी रजिस्टर मान को संग्रहीत करेगा जिसे बाद में, स्टैक पर इसकी आवश्यकता होगी। यह एक वापसी पता भी संग्रहित करेगा, जो कॉल के बाद अगला निर्देश इंगित करेगा। यह सुनिश्चित करने के लिए कि स्टैक पॉइंटर कैली के लिए सही ढंग से सेट किया गया हो, यह करने के लिए जो कुछ भी करना है, वह करेगा। फिर यह लक्ष्य पते पर कूद जाएगा [*] (इस मामले में, एक ही समारोह)। बदले में, यह जानता है कि वापसी मूल्य कॉलिंग सम्मेलन (रजिस्टर या स्टैक स्लॉट) द्वारा निर्दिष्ट जगह पर है।

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

इसलिए, अनौपचारिक रूप से, एक फ़ंक्शन पूंछ-कॉल करने योग्य होता है जब पूंछ कॉल अनुकूलन होने के लिए संभव होता है, और जब पूंछ कॉल का लक्ष्य स्वयं कार्य होता है। प्रभाव कम या कम होता है जैसे कि फ़ंक्शन में लूप होता है, और खुद को कॉल करने के बजाय, पूंछ कॉल लूप की शुरुआत में कूद जाती है। इसका मतलब है कि कॉल के बाद आवश्यक कोई चर नहीं होना चाहिए (और वास्तव में कोई "काम करने के लिए" नहीं है, जो सी ++ जैसी भाषा में विनाश के लिए कुछ भी नहीं है), और पूंछ कॉल का वापसी मूल्य कॉलर द्वारा वापस किया जाना चाहिए।

यह सब सरल/छोटी पूंछ-रिकर्सन के लिए है। ऐसे परिवर्तन हैं जिनका उपयोग कुछ पूंछ-रिकर्सिव बनाने के लिए किया जा सकता है जो पहले से नहीं है, उदाहरण के लिए अतिरिक्त पैरामीटर पेश करना, जो कि "कम-से-कम" रिकर्सन के स्तर द्वारा उपयोग की जाने वाली कुछ जानकारी संग्रहीत करता है, जो काम अन्यथा किया जाता है बाहर का रास्ता"। तो उदाहरण के लिए:

int triangle(int n) { 
    if (n == 0) return 0; 
    return n + triangle(n-1); 
} 

पूंछ पुनरावर्ती बनाया जा सकता है, या तो प्रोग्रामर द्वारा या स्वचालित रूप से एक स्मार्ट पर्याप्त संकलक द्वारा, इस तरह:

int triangle(int n, int accumulator = 0) { 
    if (n == 0) return accumulator; 
    return triangle(n-1, accumulator + n); 
} 

इसलिए, पूर्व समारोह के रूप में "वर्णन किया जा सकता पूंछ रिकर्सिव "किसी ऐसे व्यक्ति द्वारा जो एक स्मार्ट पर्याप्त भाषा/कंपाइलर के बारे में बात कर रहा हो। उस संस्करण के उपयोग के लिए तैयार रहें।

[*] स्टैक पॉइंटर को स्थानांतरित करने और कूदने के लिए एक रिटर्न पता संग्रहीत करना, आर्किटेक्चर द्वारा एक ही ऑपोड में लपेटा जा सकता है या नहीं, लेकिन यदि ऐसा नहीं होता है तो आमतौर पर ऐसा होता है।

Answer 2

हाँ; मुझे लगता है कि आपके प्रोफेसर का मतलब है कि किसी भी पथ में, यदि अंतिम निर्देश रिकर्सिव है, तो यह पूंछ रिकर्सन है।

तो, सभी तीन उदाहरण पूंछ-पुनरावर्ती हैं।

Answer 3

आपके सभी कार्य पूंछ रिकर्सिव हैं।

कोई निर्देश के बाद छोड़ दिया आत्म फोन

का अर्थ है: आत्म-कॉल के बाद, आप समारोह से लौटने के लिए, यानी कोई और अधिक कोड निष्पादित करने के लिए है, और नहीं है कि वहाँ फ़ंक्शन में कोड की कोई और पंक्ति नहीं है।

Answer 4

सभी तीन उदाहरण पूंछ रिकर्सिव हैं। आम तौर पर, यह पूंछ का परिणाम है, यदि फ़ंक्शन का परिणाम ("वापसी" कीवर्ड के बाद अभिव्यक्ति) फ़ंक्शन के लिए एकमात्र कॉल है। अभिव्यक्ति के बाहरीतम स्तर में कोई अन्य ऑपरेटर शामिल नहीं होना चाहिए। यदि स्वयं को कॉल केवल अभिव्यक्ति का हिस्सा है तो मशीन को कॉल निष्पादित करना होगा, लेकिन फिर उसे अभिव्यक्ति के मूल्यांकन में वापस लौटना होगा, यानी, यह फ़ंक्शन निष्पादन की पूंछ पर नहीं था, लेकिन बीच में एक अभिव्यक्ति। हालांकि यह किसी भी पैरामीटर पर लागू नहीं होता है जो रिकर्सिव कॉल ले सकता है: कुछ भी अनुमति है, जिसमें रिकर्सिव कॉल भी शामिल हैं (उदा। "वापसी foo (foo (0));")। कूदने के लिए कॉल का अनुकूलन केवल बाहरी कॉल के लिए ही संभव है।