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




language-agnostic functional-programming (15)

जबकि lisp सीखना शुरू करते हैं, मैं शब्द पूंछ-रिकर्सिव शब्द भर में आया हूँ। इसका क्या मतलब है?


एक पूंछ रिकर्सन एक रिकर्सिव फ़ंक्शन है जहां फ़ंक्शन फ़ंक्शन के अंत ("पूंछ") पर स्वयं को कॉल करता है जिसमें रिकर्सिव कॉल की वापसी के बाद कोई गणना नहीं की जाती है। कई कंपाइलर्स एक रिकर्सिव कॉल को पूंछ रिकर्सिव या पुनरावर्तक कॉल में बदलने के लिए ऑप्टिमाइज़ करते हैं।

किसी संख्या के फैक्टरियल की गणना करने की समस्या पर विचार करें।

एक सीधा दृष्टिकोण होगा:

  factorial(n):

    if n==0 then 1

    else n*factorial(n-1)

मान लीजिए कि आप फैक्टोरियल (4) कहते हैं। रिकर्सन पेड़ होगा:

       factorial(4)
       /        \
      4      factorial(3)
     /             \
    3          factorial(2)
   /                  \
  2                factorial(1)
 /                       \
1                       factorial(0)
                            \
                             1    

उपरोक्त मामले में अधिकतम रिकर्सन गहराई ओ (एन) है।

हालांकि, निम्नलिखित उदाहरण पर विचार करें:

factAux(m,n):
if n==0  then m;
else     factAux(m*n,n-1);

factTail(n):
   return factAux(1,n);

तथ्य के लिए रिकर्सन पेड़ टेल (4) होगा:

factTail(4)
   |
factAux(1,4)
   |
factAux(4,3)
   |
factAux(12,2)
   |
factAux(24,1)
   |
factAux(24,0)
   |
  24

यहां भी, अधिकतम रिकर्सन गहराई ओ (एन) है लेकिन कॉल में से कोई भी स्टैक में कोई अतिरिक्त चर नहीं जोड़ता है। इसलिए संकलक एक ढेर से दूर कर सकते हैं।


इस प्रश्न में बहुत सारे अच्छे उत्तर हैं ... लेकिन मैं मदद नहीं कर सकता लेकिन वैकल्पिक रूप से "पूंछ रिकर्सन" को परिभाषित करने, या कम से कम "उचित पूंछ रिकर्सन" को परिभाषित करने के लिए चुनौती देता हूं। अर्थात्: क्या इसे किसी प्रोग्राम में किसी विशेष अभिव्यक्ति की संपत्ति के रूप में देखना चाहिए? या किसी को प्रोग्रामिंग भाषा के कार्यान्वयन की संपत्ति के रूप में देखना चाहिए?

बाद के दृश्य पर अधिक के लिए, विल क्लिंजर, "उचित टेल रिकर्सन एंड स्पेस एपिसिटी" (पीएलडीआई 1 99 8) द्वारा एक क्लासिक paper है, जिसने प्रोग्रामिंग भाषा कार्यान्वयन की संपत्ति के रूप में "उचित पूंछ रिकर्सन" परिभाषित किया है। परिभाषा का निर्माण एक को कार्यान्वयन विवरणों को अनदेखा करने की अनुमति देने के लिए किया गया है (जैसे कि कॉल स्टैक वास्तव में रनटाइम स्टैक के माध्यम से या फ़्रेम के ढेर-आवंटित लिंक की सूची के माध्यम से दर्शाया जाता है)।

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

पेपर कई कारणों से सावधानीपूर्वक अध्ययन करने योग्य है:

  • यह एक कार्यक्रम की पूंछ अभिव्यक्तियों और पूंछ कॉल की एक अनिवार्य परिभाषा देता है। (ऐसी परिभाषा, और क्यों ऐसी कॉल महत्वपूर्ण हैं, यहां दिए गए अधिकांश उत्तरों का विषय प्रतीत होता है।)

    पाठ की स्वाद प्रदान करने के लिए, ये परिभाषाएं यहां दी गई हैं:

    परिभाषा 1 कोर योजना में लिखे गए कार्यक्रम की पूंछ अभिव्यक्तियों को निम्नानुसार अनिवार्य रूप से परिभाषित किया गया है।

    1. लैम्ब्डा अभिव्यक्ति का शरीर पूंछ अभिव्यक्ति है
    2. यदि (if E0 E1 E2) पूंछ अभिव्यक्ति है, तो E1 और E2 दोनों पूंछ अभिव्यक्ति हैं।
    3. पूंछ अभिव्यक्ति कुछ और नहीं है।

    परिभाषा 2 एक पूंछ कॉल एक पूंछ अभिव्यक्ति है जो एक प्रक्रिया कॉल है।

