2009-11-11 20 views
11

मैं वर्तमान में साइमन थॉम्पसन के The Craft of Functional Programming पढ़ रहा हूं और रिकर्सन का वर्णन करते समय, उन्होंने आदिम रिकर्सन नामक रिकर्सन का एक रूप भी उल्लेख किया है।आदिम रिकर्सन "सामान्य" रिकर्सन से कैसे भिन्न होता है?

आप कृपया समझा सकते हैं कि कैसे प्रत्यावर्तन के इस प्रकार "सामान्य" पुनरावर्ती कार्यों से अलग है?

यहाँ (हास्केल में) एक आदिम प्रत्यावर्तन समारोह का एक उदाहरण है:

power2 n 
    | n == 0 = 1 
    | n > 0  = 2 * power2(n - 1) 

उत्तर

8

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

data Nat 
    = Zero 
    | Succ Nat -- Succ is short for 'successor of', i.e. n+1 

इसका मतलब है आप इस तरह उन पर recurse कर सकते हैं:

power2 Zero = Succ Zero -- (Succ 0) == 1 
power2 (Succ n) = 2 * power2 n -- this is allowed because (*) is primitive recursive as well 

आदिम पुनरावर्ती कार्यों की संरचना:

f Zero  = ... 
f (Succ n) = ... 

हम के रूप में अपने उदाहरण लिख सकते हैं आदिम पुनरावर्ती भी है।

fib    Zero = Zero 
fib   (Succ Zero) = (Succ Zero) 
fib (Succ [email protected](Succ n' )) = fib n + fib n' -- addition is primitive recursive 
-3
+0

... बहुत उपयोगी-_- –

+2

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

+5

ओपी यहां कुछ सीखने की कोशिश कर रहा है। यदि आप गणित शिक्षक थे तो क्या आप अपने छात्रों को विश्वकोष में देखेंगे? –

7

आदिम पुनरावर्ती कार्यों एक (गणितज्ञ के) हॉल्टिंग समस्या के लिए स्वाभाविक प्रतिक्रिया कर रहे हैं, के लिए बिजली दूर अलग करना द्वारा मनमाने ढंग से unbounded आत्म recursion करते हैं।

एक "" बुराई समारोह

f n 
    | n is an odd perfect number = true 
    | otherwise = f n+2 

च समाप्त करता है पर विचार करें? आप अजीब सही संख्याओं की खुली समस्या को हल किए बिना नहीं जान सकते हैं। यह ऐसे कार्यों को बनाने की क्षमता है जो रोकथाम की समस्या को कठिन बनाते हैं।

निर्माण के रूप में आदिम रिकर्सन आपको ऐसा करने नहीं देता है; बिंदु "एफ एन + 2" चीज़ को प्रतिबंधित करना है, जबकि अभी भी जितना संभव हो उतना लचीला शेष है - आप एफ (एन + 1) के संदर्भ में एफ (एन) को प्राथमिक रूप से परिभाषित नहीं कर सकते हैं।

ध्यान दें कि सिर्फ इसलिए कि फ़ंक्शन आदिम रिकर्सिव नहीं है इसका मतलब यह नहीं है कि यह समाप्त नहीं होता है; एकरमेन का कार्य कैननिकल उदाहरण है।

+0

और इसलिए, अच्छी तरह से स्थापित रिकर्सन और आदिम रिकर्सन के बीच क्या अंतर है? – Hibou57

2

पुनरावर्ती कार्यों है कि केवल कर से लागू किया जा सकता छोरों आदिम पुनरावर्ती कार्य हैं:

एक और उदाहरण फाइबोनैचि संख्या है।

+1

बस एफवाईआई (आपकी दूसरी पोस्ट के आधार पर, यह नहीं), आप http://careers.stackoverflow.com/ –

+0

पर एक सीवी पोस्ट कर सकते हैं लूप चर के साथ लूप्स कड़ाई से घटते हैं। – ARi

संबंधित मुद्दे