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

Question

मैंने एक एल्गोरिदमिक पुस्तक में पढ़ा है कि एकरमेन फ़ंक्शन को पूंछ-रिकर्सिव नहीं बनाया जा सकता है (वे क्या कहते हैं "इसे पुनरावृत्ति में परिवर्तित नहीं किया जा सकता")। मैं बहुत इस बारे में उलझाना कर रहा हूँ, इसलिए मैं करने की कोशिश की और इस के साथ आते हैं:

let Ackb m n = 
    let rec rAck cont m n = 
    match (m, n) with 
     | 0, n -> cont (n+1) 
     | m, 0 -> rAck cont (m-1) 1 
     | m, n -> rAck (fun x -> rAck cont (m-1) x) m (n-1) 
    in rAck (fun x -> x) m n 
;; 

(यह OCaml/एफ # कोड है)।

मेरी समस्या यह है कि, मुझे यकीन नहीं है कि यह वास्तव में पूंछ रिकर्सिव है। क्या आप पुष्टि कर सकते हैं कि यह है? यदि नहीं, क्यों? और आखिरकार, इसका मतलब क्या है जब लोग कहते हैं कि एकरमेन फ़ंक्शन आदिम रिकर्सिव नहीं है?

धन्यवाद!

Answer 1

हां, यह पूंछ-पुनरावर्ती है। प्रत्येक समारोह को Continuation Passing Style पर एक स्पष्ट परिवर्तन द्वारा पूंछ-आरईसी बनाया जा सकता है।

इसका मतलब यह नहीं है कि फ़ंक्शन निरंतर स्मृति में निष्पादित होगा: आप निरंतरता के ढेर का निर्माण करते हैं जिन्हें आवंटित किया जाना चाहिए। यह defunctionalize के लिए एक सरल बीजगणितीय डेटाटाइप के रूप में उस डेटा का प्रतिनिधित्व करने के लिए निरंतरता हो सकता है।

primitive recursive होने के नाते गणितीय सिद्धांत में उपयोग की जाने वाली पुनरावर्ती परिभाषा के एक निश्चित रूप की अभिव्यक्ति से संबंधित एक बहुत ही अलग धारणा है, लेकिन शायद कंप्यूटर विज्ञान के लिए बहुत प्रासंगिक नहीं है जैसा कि आप जानते हैं: वे बहुत कम अभिव्यक्तिशील हैं, और फ़ंक्शन संरचना के साथ सिस्टम (गोडेल सिस्टम टी के साथ शुरू), जैसे कि सभी मौजूदा प्रोग्रामिंग भाषाएं, अधिक शक्तिशाली हैं।

कंप्यूटर भाषाओं की अवधि में, प्राइमेटिव रिकर्सिव फ़ंक्शन लगभग सामान्य रिकर्सन के बिना प्रोग्राम के अनुरूप होते हैं जहां सभी लूप/पुनरावृत्तियों को स्थिर रूप से बाध्य किया जाता है (संभावित पुनरावृत्ति की संख्या ज्ञात है)।

Answer 2

हां।

परिभाषा के अनुसार, किसी भी पुनरावर्ती समारोह के रूप में लंबे समय से यह एक असीम ढेर की तरह निर्माण की पहुंच है के रूप में एक यात्रा में तब्दील किया जा सकता है। दिलचस्प सवाल यह है कि क्या इसे स्टैक या किसी अन्य असंबद्ध डेटा स्टोरेज के बिना किया जा सकता है।

एक पूंछ-पुनरावर्ती कार्य को केवल इस तरह के पुनरावृत्ति में बदला जा सकता है यदि उसके तर्कों का आकार बाध्य है। आपके उदाहरण में (और लगभग किसी भी पुनरावर्ती कार्य जो निरंतरता का उपयोग करता है), cont पैरामीटर सभी साधनों और प्रयोजनों के लिए एक ढेर है जो किसी भी आकार में बढ़ सकता है। दरअसल, निरंतरता-गुजरने वाली शैली का पूरा बिंदु आमतौर पर कॉल स्टैक ("लौटने के बाद क्या करना है?") पर मौजूद डेटा को स्टोर करना है, इसके बजाय निरंतरता पैरामीटर में।