(एक पूंछ रिकर्सिव कॉल, या जैसा कि पेपर कहता है, "स्वयं-पूंछ कॉल" एक पूंछ कॉल का एक विशेष मामला है जहां प्रक्रिया स्वयं को बुलाया जाता है।)

  • यह कोर स्कीम का मूल्यांकन करने के लिए छह अलग-अलग "मशीनों" के लिए औपचारिक परिभाषाएं प्रदान करता है, जहां प्रत्येक मशीन में एसिम्प्टोटिक स्पेस कॉम्प्लेक्सिटी क्लास को छोड़कर एक ही अवलोकन योग्य व्यवहार होता है जिसमें प्रत्येक होता है।

    उदाहरण के लिए, क्रमशः मशीनों के लिए परिभाषाएं देने के बाद, 1. स्टैक-आधारित मेमोरी प्रबंधन, 2. कचरा संग्रह लेकिन कोई पूंछ कॉल नहीं, 3. कचरा संग्रह और पूंछ कॉल, पेपर आगे भी उन्नत स्टोरेज प्रबंधन रणनीतियों के साथ जारी है, जैसे कि 4. "evlis पूंछ रिकर्सन", जहां पर्यावरण को पूंछ कॉल में अंतिम उप-अभिव्यक्ति तर्क के मूल्यांकन में संरक्षित करने की आवश्यकता नहीं है, 5. उस बंद होने के केवल मुफ्त चर के बंद होने के वातावरण को कम करना, और 6. एपेल और शाओ द्वारा परिभाषित तथाकथित "सुरक्षित-स्थान-स्थान" अर्थशास्त्र।

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

(अब मेरे जवाब पर पढ़ना, मुझे यकीन नहीं है कि क्या मैं वास्तव में paper के महत्वपूर्ण बिंदुओं को पकड़ने में कामयाब रहा हूं। लेकिन, paper , मैं अभी इस जवाब को विकसित करने के लिए और अधिक समय नहीं दे सकता।)


एक महत्वपूर्ण बात यह है कि पूंछ की पुनरावृत्ति अनिवार्य रूप से लूपिंग के बराबर होती है। यह सिर्फ संकलक अनुकूलन का मामला नहीं है, बल्कि अभिव्यक्ति के बारे में एक मौलिक तथ्य है। यह दोनों तरीकों से जाता है: आप फॉर्म का कोई भी लूप ले सकते हैं

while(E) { S }; return Q

जहां E और Q अभिव्यक्तियां हैं और S कथन का अनुक्रम है, और इसे एक पूंछ रिकर्सिव फ़ंक्शन में बदल देता है

f() = if E then { S; return f() } else { return Q }

बेशक, E , S , और Q को कुछ चरों पर कुछ रोचक मूल्य की गणना करने के लिए परिभाषित किया जाना है। उदाहरण के लिए, लूपिंग फ़ंक्शन

sum(n) {
  int i = 1, k = 0;
  while( i <= n ) {
    k += i;
    ++i;
  }
  return k;
}

पूंछ-पुनरावर्ती कार्य के बराबर है

sum_aux(n,i,k) {
  if( i <= n ) {
    return sum_aux(n,i+1,k+i);
  } else {
    return k;
  }
}

sum(n) {
  return sum_aux(n,1,0);
}

(कम पैरामीटर वाले फ़ंक्शन के साथ पूंछ-रिकर्सिव फ़ंक्शन का यह "रैपिंग" एक सामान्य कार्यात्मक मुहावरे है।)


जावा में, यहां फाइबोनैकी फ़ंक्शन का संभावित पूंछ पुनरावर्ती कार्यान्वयन है:

public int tailRecursive(final int n) {
    if (n <= 2)
        return 1;
    return tailRecursiveAux(n, 1, 1);
}

private int tailRecursiveAux(int n, int iter, int acc) {
    if (iter == n)
        return acc;
    return tailRecursiveAux(n, ++iter, acc + iter);
}

