क्या कोई समस्या है जिसमें केवल एक पुनरावर्ती समाधान है?

Question

संभावित डुप्लिकेट:
Is there a problem that has only a recursive solution?
Can every recursion be converted into iteration?
“Necessary” Uses of Recursion in Imperative Languages

वहाँ एक समस्या केवल एक पुनरावर्ती समाधान, वह है, एक समस्या एक पुनरावर्ती समाधान है, लेकिन एक सतत समाधान है कि है अभी तक पाया गया है, या बेहतर अभी तक, अस्तित्व में साबित हुआ है (जाहिर है, यह एक पूंछ-रिकर्सन नहीं है)?

Answer 1

Ackermann function प्रत्यावर्तन

Answer 2

सभी गैर एनपी-पूर्ण समस्याओं को केवल अनुक्रम, निर्णय और पुनरावृत्ति के साथ हल किया जा सकता है। रिकर्सन की आवश्यकता नहीं होनी चाहिए, हालांकि यह आमतौर पर समस्या को बहुत सरल बनाता है।

Answer 3

फ़ंक्शन कॉल को स्टैक पर धक्का देने के साथ प्रतिस्थापित करता है, और स्टैक को पॉप-अप करने के साथ लौटाता है, और आपने रिकर्सन को समाप्त कर दिया है।

संपादित करें: प्रतिक्रिया पुनरावर्ती एल्गोरिदम लगातार अंतरिक्ष में दिखाया जा सकता है "एक ढेर का उपयोग कर अंतरिक्ष की लागत में कमी नहीं करता" करने के लिए

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

भाज्य:

def fact_rec(n): 
    ' Textbook Factorial function ' 
    if n < 2: return 1 
    else:  return n * f(n-1) 


def f(n, product=1): 
    ' Tail-recursive factorial function ' 
    if n < 2: return product 
    else:  return f(n-1, product*n) 

def f(n): 
    ' explicit stack -- otherwise same as tail-recursive function ' 
    stack, product = [n], 1 
    while len(stack): 
     n = stack.pop() 
     if n < 2: pass 
     else: 
      stack.append(n-1) 
      product *= n 
    return product 

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

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

Answer 4

यह कितने कोड की लाइनें यह समस्या को हल करने के लिए ले जा रहा है करने के लिए नीचे आता है ...

सूची सभी अपने सी पर फ़ाइलें: \ बिना प्रत्यावर्तन और उसके बाद का उपयोग कर। निश्चित रूप से आप इसे दोनों तरीकों से कर सकते हैं - लेकिन एक तरीका समझने और डीबग करने के लिए बहुत आसान होगा।

Answer 5

नहीं। रिकर्सन स्टैक से अधिक कुछ नहीं है और आप स्पष्ट रूप से एक ढेर को लागू करके एक ही परिणाम प्राप्त कर सकते हैं।

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

मैंने वहां "पारंपरिक" रखा क्योंकि वे वास्तव में उन लूपों का मतलब करते हैं जो एक निश्चित संख्या को फिर से सक्रिय करते हैं जबकि सी शैली (...; ...; ...) लूप छिपाने में लूप होते हैं।

Answer 6

प्रोग्रामिंग में, रिकर्सन वास्तव में पुनरावृत्ति का एक विशेष मामला है - एक जहां आप कॉल स्टैक का उपयोग राज्य के भंडारण के विशेष साधन के रूप में करते हैं।आप किसी भी पुनरावर्ती विधि को पुनरावृत्त करने के लिए पुनः लिख सकते हैं। यह अधिक जटिल या कम सुरुचिपूर्ण हो सकता है, लेकिन यह बराबर है। कुछ उदाहरण हैं खोजने जड़ों (Newton's Method), कंप्यूटिंग अभाज्य संख्या, ग्राफ अनुकूलन, आदि हालांकि, यहां भी, वहाँ का सवाल है -

गणित में, वहाँ कुछ समस्याओं कि एक जवाब पर पहुंचने के लिए पुनरावर्ती तकनीक की आवश्यकता होती हैं आप "पुनरावृत्ति" और "रिकर्सन" शब्दों के बीच अंतर कैसे करते हैं।

संपादित करें: जैसा कि अन्य ने बताया है, वहां कई कार्य मौजूद हैं जिनकी परिभाषा रिकर्सिव है - पूर्व। Ackermann function। हालांकि, इसका मतलब यह नहीं है कि उन्हें पुनरावृत्त संरचनाओं का उपयोग करके गणना नहीं की जा सकती है - जब तक आपके पास ट्यूरिंग पूर्ण ऑपरेशन सेट और असीमित स्मृति हो।

Answer 7

बिना व्यक्त नहीं किया जा सकता आप प्रत्यावर्तन के बिना एक Turing Machine परिभाषित कर सकते हैं (है ना?) तो प्रत्यावर्तन एक भाषा Turing-complete होने के लिए आवश्यक नहीं है।

Answer 8

Ackermann function answer के जवाब में, यह एक बहुत सीधी कन्वर्ट-द-कॉल-स्टैक-इन-ए-रीयल-स्टैक समस्या है। यह पुनरावृत्त संस्करण का एक लाभ भी दिखाता है।

मेरे प्लेटफ़ॉर्म (पायथन 3.1 आरसी 2/Vista32) पर पुनरावृत्त संस्करण एके (3,7) = 1021 ठीक की गणना करता है, जबकि रिकर्सिव संस्करण स्टैक ओवरफ्लो। एनबी: यह एक अलग मशीन पर पायथन 2.6.2/Vista64 पर स्टैक ओवरफ्लो नहीं था, इसलिए यह प्लेटफार्म-निर्भर,

(सामुदायिक विकी क्योंकि यह वास्तव में किसी अन्य उत्तर पर टिप्पणी है [अगर केवल टिप्पणियां समर्थित हैं कोड स्वरूपण ....])

def ack(m,n): 
    s = [m] 
    while len(s): 
    m = s.pop() 
    if m == 0: 
     n += 1 
    elif n == 0: 
     s.append(m-1) 
     n = 1 
    else: 
     s.append(m-1) 
     s.append(m) 
     n -= 1 
    return n