दिलचस्प पोस्ट
AngularJS त्रुटि: क्रॉस मूल अनुरोध केवल प्रोटोकॉल योजनाओं के लिए समर्थित हैं: http, डेटा, क्रोम-एक्सटेंशन, https कैसे MVVM में एक PasswordBox के साथ बाध्य करने के लिए जांचें कि पायथन में क्या फ़ाइलें खुली हैं Windows 8.1 पर विंडोज 10 यूनिवर्सल एप्प्स चलाएं मैं स्विफ्ट में NSTimer का उपयोग कैसे कर सकता हूं? डोमोनोड के आंतरिक एचटीएमएल कैसे प्राप्त करें? पुनर्निर्माण और स्वच्छ के बीच अंतर + दृश्य स्टूडियो में बिल्ड अपलोड की गई छवियों, एसक्यूएल डाटाबेस या डिस्क फाइल सिस्टम को स्टोर करने के लिए सबसे अच्छी जगह क्या है? अपना कस्टम एडैप्टर बनाने के दौरान getView () विधि कैसे काम करती है? टेम्पलेट्स में कीवर्ड 'टाइपनाम' और 'क्लास' का अंतर? नियमित अभिव्यक्ति का उपयोग करते हुए एक बड़ी स्ट्रिंग के उपस्ट्रिंग को खोजने के लिए जावा का उपयोग करना डीपी के मामले में स्क्रीन चौड़ाई कैसे निर्धारित करें या एंड्रॉइड में रनटाइम पर डुबकी? अजाक्स के साथ एमवीसी 4 का उपयोग करते हुए फ़ाइल अपलोड करें Sys.stdin के लिए छोटा बफर आकार सेट करना? मैं सीएसएस में माता-पिता से बच्चे की अस्पष्टता को विरासत में नहीं देना चाहता

पूंछ पुनर्कलन क्या है?

हालांकि, लिस्प को सीखना शुरू करने के बाद, मैं पूंछ-पुनरावर्ती अवधि में आया हूं। यह वास्तव में क्या मतलब है?

वेब के समाधान से एकत्रित समाधान "पूंछ पुनर्कलन क्या है?"

एक साधारण कार्य पर विचार करें जो पहले एन पूर्णांक जोड़ता है (जैसे 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) हैं तो ये घटित होने वाली घटनाओं का अनुक्रम होता है, (जो डिफ़ॉल्ट रूप से दूसरी तर्क के कारण प्रभावी रूप से tailrecsum(5, 0) )।

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

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

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

परंपरागत पुनरावृत्ति में , विशिष्ट मॉडल यह है कि आप पहले अपने रिकर्सिव कॉल करते हैं, और फिर आप रिकर्सिव कॉल के रिटर्न मान लेते हैं और परिणाम की गणना करते हैं। इस तरीके से, आप अपने गणना का परिणाम तब तक नहीं प्राप्त करते जब तक आप प्रत्येक रिकर्सिव कॉल से वापस नहीं लौटाते।

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

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

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

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

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

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

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

इसे शब्दों के साथ समझाए जाने के बजाय, यहां एक उदाहरण है। यह तथ्यात्मक कार्य का एक योजना संस्करण है:

 (define (factorial x) (if (= x 0) 1 (* x (factorial (- x 1))))) 

यहां एक तथ्य है जो पूंछ-पुनरावर्ती है:

 (define factorial (letrec ((fact (lambda (x accum) (if (= x 0) accum (fact (- x 1) (* accum x)))))) (lambda (x) (fact x 1)))) 

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

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

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

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

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

पूंछ पुनरावर्ती / एन। /

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

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

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

टेल रिकर्सन, रिकर्सिव एल्गोरिथम में अंतिम लॉजिक अनुदेश में अंतिम रूप से रिकर्सिव कॉल को संदर्भित करता है।

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

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

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

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

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

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

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

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

यहाँ पहले उल्लेख किया गया 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 } 

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

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

पूंछ-कॉल पुनर्रचना और गैर पूंछ-कॉल पुनर्रचना के बीच के कुछ मुख्य अंतरों को समझने के लिए हम इन तकनीकों के एनएटी लागूकरण का पता लगा सकते हैं।

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

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

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

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

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

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

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

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

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

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

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

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

यहां छवि विवरण दर्ज करें

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

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

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

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

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

पुनरुत्थान का मतलब है एक फंक्शन को स्वयं बुला रहा है उदाहरण के लिए:

 (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))) 

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

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

tail call recursion समझने के लिए सबसे अच्छा तरीका है: एक विशेष मामले 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) जिसका मतलब है कि आखिरी कॉल विधि को ही बनायी जाती है और उसके बाद कोई ऑपरेशन नहीं होता है।

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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