मानक पुनरावर्ती कार्यान्वयन के साथ इसकी तुलना करें:

public int recursive(final int n) {
    if (n <= 2)
        return 1;
    return recursive(n - 1) + recursive(n - 2);
}

नियमित रिकर्सन का उपयोग करके, प्रत्येक रिकर्सिव कॉल कॉल स्टैक पर एक और प्रविष्टि डालता है। जब रिकर्सन पूरा हो जाता है, तब ऐप को प्रत्येक प्रविष्टि को वापस नीचे से पॉप करना होगा।

पूंछ रिकर्सन के साथ, कंपाइलर स्टैक को एक प्रविष्टि में पतन करने में सक्षम है, इसलिए आप स्टैक स्पेस को सहेजते हैं ... एक बड़ी रिकर्सिव क्वेरी वास्तव में एक स्टैक ओवरफ़्लो का कारण बन सकती है।

मूल रूप से पूंछ के पुनरावृत्ति पुनरावृत्ति में अनुकूलित करने में सक्षम हैं।


पूंछ रिकर्सन रिकर्सिव एल्गोरिदम में अंतिम तर्क निर्देश में पिछली बार रिकर्सिव कॉल को संदर्भित करता है।

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

factorial(x, fac) {
  if (x == 1)
     return fac;
   else
     return factorial(x-1, x*fac);
}

ध्यान दें, फैक्टोरियल के लिए प्रारंभिक कॉल फैक्टोरियल (एन, 1) होना चाहिए जहां एन वह संख्या है जिसके लिए फैक्टोरियल की गणना की जानी चाहिए।


मैं एक लिस्प प्रोग्रामर नहीं हूं, लेकिन मुझे लगता है कि this मदद मिलेगी।

असल में यह प्रोग्रामिंग की एक शैली है जैसे रिकर्सिव कॉल आखिरी चीज है जो आप करते हैं।


यह पूंछ रिकर्सन के बारे में कंप्यूटर प्रोग्राम की संरचना और व्याख्या से एक अंश है।

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

एक कारण यह है कि प्रक्रिया और प्रक्रिया के बीच भेद भ्रमित हो सकता है कि आम भाषाओं (एडा, पास्कल और सी सहित) के अधिकांश कार्यान्वयन इस तरह से डिजाइन किए गए हैं कि किसी भी पुनरावर्ती प्रक्रिया की व्याख्या से स्मृति की मात्रा कम हो जाती है प्रक्रिया कॉल की संख्या, यहां तक ​​कि जब वर्णित प्रक्रिया सिद्धांत रूप में, पुनरावृत्त है। नतीजतन, ये भाषा केवल विशेष उद्देश्य "लूपिंग संरचनाओं" जैसे कि दोहराने, दोहराने, तक, के लिए, और समय तक पहुंचकर पुनरावृत्ति प्रक्रियाओं का वर्णन कर सकती हैं। योजना का कार्यान्वयन इस दोष को साझा नहीं करता है। यह निरंतर प्रक्रिया में एक पुनरावृत्ति प्रक्रिया को निष्पादित करेगा, भले ही पुनरावृत्ति प्रक्रिया को पुनरावर्तक प्रक्रिया द्वारा वर्णित किया गया हो। इस संपत्ति के साथ एक कार्यान्वयन पूंछ-पुनरावर्ती कहा जाता है। एक पूंछ-पुनरावर्ती कार्यान्वयन के साथ, सामान्य प्रक्रिया कॉल तंत्र का उपयोग करके पुनरावृत्ति व्यक्त की जा सकती है, ताकि विशेष पुनरावृत्ति संरचना केवल सिंटैक्टिक चीनी के रूप में उपयोगी हो।


यहां दो फ़ंक्शंस की तुलना में एक त्वरित कोड स्निपेट है। पहला दिया गया नंबर के फैक्टोरियल को खोजने के लिए पारंपरिक पुनरावृत्ति है। दूसरा पूंछ रिकर्सन का उपयोग करता है।

समझने के लिए बहुत सरल और सहज ज्ञान युक्त।

यह बताने का आसान तरीका है कि एक रिकर्सिव फ़ंक्शन पूंछ रिकर्सिव है, अगर यह बेस केस में ठोस मूल्य देता है। मतलब यह है कि यह 1 या सच या उस तरह कुछ भी वापस नहीं करता है। यह संभवतः विधि पैरामीटर में से किसी एक के संस्करण को वापस कर देगा।

