क्या ऐसी समस्याएं हैं जिन्हें पूंछ रिकर्सन का उपयोग करके लिखा नहीं जा सकता है?

Question

पूंछ रिकर्सन कार्यात्मक भाषाओं में एक महत्वपूर्ण प्रदर्शन अनुकूलन stragegy है क्योंकि यह निरंतर ढेर (ओ (एन) के बजाय निरंतर ढेर का उपभोग करने के लिए रिकर्सिव कॉल की अनुमति देता है।

क्या ऐसी कोई समस्या है जो केवल पूंछ-पुनरावर्ती शैली में नहीं लिखी जा सकती है, या क्या एक निष्क्रिय-पुनरावर्ती कार्य को पूंछ-पुनरावर्ती में परिवर्तित करना हमेशा संभव है?

यदि ऐसा है, तो एक दिन कार्यात्मक कंपाइलर और दुभाषिया स्वचालित रूप से रूपांतरण करने के लिए पर्याप्त बुद्धिमान हो सकते हैं?

Answer 1

हाँ, वास्तव में आप कुछ कोड लेने के लिए और और हर एक पूंछ कॉल में लौट — हर कार्य कॉल — बदल सकते हैं। आप जो खत्म करते हैं उसे निरंतरता-गुजरने वाली शैली या सीपीएस कहा जाता है।

उदाहरण के लिए, यहाँ दो पुनरावर्ती कॉल युक्त एक समारोह है:

(define (count-tree t) 
    (if (pair? t) 
    (+ (count-tree (car t)) (count-tree (cdr t))) 
    1)) 

और यहाँ अगर आप निरंतरता-गुजर शैली को यह समारोह परिवर्तित यह कैसी दिखाई देगी:

(define (count-tree-cps t ctn) 
    (if (pair? t) 
    (count-tree-cps (car t) 
        (lambda (L) (count-tree-cps (cdr t) 
               (lambda (R) (ctn (+ L R)))))) 
    (ctn 1))) 

अतिरिक्त तर्क, ctn, एक प्रक्रिया है जो पूंछ-कॉल लौटने की बजाय है। (एसडीसीवीवीसी का जवाब कहता है कि आप ओ (1) स्पेस में सबकुछ नहीं कर सकते हैं, और यह सही है; यहां प्रत्येक निरंतरता एक बंद है जो कुछ मेमोरी लेती है।)

मैंने कॉल को car पर परिवर्तित नहीं किया है या पूंछ-कॉल में cdr या +।यह भी किया जा सकता है, लेकिन मुझे लगता है कि उन पत्ते की कॉल वास्तव में रेखांकित की जाएगी।

अब मजेदार भाग के लिए। Chicken Scheme वास्तव में यह संकलन करता है जो सभी संकलन करता है। चिकन द्वारा संकलित प्रक्रियाएं कभी भी वापस नहीं आतीं। एक क्लासिक पेपर समझाता है कि चिकन योजना 1 99 4 में चिकन लागू होने से पहले क्यों लिखी गई थी: CONS should not cons its arguments, Part II: Cheney on the M.T.A.

आश्चर्यजनक रूप से पर्याप्त, निरंतरता-गुजरने वाली शैली जावास्क्रिप्ट में काफी आम है। आप ब्राउज़र की "धीमी स्क्रिप्ट" पॉपअप से परहेज करते हुए to do long-running computation का उपयोग कर सकते हैं। और यह एसिंक्रोनस एपीआई के लिए आकर्षक है। jQuery.get (XMLHttpRequest के आसपास एक साधारण रैपर) निरंतरता-गुजरने वाली शैली में स्पष्ट रूप से है; अंतिम तर्क एक समारोह है।

Answer 2

कोई पुनरावर्ती एल्गोरिदम के एक सतत एल्गोरिथ्म (शायद एक ढेर या सूची की आवश्यकता होती है) के रूप में लिखा जा सकता है और पुनरावृत्ति एल्गोरिदम हमेशा पूंछ पुनरावर्ती एल्गोरिदम के रूप में लिखा जा सकता है, तो मुझे लगता है यह सच है कि किसी भी पुनरावर्ती समाधान किसी तरह एक करने के लिए परिवर्तित किया जा सकता पूंछ-पुनरावर्ती समाधान।

(टिप्पणी में, पास्कल Cuoq बताते हैं कि किसी भी एल्गोरिथ्म continuation-passing style में बदला जा सकता है।)

ध्यान दें कि कुछ पूंछ पुनरावर्ती है सिर्फ इसलिए कि इसका मतलब यह नहीं है कि इसकी स्मृति उपयोग निरंतर है। इसका मतलब यह है कि कॉल-रिटर्न स्टैक नहीं बढ़ता है।

Answer 3

आप ओ (1) स्पेस (स्पेस पदानुक्रम प्रमेय) में सब कुछ नहीं कर सकते हैं। यदि आप पूंछ रिकर्सन का उपयोग करने पर जोर देते हैं, तो आप कॉल स्टैक को तर्कों में से एक के रूप में स्टोर कर सकते हैं। जाहिर है यह कुछ भी नहीं बदलता है; कहीं आंतरिक रूप से, एक कॉल स्टैक है, आप बस इसे स्पष्ट रूप से दृश्यमान बना रहे हैं।

यदि हां, तो एक दिन कार्यात्मक compilers और दुभाषियों के लिए पर्याप्त बुद्धिमान स्वचालित रूप से रूपांतरण करने के लिए हो सकता है?

इस तरह के रूपांतरण अंतरिक्ष जटिलता को कम नहीं करेंगे।

पास्कल कुओक ने टिप्पणी की, एक और तरीका CPS का उपयोग करना है; सभी कॉल तब पूंछ रिकर्सिव हैं।

Answer 4

मुझे नहीं लगता कि tak जैसे कुछ पूंछ कॉल का उपयोग करके लागू किया जा सकता है। (निरंतरता की अनुमति नहीं दे)

Answer 5

यह सच है लेकिन यह देखने के लिए उपयोगी नहीं है कि पारस्परिक रूप से पुनरावर्ती कार्यों के किसी संग्रह को पूंछ-पुनरावर्ती कार्य में बदल दिया जा सकता है। यह अवलोकन 1 9 60 के दशक के पुराने चेस्टनट के बराबर है कि नियंत्रण-प्रवाह संरचनाओं को समाप्त किया जा सकता है क्योंकि प्रत्येक कार्यक्रम को अंदर दिए गए केस स्टेटमेंट के साथ लूप के रूप में लिखा जा सकता है।

क्या जानना उपयोगी है कि कई फ़ंक्शन जो स्पष्ट रूप से पूंछ-पुनरावर्ती नहीं हैं, पैरामीटर संचयित करने के अलावा पूंछ-पुनरावर्ती रूप में परिवर्तित हो सकते हैं। (इस परिवर्तन का एक चरम संस्करण निरंतरता-गुजरने वाली शैली (सीपीएस) में परिवर्तन है, लेकिन अधिकांश प्रोग्रामर सीपीएस परिवर्तन को पढ़ने में मुश्किल पाते हैं।)

यहां एक फ़ंक्शन का उदाहरण है जो "रिकर्सिव" है (वास्तव में यह सिर्फ पुनरावृत्ति है), लेकिन नहीं पूंछ पुनरावर्ती:

factorial n = if n == 0 then 1 else n * factorial (n-1) 

इस मामले गुणा होता है पुनरावर्ती कॉल के बाद में। हम एक संस्करण एक जमा पैरामीटर में उत्पाद रखकर पूंछ पुनरावर्ती है कि बना सकते हैं:

factorial n = f n 1 
    where f n product = if n == 0 then product else f (n-1) (n * product) 

भीतरी समारोह f पूंछ पुनरावर्ती है और एक तंग पाश में संकलित करता है।

---

मैं उपयोगी निम्नलिखित भेद पाते हैं:

• एक सतत या पुनरावर्ती कार्यक्रम में, आप पहले सुलझाने आकार n-1 की एक subproblem द्वारा आकार n की समस्या का समाधान। फैक्टोरियल फ़ंक्शन कंप्यूटिंग इस श्रेणी में आता है, और इसे या तो क्रमशः या किया जा सकता है। (यह विचार सामान्यीकरण करता, जैसे, फाइबोनैचि समारोह, जहां तुम दोनों n-1 और n-2 जरूरत n को हल करने के लिए।)

• एक पुनरावर्ती कार्यक्रम में, आप पहली बार दो subproblems को हल करके आकार n की एक समस्या का समाधान आकार n/2। या, अधिक आम तौर पर, आप n आकार की समस्या को हल करते हैं, पहले आकार k और n-k आकार के एक उपप्रोबल को हल करके, जहां 1 < k < n।Quicksort और mergesort इस तरह की समस्या के दो उदाहरण हैं, जो आसानी से प्रोग्राम किए जा सकते हैं, लेकिन प्रोग्राम या प्रोग्रामिंग के लिए केवल इतना आसान नहीं है कि केवल पूंछ रिकर्सन का उपयोग करें। (आप अनिवार्य रूप से एक स्पष्ट ढेर का उपयोग कर प्रत्यावर्तन अनुकरण करने के लिए है।)

• गतिशील प्रोग्रामिंग, आपको पहले को हल करके आकार n की एक समस्या का समाधान सभी आकार k, जहां k<n के सभी subproblems। लंदन अंडरग्राउंड पर एक से दूसरे बिंदु पर सबसे छोटा मार्ग ढूंढना इस प्रकार की समस्या का एक उदाहरण है। (लंदन भूमिगत एक गुणा से जुड़े ग्राफ है, और आप पहले सभी बिंदुओं जिसके लिए कम से कम पथ 1 स्टॉप, तो जिसके लिए कम से कम पथ 2 स्टॉप है, आदि आदि है पता लगाकर समस्या का समाधान )

केवल पहले प्रकार के कार्यक्रम में सरल पूंछ-पुनरावर्ती रूप में परिवर्तन है।