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




language-agnostic functional-programming recursion tail-recursion (19)

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


Answers

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

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

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


एक साधारण फ़ंक्शन पर विचार करें जो पहले एन पूर्णांक जोड़ता है। (उदाहरण के लिए 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 अपडेट किया गया है।

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


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

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

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


इसका मतलब है कि स्टैक पर निर्देश पॉइंटर को धक्का देने की आवश्यकता के बजाय, आप बस रिकर्सिव फ़ंक्शन के शीर्ष पर जा सकते हैं और निष्पादन जारी रख सकते हैं। यह कार्यों को ढेर बहने के बिना अनिश्चित काल तक पुनर्जीवित करने की अनुमति देता है।

मैंने इस विषय पर एक blog पोस्ट लिखा है, जिसमें स्टैक फ्रेम की तरह दिखने के ग्राफिकल उदाहरण हैं।


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

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

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

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


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

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


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

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);
}

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

  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

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


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

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

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


पूंछ-कॉल रिकर्सन और गैर पूंछ-कॉल रिकर्सन के बीच कुछ मूल मतभेदों को समझने के लिए हम इन तकनीकों के .NET कार्यान्वयन का पता लगा सकते हैं।

सी #, एफ #, और सी ++ \ सीएलआई में कुछ उदाहरणों के साथ एक लेख यहां दिया गया है: सी #, एफ #, और सी ++ \ सीएलआई में टेल रिकर्सन में एडवेंचर्स

सी # पूंछ कॉल रिकर्सन के लिए अनुकूल नहीं है जबकि एफ # करता है।

सिद्धांत के मतभेद लूप बनाम लैम्ब्डा कैलकुस शामिल हैं। सी # दिमाग में दिमाग के साथ बनाया गया है जबकि एफ # लैम्ब्डा कैलकुस के सिद्धांतों से बनाया गया है। लैम्ब्डा कैलकुस के सिद्धांतों पर एक बहुत अच्छी (और मुक्त) पुस्तक के लिए, देखें: एबेलसन, सुस्मान और सुस्मान द्वारा कंप्यूटर प्रोग्राम की संरचना और व्याख्या

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

यदि आप सी # और एफ # के बीच पूंछ-कॉल रिकर्सन के कुछ डिज़ाइन अंतरों के बारे में पढ़ना चाहते हैं, तो देखें: सी # और एफ # में टेल-कॉल ऑपोड जेनरेट करना

यदि आप यह जानना चाहते हैं कि सी # कंपाइलर पूंछ-कॉल अनुकूलन करने से कौन सी स्थितियों को रोकता है, तो यह आलेख देखें: जेआईटी सीएलआर पूंछ-कॉल की स्थिति


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

जब आप मानते हैं कि कुछ प्रक्रियाएं अतिरिक्त फ्रेम का उपयोग कर सकती हैं तो समानता टूट जाती है, लेकिन स्टैक को असीम रूप से विकसित नहीं होने पर अभी भी पूंछ-पुनरावर्ती माना जाता है।


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

तो यह एक पूंछ रिकर्सन अर्थात एन (एक्स -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);
}

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


यहां पहले बताए गए 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
}

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

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

यह बताने का आसान तरीका है कि एक रिकर्सिव फ़ंक्शन पूंछ रिकर्सिव है, अगर यह बेस केस में ठोस मूल्य देता है। मतलब यह है कि यह 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);
    }
}

रिकर्सन का अर्थ है एक फ़ंक्शन स्वयं को कॉल करना। उदाहरण के लिए:

(define (un-ended name)
  (un-ended 'me)
  (print "How can I get here?"))

पूंछ-रिकर्सन का मतलब है कि समारोह का निष्कर्ष निकालना:

(define (un-ended name)
  (print "hello")
  (un-ended 'me))

देखें, आखिरी चीज अन-एंड फ़ंक्शन (स्कीम शब्दकोष में प्रक्रिया) स्वयं को कॉल करना है। एक और (अधिक उपयोगी) उदाहरण है:

(define (map lst op)
  (define (helper done left)
    (if (nil? left)
        done
        (helper (cons (op (car left))
                      done)
                (cdr left))))
  (reverse (helper '() lst)))

सहायक प्रक्रिया में, आखिरी चीज जो बायीं तरफ है वह शून्य नहीं है (खुद को कुछ और सीडीआर के बाद) कॉल करना है। यह मूल रूप से आप एक सूची को कैसे मैप करते हैं।

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


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

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);
}

यहां एक सामान्य लिस्प उदाहरण है जो पूंछ-रिकर्सन का उपयोग करके फैक्टोरियल करता है। ढेर-कम प्रकृति के कारण, कोई बेहद बड़े फैक्टोरियल कंप्यूटेशंस कर सकता है ...

(defun ! (n &optional (product 1))
    (if (zerop n) product
        (! (1- n) (* product n))))

और फिर मस्ती के लिए आप कोशिश कर सकते हैं (format nil "~R" (! 25))


मान लें कि हैरी पॉटर ऑर्डर करें: अमेज़ॅन से 8-फिल्म संग्रह [ब्लू-रे] पूर्ण करें और एक ही समय में एक ही फिल्म संग्रह ऑनलाइन डाउनलोड करें। आप जांचना चाहते हैं कि कौन सी विधि तेज है। डिलीवरी आने के लिए लगभग एक दिन लगती है और डाउनलोड लगभग 30 मिनट पहले पूरा हो जाता है। महान! तो यह एक तंग दौड़ है।

क्या होगा यदि मैं कई ब्लू-रे फिल्मों जैसे द लॉर्ड ऑफ द रिंग्स, ट्वाइलाइट, द डार्क नाइट त्रयी आदि का ऑर्डर करता हूं और एक ही समय में सभी फिल्में ऑनलाइन डाउनलोड करता हूं? इस बार, डिलीवरी अभी भी पूरा होने में एक दिन लगती है, लेकिन ऑनलाइन डाउनलोड को समाप्त होने में 3 दिन लगते हैं। ऑनलाइन खरीदारी के लिए, खरीदे गए आइटम (इनपुट) की संख्या प्रसव के समय को प्रभावित नहीं करती है। आउटपुट स्थिर है। हम इसे ओ (1) कहते हैं

ऑनलाइन डाउनलोड करने के लिए, डाउनलोड समय मूवी फ़ाइल आकार (इनपुट) के लिए सीधे आनुपातिक है। हम इसे ओ (एन) कहते हैं

प्रयोगों से, हम जानते हैं कि ऑनलाइन शॉपिंग स्केल ऑनलाइन डाउनलोड से बेहतर है। बड़े ओ नोटेशन को समझना बहुत महत्वपूर्ण है क्योंकि यह आपको एल्गोरिदम की स्केलेबिलिटी और दक्षता का विश्लेषण करने में मदद करता है।

नोट: बिग ओ नोटेशन एल्गोरिदम के सबसे खराब-केस परिदृश्य का प्रतिनिधित्व करता है। आइए मान लें कि ओ (1) और ओ (एन) ऊपर दिए गए उदाहरण के सबसे बुरे मामले परिदृश्य हैं।

संदर्भ : http://carlcheo.com/compsci







algorithm language-agnostic functional-programming recursion tail-recursion