एक और तरीका यह बताना है कि यदि रिकर्सिव कॉल किसी भी अतिरिक्त, अंकगणित, संशोधन इत्यादि से मुक्त है ... इसका अर्थ शुद्ध रिकर्सिव कॉल के अलावा कुछ भी नहीं है।

public static int factorial(int mynumber) {
    if (mynumber == 1) {
        return 1;
    } else {            
        return mynumber * factorial(--mynumber);
    }
}

public static int tail_factorial(int mynumber, int sofar) {
    if (mynumber == 1) {
        return sofar;
    } else {
        return tail_factorial(--mynumber, sofar * mynumber);
    }
}

यहां पहले बताए गए tailrecsum फ़ंक्शन का एक पर्ल 5 संस्करण है।

sub tail_rec_sum($;$){
  my( $x,$running_total ) = (@_,0);

  return $running_total unless $x;

  @_ = ($x-1,$running_total+$x);
  goto &tail_rec_sum; # throw away current stack frame
}

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

एक पूंछ कॉल [पूंछ रिकर्सन] कॉल के रूप में पहने हुए एक प्रकार का गेटो है। एक पूंछ कॉल तब होती है जब कोई फ़ंक्शन किसी अन्य को अंतिम क्रिया के रूप में कॉल करता है, इसलिए इसमें कुछ और नहीं है। उदाहरण के लिए, निम्नलिखित कोड में, g को कॉल पूंछ कॉल है:

function f (x)
  return g(x)
end

f कॉल g बाद, इसके पास कुछ और नहीं है। ऐसी परिस्थितियों में, जब कॉल किया गया फ़ंक्शन समाप्त होता है तो प्रोग्राम को कॉलिंग फ़ंक्शन पर वापस जाने की आवश्यकता नहीं होती है। इसलिए, पूंछ कॉल के बाद, कार्यक्रम को स्टैक में कॉलिंग फ़ंक्शन के बारे में कोई जानकारी रखने की आवश्यकता नहीं है। ...

चूंकि एक उचित पूंछ कॉल कोई स्टैक स्पेस का उपयोग नहीं करती है, इसलिए "नेस्टेड" पूंछ कॉल की संख्या पर कोई सीमा नहीं है जो एक प्रोग्राम कर सकता है। उदाहरण के लिए, हम निम्नलिखित फ़ंक्शन को तर्क के रूप में किसी भी संख्या के साथ कॉल कर सकते हैं; यह ढेर कभी नहीं बह जाएगा:

function foo (n)
  if n > 0 then return foo(n - 1) end
end

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

यह गेम एक ठेठ राज्य मशीन है, जहां वर्तमान कमरा राज्य है। हम प्रत्येक कमरे के लिए एक समारोह के साथ इस तरह की भूलभुलैया लागू कर सकते हैं। हम एक कमरे से दूसरे कमरे में जाने के लिए पूंछ कॉल का उपयोग करते हैं। चार कमरे के साथ एक छोटी भूलभुलैया इस तरह दिख सकती है:

function room1 ()
  local move = io.read()
  if move == "south" then return room3()
  elseif move == "east" then return room2()
  else print("invalid move")
       return room1()   -- stay in the same room
  end
end

function room2 ()
  local move = io.read()
  if move == "south" then return room4()
  elseif move == "west" then return room1()
  else print("invalid move")
       return room2()
  end
end

function room3 ()
  local move = io.read()
  if move == "north" then return room1()
  elseif move == "east" then return room4()
  else print("invalid move")
       return room3()
  end
end

function room4 ()
  print("congratulations!")
end

तो आप देखते हैं, जब आप एक रिकर्सिव कॉल करते हैं जैसे:

function x(n)
  if n==0 then return 0
  n= n-2
  return x(n) + 1
end

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


शब्दकोष फ़ाइल में पूंछ रिकर्सन की परिभाषा के बारे में यह कहना है:

पूंछ रिकर्सन / एन /

यदि आप पहले से बीमार नहीं हैं, तो पूंछ रिकर्सन देखें।


संक्षेप में, एक पूंछ रिकर्सन में फ़ंक्शन में अंतिम कथन के रूप में रिकर्सिव कॉल होता है ताकि उसे रिकर्सिव कॉल की प्रतीक्षा न करनी पड़े।

