पूंछ प्रत्यावर्तन कॉल (सी प्राइमर प्लस किताब उदाहरण)

Question

C Primer Plus (6th edition) में, यह इस तरह से tail recursion concept परिभाषित करता है:

प्रत्यावर्तन का सरलतम रूप में, पुनरावर्ती कॉल समारोह के अंत में है, वापसी बयान से ठीक पहले। इसे पूंछ रिकर्सन, या एंड रिकर्सन कहा जाता है, क्योंकि रिकर्सिव कॉल अंत में आता है। पूंछ रिकर्सन सबसे सरल रूप है क्योंकि यह लूप की तरह कार्य करता है।

और यह एक पूंछ पुनरावर्ती ढंग से भाज्य की गणना का एक उदाहरण देता है:

नोट:

long rfact(int n) { 
    long ans; 
    if (n > 0) 
     ans = n * rfact(n - 1); 
    else 
     ans = 1; 
    return ans; 
} 

यह भी एक पक्ष टिप्पणी है, जो मेरी राय में सही नहीं है बनाता है हालांकि हालांकि rfact() के लिए रिकर्सिव कॉल फ़ंक्शन में आखिरी पंक्ति नहीं है, यह अंतिम विवरण है जिसे n> 0 पर निष्पादित किया गया है, इसलिए यह पूंछ रिकर्सन है।

एक स्पष्ट रूप से देख सकते हैं कि पिछले बयान n * rfact(n - 1) जो, अगर आप रिकर्सिवली का विस्तार, यह आस्थगित गुणा की एक श्रृंखला के लिए नेतृत्व करेंगे है। प्रक्रिया प्रकृति में पुनरावर्ती है, इसलिए कार्यान्वयन here वर्णित अनुसार पूंछ रिकर्सिव नहीं हो सकता है।

उदाहरण भ्रामक है। आप की राय क्या है?

Answer 1

जहां तक ​​एक अच्छी सी प्रोग्रामिंग पुस्तक जाती है, मैंने सी प्रोग्रामिंग भाषा का उपयोग किया।

आप कह रहे हैं कि यह पूंछ रिकर्सन नहीं है। एक भाज्य के लिए विशिष्ट पूंछ प्रत्यावर्तन उदाहरण है:

int factorial(int x) { 
    return tailfactorial(x, 1); 
} 

int tailfactorial(int x, int multiplier) { 
    if (x <= 0) { 
     return multiplier;  
    }  
    return tailfactorial(x - 1, x * multiplier); 
} 

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

Answer 2

दी गई परिभाषा और उदाहरण दोनों भ्रामक हैं। tail recursion की परिभाषा है:

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

यह आवश्यक नहीं है कि रिकर्सिव कॉल रिटर्न स्टेटमेंट या फ़ंक्शन के अंतिम विवरण से पहले होना चाहिए। एक उदाहरण देखें:

function foo(data) { 
    a(data); 
    return b(data); 
} 

इस मामले a में सिर्फ return बयान से पहले है, लेकिन b पूंछ स्थिति में है।

function bar(data) { 
    if (a(data)) { 
     return b(data); 
    } 
    return c(data); 
} 

इस उदाहरण में, दोनों b और c पूंछ स्थिति में हैं, हालांकि b समारोह bar के अंत में नहीं है।

अपने दिए गए उदाहरण में, आखिरी बात समारोह वापसी से पहले प्रदर्शन कर रहा है गुणा

ans = n * rfact(n - 1); 

इसलिए, इसकी नहीं एक पूंछ पुनरावर्ती क्रिया है। पूंछ पुनरावर्ती क्रिया की

Am उदाहरण

factorial1(n, accumulator) { 
    if (n == 0) return accumulator; 
    return factorial1(n - 1, n * accumulator); // The last thing, before return, performed 
               // by factorial1 is to call itself. 
    } 

    factorial(n) { 
    return factorial1(n, 1); 
    } 

जो

factorial1(n, accumulator) { 
    while (n != 0) { 
     accumulator *= n; 
     n -= 1; 
    } 
    return accumulator; 
    }