तो यह एक पूंछ रिकर्सन अर्थात एन (एक्स -1, पी * एक्स) फ़ंक्शन में आखिरी कथन है जहां संकलक यह समझने के लिए चालाक है कि इसे फॉर-लूप (फैक्टोरियल) में अनुकूलित किया जा सकता है। दूसरा पैरामीटर पी इंटरमीडिएट उत्पाद मूल्य रखता है।

function N(x, p) {
   return x == 1 ? p : N(x - 1, p * x);
}

यह उपरोक्त फैक्टोरियल फ़ंक्शन लिखने का गैर-पूंछ-पुनरावर्ती तरीका है (हालांकि कुछ सी ++ कंपाइलर इसे किसी भी तरह अनुकूलित करने में सक्षम हो सकते हैं)।

function N(x) {
   return x == 1 ? 1 : x * N(x - 1);
}

लेकिन यह नहीं है:

function F(x) {
  if (x == 1) return 0;
  if (x == 2) return 1;
  return F(x - 1) + F(x - 2);
}

मैंने " समझने वाली टेल रिकर्सन - विजुअल स्टूडियो सी ++ - असेंबली व्यू " नामक एक लंबी पोस्ट लिखी थी


tail call recursion को समझने का सबसे अच्छा तरीका यह है: tail call recursion का एक विशेष मामला जहां अंतिम कॉल (या पूंछ कॉल) कार्य ही होता है।

पायथन में प्रदान किए गए उदाहरणों की तुलना करना:

def recsum(x):
 if x == 1:
  return x
 else:
  return x + recsum(x - 1)

^ प्रत्यावर्तन

def tailrecsum(x, running_total=0):
  if x == 0:
    return running_total
  else:
    return tailrecsum(x - 1, running_total + x)

^ टेल रिकर्सन

जैसा कि आप सामान्य रिकर्सिव संस्करण में देख सकते हैं, कोड ब्लॉक में अंतिम कॉल x + recsum(x - 1) । तो recsum विधि को कॉल करने के बाद एक और ऑपरेशन है जो x + ..

हालांकि पूंछ रिकर्सिव संस्करण में कोड ब्लॉक में अंतिम कॉल (या पूंछ कॉल) tailrecsum(x - 1, running_total + x) जिसका अर्थ है कि अंतिम कॉल विधि के लिए ही बनाई जाती है और उसके बाद कोई ऑपरेशन नहीं होता है।

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

संपादित करें

एनबी। ध्यान रखें कि ऊपर दिया गया उदाहरण पायथन में लिखा गया है जिसका रनटाइम टीसीओ का समर्थन नहीं करता है। यह बिंदु को समझाने के लिए सिर्फ एक उदाहरण है। टीसीओ स्कीम, हास्केल इत्यादि जैसी भाषाओं में समर्थित है


एक साधारण फ़ंक्शन पर विचार करें जो पहले एन पूर्णांक जोड़ता है। (उदाहरण के लिए sum(5) = 1 + 2 + 3 + 4 + 5 = 15 )।

यहां एक सरल जावास्क्रिप्ट कार्यान्वयन है जो रिकर्सन का उपयोग करता है:

function recsum(x) {
    if (x===1) {
        return x;
    } else {
        return x + recsum(x-1);
    }
}

यदि आपने recsum(5) कहा है, तो जावास्क्रिप्ट दुभाषिया का मूल्यांकन यह होगा:

recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + 1)))
15

ध्यान दें कि जावास्क्रिप्ट दुभाषिया वास्तव में राशि की गणना करने के काम को शुरू करने से पहले प्रत्येक रिकर्सिव कॉल को पूरा करना होगा।

यहां एक ही फ़ंक्शन का पूंछ-रिकर्सिव संस्करण है:

function tailrecsum(x, running_total=0) {
    if (x===0) {
        return running_total;
    } else {
        return tailrecsum(x-1, running_total+x);
    }
}

यहां घटनाओं का अनुक्रम दिया गया है जो तब होता है जब आप tailrecsum(5) , (जो कि डिफ़ॉल्ट दूसरे तर्क के कारण प्रभावी रूप से tailrecsum(5, 0) )।

tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15

पूंछ-रिकर्सिव केस में, रिकर्सिव कॉल के प्रत्येक मूल्यांकन के साथ, running_total अपडेट किया गया है।

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





tail-recursion