प्रत्यावर्तन क्या है और जब मैं इसे इस्तेमाल करना चाहिए?

वोट
121

जिन विषयों के मेलिंग सूचियों और ऑनलाइन चर्चा पर नियमित रूप से आने के लिए लगता है में से एक कंप्यूटर विज्ञान की डिग्री कर की खूबियों (या अभाव क्या है)। एक तर्क यह है कि नकारात्मक पार्टी के लिए फिर से समय और आने के लिए लगता है कि वे साल के कुछ नंबर के लिए कोडिंग किया गया है और वे प्रत्यावर्तन कभी उपयोग नहीं किया है।

तो सवाल यह है:

  1. प्रत्यावर्तन क्या है?
  2. जब मैं प्रत्यावर्तन का प्रयोग करेंगे?
  3. क्यों लोगों प्रत्यावर्तन का उपयोग नहीं करते?
06/08/2008 को 03:29
का स्रोत उपयोगकर्ता
अन्य भाषाओं में...                            


40 जवाब

वोट
86

का अच्छा स्पष्टीकरण की एक संख्या हैं प्रत्यावर्तन इस सूत्र में, इस सवाल का जवाब (तुम क्यों यह सबसे अधिक भाषाओं में उपयोग नहीं करना चाहिए के बारे में है। * प्रमुख अनिवार्य भाषा कार्यान्वयन के बहुमत में यानी सी, सी ++, बेसिक, अजगर के हर प्रमुख कार्यान्वयन , रूबी, जावा, और सी #) यात्रा बेहद प्रत्यावर्तन करना बेहतर है।

क्यों देखने के लिए, चरणों के बारे में है कि ऊपर भाषाओं में एक समारोह कॉल करने के लिए उपयोग करें:

  1. अंतरिक्ष पर बना ली है ढेर समारोह के तर्कों और स्थानीय चर के लिए
  2. समारोह के तर्कों इस नए अंतरिक्ष में कॉपी कर रहे हैं
  3. नियंत्रण कार्य करने के लिए कूदता है
  4. समारोह के कोड रन
  5. समारोह के परिणाम एक वापसी मान में बनाई जाए
  6. ढेर अपने पिछले स्थिति के लिए rewound है
  7. नियंत्रण जहां समारोह बुलाया गया था वापस करने के लिए कूदता है

इन सभी चरणों को करने से समय लगता है, आमतौर पर थोड़ा और अधिक की तुलना में यह एक पाश के माध्यम से पुनरावृति करने के लिए ले जाता है। हालांकि, वास्तविक समस्या चरण # 1 में है। जब कई कार्यक्रमों शुरू करते हैं, वे अपने ढेर के लिए स्मृति का एक भी हिस्सा आवंटित है, और जब वे कहते हैं कि स्मृति से बाहर चलाने (अक्सर, लेकिन हमेशा नहीं प्रत्यावर्तन के कारण), कार्यक्रम एक की वजह से दुर्घटनाओं ढेर अतिप्रवाह

तो इन भाषाओं में प्रत्यावर्तन धीमी है और यह आपको दुर्घटनाग्रस्त की चपेट में आता है। अभी भी हालांकि यह प्रयोग करने के लिए कुछ तर्क हैं। सामान्य तौर पर, रिकर्सिवली लिखे कोड छोटे और थोड़ा और अधिक सुरुचिपूर्ण एक बार तुम्हें पता है कि यह कैसे को पढ़ने के लिए है।

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

* मैं प्रत्यावर्तन प्यार करता हूँ। मेरा पसंदीदा स्थिर भाषा बिल्कुल छोरों का उपयोग नहीं करता, प्रत्यावर्तन कुछ बार-बार ऐसा करने के लिए एक ही रास्ता है। मुझे नहीं लगता कि प्रत्यावर्तन आम तौर पर भाषा है कि यह के लिए देखते नहीं कर रहे हैं में एक अच्छा विचार है।

** जिस तरह से मारियो से, आपके ArrangeString समारोह के लिए विशिष्ट नाम "में शामिल होने" है, और मैं अगर पसंद की अपनी भाषा को पहले से ही इसके बारे में एक कार्यान्वयन नहीं है आश्चर्य होगा।

06/08/2008 को 06:09
का स्रोत उपयोगकर्ता

वोट
63

प्रत्यावर्तन की सरल अंग्रेज़ी उदाहरण।

A child couldn't sleep, so her mother told her a story about a little frog,
    who couldn't sleep, so the frog's mother told her a story about a little bear,
         who couldn't sleep, so the bear's mother told her a story about a little weasel... 
            who fell asleep.
         ...and the little bear fell asleep;
    ...and the little frog fell asleep;
...and the child fell asleep.
04/05/2010 को 17:38
का स्रोत उपयोगकर्ता

वोट
49

सबसे बुनियादी कंप्यूटर विज्ञान अर्थ में, प्रत्यावर्तन एक समारोह है जो अपने आप कॉल है। आप एक लिंक्ड सूची संरचना है कहते हैं:

struct Node {
    Node* next;
};

और अगर आप पता लगाने के लिए कितनी देर तक एक लिंक्ड सूची आप प्रत्यावर्तन साथ ऐसा कर सकते है हैं:

int length(const Node* list) {
    if (!list->next) {
        return 1;
    } else {
        return 1 + length(list->next);
    }
}

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

04/05/2010 को 12:25
का स्रोत उपयोगकर्ता

वोट
46

जब भी एक समारोह में ही कहता है, एक पाश बनाने, तो उस प्रत्यावर्तन है। कुछ भी साथ के रूप में वहाँ अच्छा उपयोग करता है और प्रत्यावर्तन के लिए बुरा उपयोग हैं।

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

int FloorByTen(int num)
{
    if (num % 10 == 0)
        return num;
    else
        return FloorByTen(num-1);
}

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

तो पूरी कारण प्रत्यावर्तन करने के लिए नहीं बल्कि यात्रा से का लाभ लेने के होना चाहिए कॉल स्टैक कुछ चालाक सामान करना है। उदाहरण के लिए, यदि आप एक ही पाश अंदर विभिन्न मापदंडों के साथ एक समारोह में कई बार फोन तो है कि पूरा करने के लिए एक रास्ता है शाखाओं में । एक क्लासिक उदाहरण है सिएरपिन्स्की त्रिकोण

यहाँ छवि विवरण दर्ज

तुम बहुत बस प्रत्यावर्तन, के साथ उन लोगों में से एक आकर्षित कर सकते हैं जहां 3 दिशाओं में कॉल स्टैक शाखाओं:

private void BuildVertices(double x, double y, double len)
{
    if (len > 0.002)
    {
        mesh.Positions.Add(new Point3D(x, y + len, -len));
        mesh.Positions.Add(new Point3D(x - len, y - len, -len));
        mesh.Positions.Add(new Point3D(x + len, y - len, -len));
        len *= 0.5;
        BuildVertices(x, y + len, len);
        BuildVertices(x - len, y - len, len);
        BuildVertices(x + len, y - len, len);
    }
}

आप यात्रा के साथ एक ही बात करने के लिए प्रयास करते हैं मुझे लगता है कि आप मिल जाएगा यह पूरा करने के लिए एक बहुत अधिक कोड लेता है।

अन्य सामान्य उपयोग के मामलों traversing पदानुक्रम, जैसे वेबसाइट क्रॉलर्स, निर्देशिका तुलना, आदि शामिल हो सकता है

निष्कर्ष

व्यावहारिक दृष्टि से, प्रत्यावर्तन सबसे अधिक उपयुक्त है जब भी आप पुनरावृत्ति शाखाओं की जरूरत है बनाता है।

04/05/2010 को 14:33
का स्रोत उपयोगकर्ता

वोट
28

प्रत्यावर्तन फूट डालो और जीत मानसिकता के आधार पर समस्याओं को हल करने का एक तरीका है। मूल विचार यह है कि आप मूल समस्या लेने के लिए और इसे छोटे (अधिक आसानी से हल) खुद के उदाहरण में विभाजित, उन छोटे उदाहरणों का समाधान (आमतौर पर एक ही एल्गोरिथ्म फिर से का उपयोग करके) और फिर उन्हें अंतिम समाधान में पुनः है।

विहित उदाहरण एक नियमित n के क्रमगुणित उत्पन्न करने के लिए है। n के क्रमगुणित 1 और एन के बीच संख्या के सभी गुणा किया जाता है। सी # में एक सतत समाधान इस तरह दिखता है:

public int Fact(int n)
{
  int fact = 1;

  for( int i = 2; i <= n; i++)
  {
    fact = fact * i;
  }

  return fact;
}

वहाँ पुनरावृत्ति समाधान के बारे में आश्चर्य की बात कुछ भी नहीं है और यह किसी के साथ सी # परिचित करने के लिए अर्थपूर्ण होनी चाहिए।

पुनरावर्ती समाधान मान्यता है कि वें क्रमगुणित n * तथ्य है द्वारा पाया जाता है (n-1)। या दूसरे शब्दों में कहें, यदि आप जानते हैं कि एक विशेष भाज्य संख्या आप अगले एक की गणना कर सकते है। यहाँ सी # में पुनरावर्ती समाधान है:

public int FactRec(int n)
{
  if( n < 2 )
  {
    return 1;
  }

  return n * FactRec( n - 1 );
}

इस समारोह के पहले भाग एक के रूप में जाना जाता है बेस प्रकरण (या कभी कभी गार्ड खण्ड) और क्या हमेशा के लिए चलने से एल्गोरिथ्म को रोकता है। यह सिर्फ मान 1 जब भी समारोह 1 या उससे कम की एक मूल्य के साथ कहा जाता है देता है। दूसरे भाग को और अधिक रोचक है और कहा जाता है रिकर्सिव चरण । यहाँ हम एक थोड़ा संशोधित पैरामीटर (हम 1 से यह घटती) के साथ एक ही विधि कॉल और फिर n के हमारे प्रति के साथ परिणाम गुणा।

जब पहली बार सामना करना पड़ा इस भ्रामक तरह का तो यह जांच करने के लिए शिक्षाप्रद है कि यह कैसे काम करता है जब रन हो सकता है। कल्पना कीजिए कि हम FactRec फोन (5)। हम नियमित दर्ज करते हैं, आधार मामला द्वारा उठाया नहीं कर रहे हैं और इसलिए हम इस तरह अंत:

// In FactRec(5)
return 5 * FactRec( 5 - 1 );

// which is
return 5 * FactRec(4);

अगर हम पैरामीटर 4 हम फिर से गार्ड खंड द्वारा बंद कर दिया नहीं कर रहे हैं और इसलिए हम पर अंत के साथ विधि दोबारा डालनी:

// In FactRec(4)
return 4 * FactRec(3);

हम वापसी मान में इस वापसी मान स्थानापन्न यदि उपरोक्त पर हम पाते हैं

// In FactRec(5)
return 5 * (4 * FactRec(3));

यह आप कैसे अंतिम समाधान तो पर पहुंचे है कि हम तेजी से ट्रैक और नीचे रास्ते पर हर कदम दिखाता हूँ के रूप में एक सुराग देना चाहिए:

return 5 * (4 * FactRec(3));
return 5 * (4 * (3 * FactRec(2)));
return 5 * (4 * (3 * (2 * FactRec(1))));
return 5 * (4 * (3 * (2 * (1))));

यही कारण है कि अंतिम प्रतिस्थापन होता है जब आधार मामला शुरू हो रहा है। इस बिंदु पर हम हल करने के लिए जो पहली जगह में factorials की परिभाषा के लिए सीधे बराबर एक सरल algrebraic सूत्र है।

यह ध्यान रखें कि या तो एक आधार के मामले में विधि परिणामों में हर कॉल ट्रिगर हो रहा है या एक ही तरीका है, जहां मानकों एक आधार मामले के करीब हैं के लिए एक कॉल (अक्सर एक पुनरावर्ती कॉल कहा जाता है) शिक्षाप्रद है। अगर ऐसा नहीं है तो विधि हमेशा के लिए चला जाएगा।

06/08/2008 को 03:54
का स्रोत उपयोगकर्ता

वोट
12

प्रत्यावर्तन एक समारोह है जो अपने आप कॉल के साथ एक समस्या को सुलझाने है। इस का एक अच्छा उदाहरण एक भाज्य कार्य है। क्रमगुणित जहां 5 भाज्य, उदाहरण के लिए, 5 * 4 * 3 * 2 * 1. इस समारोह धनात्मक पूर्णांक के लिए सी # में इस हल करती है एक गणित की समस्या है (परीक्षण नहीं - एक बग हो सकता है)।

public int Factorial(int n)
{
    if (n <= 1)
        return 1;

    return n * Factorial(n - 1);
}
04/05/2010 को 12:29
का स्रोत उपयोगकर्ता

वोट
9

एक पर विचार वर्ष, अच्छी तरह से ज्ञात समस्या :

गणित में, सबसे बड़ा आम भाजक (gcd) दो या अधिक गैर शून्य पूर्णांकों का ..., सबसे बड़ा सकारात्मक पूर्णांक है कि एक शेष के बिना संख्या विभाजित करता है।

gcd की परिभाषा में आश्चर्यजनक रूप से आसान है:

gcd परिभाषा

जहां आधुनिक है सापेक्ष ऑपरेटर (जो है, पूर्णांक विभाजन के बाद शेष)।

अंग्रेजी में, इस परिभाषा का कहना है किसी भी संख्या और शून्य का सबसे बड़ा आम भाजक है कि संख्या, और दो संख्याओं का सबसे बड़ा आम भाजक है मी और n के सबसे बड़ा आम भाजक है n और विभाजित करने के बाद शेष मीटर से n

क्या आप जानते हैं करना चाहते हैं तो यह क्यों काम करता है, पर विकिपीडिया लेख देखें इयूक्लिडियन एल्गोरिथ्म

एक उदाहरण के रूप में gcd (10, 8) की गणना करते हैं। हर कदम बस से पहले एक के बराबर है:

  1. gcd (10, 8)
  2. gcd (10, 10 आधुनिक 8)
  3. gcd (8, 2)
  4. gcd (8, 8 आधुनिक 2)
  5. gcd (2, 0)
  6. 2

पहले चरण में, 8 शून्य के बराबर नहीं है, तो परिभाषा के दूसरे भाग लागू होता है। 10 आधुनिक 8 = 2 क्योंकि 8 2. के शेष चरण 3 पर के साथ एक बार 10 में चला जाता है, दूसरे भाग फिर से लागू होता है, लेकिन इस बार 8 आधुनिक 2 = 0 क्योंकि 2 विभाजित 8 कोई शेष के साथ। चरण 5 में, दूसरा तर्क 0 है, तो जवाब 2 है।

आपको लगता है कि gcd दोनों बराबर का बाएँ और दाएँ पक्ष पर हस्ताक्षर पर दिखाई देता है देखा? एक गणितज्ञ कहेंगे इस परिभाषा पुनरावर्ती है, क्योंकि अभिव्यक्ति आप तय कर रहे हैं फिर से होता है इसकी परिभाषा के अंदर।

पुनरावर्ती परिभाषाओं सुरुचिपूर्ण हो जाते हैं। उदाहरण के लिए, एक सूची के योग के लिए एक पुनरावर्ती परिभाषा है

sum l =
    if empty(l)
        return 0
    else
        return head(l) + sum(tail(l))

जहां headएक सूची में पहले तत्व है और tailसूची में से बाकी है। ध्यान दें कि sumअंत में इसकी परिभाषा के अंदर फिर से होता है।

हो सकता है कि आप के बजाय एक सूची से अधिकतम मान पसंद करते हैं:

max l =
    if empty(l)
        error
    elsif length(l) = 1
        return head(l)
    else
        tailmax = max(tail(l))
        if head(l) > tailmax
            return head(l)
        else
            return tailmax

आप इसे जोड़ की एक श्रृंखला में बदलने के लिए गैर नकारात्मक पूर्णांक रिकर्सिवली के गुणन से परिभाषित करें:

a * b =
    if b = 0
        return 0
    else
        return a + (a * (b - 1))

अतिरिक्त की एक श्रृंखला में गुणन बदलने मतलब नहीं है के बारे में है कि बिट, कुछ सरल उदाहरण के विस्तार को देखने के लिए यह कैसे काम करता प्रयास करें।

मर्ज तरह एक प्यारा पुनरावर्ती परिभाषा है:

sort(l) =
    if empty(l) or length(l) = 1
        return l
    else
        (left,right) = split l
        return merge(sort(left), sort(right))

पुनरावर्ती परिभाषाओं चारों ओर अगर आप जानते हैं देखने के लिए क्या कर रहे हैं। गौर करें कि इन परिभाषाओं के सभी बहुत ही सरल आधार मामलों, है जैसे , gcd (एम, 0) एम =। पुनरावर्ती मामलों छीलना दूर समस्या पर आसान जवाब करने के लिए नीचे लाने के लिए।

इस समझ के साथ, आप अब में अन्य एल्गोरिदम सराहना कर सकते हैं प्रत्यावर्तन पर विकिपीडिया के लेख !

04/05/2010 को 14:58
का स्रोत उपयोगकर्ता

वोट
9

प्रत्यावर्तन एक तरीका है जिसके समस्या का एक छोटा संस्करण को सुलझाने और फिर उस परिणाम के साथ साथ कुछ अन्य गणना का उपयोग कर मूल समस्या का जवाब तैयार करने के लिए से एक समस्या का हल करने के लिए संदर्भित करता है। कई बार, छोटे संस्करण को सुलझाने की प्रक्रिया में, विधि समस्या का एक अभी तक छोटे संस्करण का समाधान होगा, और इतने पर, जब तक यह एक "आधार मामले" जो हल करने के लिए मामूली बात है तक पहुँचता है।

उदाहरण के लिए, संख्या के लिए एक भाज्य की गणना करने के Xलिए, एक के रूप में यह प्रतिनिधित्व कर सकते हैं X times the factorial of X-1। इस प्रकार, विधि "recurses" के भाज्य को खोजने के लिए X-1, और फिर गुणा जो कुछ भी यह द्वारा मिल गया Xएक अंतिम जवाब देने के लिए। बेशक, के भाज्य लगाने के लिए X-1, यह पहली की भाज्य की गणना करेंगे X-2, और इतने पर। आधार मामला होगा जब X0 या 1 है, ऐसी स्थिति में इसे वापस करने के लिए जानता है 1के बाद से 0! = 1! = 1

04/05/2010 को 12:26
का स्रोत उपयोगकर्ता

वोट
9
  1. एक समारोह है कि खुद को कॉल
  2. एक समारोह हो सकता है जब (आसानी से) एक सरल ऑपरेशन के साथ साथ समस्या के कुछ छोटे से हिस्से पर एक ही समारोह में विघटित। मैं नहीं बल्कि, कहना चाहिए, यह यह प्रत्यावर्तन लिए एक अच्छे उम्मीदवार बनाता है।
  3. वे करते हैं!

विहित उदाहरण भाज्य जो की तरह लग रहा है:

int fact(int a) 
{
  if(a==1)
    return 1;

  return a*fact(a-1);
}

सामान्य तौर पर, प्रत्यावर्तन जरूरी तेजी (समारोह कॉल उपरि उच्च हो जाता है क्योंकि पुनरावर्ती कार्यों छोटे होते हैं, ऊपर देखें) और कुछ समस्याओं से ग्रस्त कर सकते हैं (ढेर अतिप्रवाह किसी को?) नहीं है। कुछ वे गैर तुच्छ मामलों में 'सही' प्राप्त करने के लिए कठिन हो जाते हैं, लेकिन मैं वास्तव में उस में नहीं खरीदते हैं का कहना है। कुछ स्थितियों में, प्रत्यावर्तन सबसे समझ में आता है और सबसे सुंदर और स्पष्ट को किसी खास समारोह में लिखने के लिए है। ऐसा लगता है कि कुछ भाषाओं पुनरावर्ती समाधान के पक्ष में है और उन्हें और अधिक अनुकूलन (लिस्प मन में आता है)।

06/08/2008 को 03:35
का स्रोत उपयोगकर्ता

वोट
7

एक पुनरावर्ती समारोह एक है जो अपने आप कॉल है। सबसे आम कारण है कि मैं इसे एक वृक्ष संरचना traversing है उपयोग करने के लिए मिल गया है। उदाहरण के लिए, अगर मैं चेक बॉक्स के साथ एक TreeView है (लगता है एक नया कार्यक्रम, "स्थापित करने के लिए सुविधाओं का चयन" पृष्ठ की स्थापना), मैं एक "सभी की जाँच करें" बटन जो इस (स्यूडोकोड) की तरह कुछ हो जाएगा चाहते हो सकता है:

function cmdCheckAllClick {
    checkRecursively(TreeView1.RootNode);
}

function checkRecursively(Node n) {
    n.Checked = True;
    foreach ( n.Children as child ) {
        checkRecursively(child);
    }
}

तो आप देख सकते है कि checkRecursively प्रथम नोड जो यह पारित हो जाता है की जाँच करता है, तो उस नोड के बच्चों में से प्रत्येक के लिए खुद को कहता है।

आप प्रत्यावर्तन के साथ एक सा सावधान रहने की जरूरत नहीं है। आप एक अनंत पुनरावर्ती पाश में हो, तो आप एक स्टैक ओवरफ़्लो अपवाद मिल जाएगा :)

मैं एक कारण है कि लोगों को यह प्रयोग नहीं करना चाहिए, जब उचित नहीं सोच सकते हैं। यह कुछ परिस्थितियों में, और दूसरों में नहीं उपयोगी है।

मुझे लगता है कि क्योंकि यह एक दिलचस्प तकनीक है, कुछ कोडर शायद ऊपर, अधिक बार उन्हें करना चाहिए की तुलना में इसे का उपयोग वास्तविक औचित्य के बिना खत्म हो। यह कुछ हलकों में प्रत्यावर्तन एक बुरा नाम दे दिया है।

06/08/2008 को 03:44
का स्रोत उपयोगकर्ता

वोट
5

प्रत्यावर्तन एक अभिव्यक्ति प्रत्यक्ष या परोक्ष रूप से ही संदर्भित है।

एक साधारण उदाहरण के रूप में पुनरावर्ती acronyms पर विचार करें:

  • जीएनयू के लिए खड़ा है जीएनयू के नहीं यूनिक्स
  • पीएचपी के लिए खड़ा है PHP: हाइपरटेक्स्ट प्रीप्रोसेसर
  • YAML खड़ा के लिए YAML भाषा मार्कअप नहीं है
  • WINE खड़ा के लिए शराब एक Emulator नहीं है
  • वीज़ा के लिए खड़ा है वीज़ा इंटरनेशनल सेवा संघ

विकिपीडिया पर अधिक उदाहरण

04/05/2010 को 12:56
का स्रोत उपयोगकर्ता

वोट
5

यहाँ एक सरल उदाहरण है: एक सेट में कितने तत्वों। (वहाँ बेहतर तरीके बातें गिनती करने के लिए हैं, लेकिन यह एक अच्छा सरल पुनरावर्ती उदाहरण है।)

सबसे पहले, हम दो नियमों की जरूरत है:

  1. अगर सेट खाली है, सेट में आइटम की गणना शून्य (ओह!) है।
  2. अगर सेट खाली नहीं है, गिनती एक से अधिक सेट के बाद एक आइटम निकाल दिया जाता है में आइटमों की संख्या है।

मान लीजिए आप इस तरह एक सेट है: [XXX]। के गिनती देखते हैं कि कितने आइटम हैं।

  1. सेट है [XXX] जो खाली नहीं है, तो हम शासन 2. लागू मदों की संख्या एक से अधिक में आइटमों की संख्या है [xx] (यानी हम एक आइटम निकाल)।
  2. सेट [xx] है, तो हम फिर से नियम 2 लागू होते हैं: [x] की एक वस्तु के + संख्या।
  3. [] की एक वस्तु के + संख्या: सेट [x], जो अभी भी नियम 2 से मेल खाता है।
  4. अब सेट [], जो नियम 1 से मेल खाता है: गिनती शून्य है!
  5. हम चरण 4 में जवाब पता अब जब कि (0), हम हल कर सकते हैं चरण 3 (1 + 0)
  6. इसी तरह, अब हम चरण 3 में जवाब पता है कि (1), हम हल कर सकते हैं चरण 2 (1 + 1)
  7. और अंत में अब है कि हम (2) चरण 2 में जवाब पता है, हम (+2 1) चरण 1 हल कर सकते हैं और में मदों की संख्या प्राप्त [XXX], जो 3. हुर्रे है!

हम के रूप में इस का प्रतिनिधित्व कर सकते हैं:

count of [x x x] = 1 + count of [x x]
                 = 1 + (1 + count of [x])
                 = 1 + (1 + (1 + count of []))
                 = 1 + (1 + (1 + 0)))
                 = 1 + (1 + (1))
                 = 1 + (2)
                 = 3

जब एक पुनरावर्ती समाधान को लागू करने, आप आमतौर पर कम से कम 2 नियम है:

  • आधार, सरल मामले जिसमें कहा गया है कि क्या होता है जब आपके पास अपने सभी डेटा के "का इस्तेमाल किया।" यह आमतौर पर की "यदि आप इस प्रक्रिया के लिए डेटा से बाहर हैं, आपका जवाब एक्स है" कुछ विविधता होती है
  • पुनरावर्ती नियम है, जिसमें कहा गया है आप अभी भी डेटा है तो क्या होता है। यह आमतौर पर नियम किसी तरह का है कि कहते हैं कि "कुछ करने के लिए अपने डेटा कम पर सेट बनाने के लिए, और छोटे डेटा सेट करने के लिए अपने नियमों पुन: लागू करने के लिए।"

अगर हम स्यूडोकोड करने के लिए ऊपर का अनुवाद, हम पाते हैं:

numberOfItems(set)
    if set is empty
        return 0
    else
        remove 1 item from set
        return 1 + numberOfItems(set)

वहाँ एक बहुत अधिक उपयोगी उदाहरण (एक पेड़ traversing, उदाहरण के लिए), जो मुझे यकीन है कि अन्य लोगों को कवर किया जाएगा हूँ।

06/08/2008 को 04:12
का स्रोत उपयोगकर्ता

वोट
5

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

लोग कई कारणों से के लिए प्रत्यावर्तन से बचने:

  1. के रूप में कार्यात्मक प्रोग्रामिंग करने के लिए विरोध ज्यादातर लोगों (अपने आप को शामिल) प्रक्रियात्मक या वस्तु उन्मुख प्रोग्रामिंग पर अपने प्रोग्रामिंग दांत काट। इस तरह के लोगों के लिए, पुनरावृत्ति दृष्टिकोण (आमतौर पर छोरों का उपयोग करके) और अधिक प्राकृतिक महसूस करता है।

  2. हममें से वे जो प्रक्रियात्मक या ऑब्जेक्ट ओरिएंटेड प्रोग्रामिंग पर हमारी प्रोग्रामिंग दांत काट अक्सर प्रत्यावर्तन से बचने के लिए, क्योंकि यह त्रुटियों की संभावना है बताया गया है।

  3. हम अक्सर बताया कि प्रत्यावर्तन धीमी है। कॉलिंग और एक नियमित से लौटने के बार-बार ढेर धक्का और पॉपिंग, जो पाशन की तुलना में धीमी है की एक बहुत कुछ शामिल है। मुझे लगता है कि कुछ भाषाओं दूसरों से बेहतर संभाल, और उन भाषाओं सबसे अधिक संभावना उन जहां प्रभावी प्रतिमान प्रक्रियात्मक या वस्तु उन्मुख है नहीं कर रहे हैं।

  4. प्रोग्रामिंग भाषाओं मैं का उपयोग किया है की कम से कम एक जोड़ी के लिए, मैं सुनवाई सिफारिशों क्योंकि इसके ढेर है कि गहरे नहीं है अगर यह एक निश्चित गहराई से परे हो जाता है प्रत्यावर्तन उपयोग करने के लिए नहीं याद है।

06/08/2008 को 04:12
का स्रोत उपयोगकर्ता

वोट
4

1.) एक विधि है, तो वह खुद को कॉल कर सकते हैं पुनरावर्ती है; या तो सीधे:

void f() {
   ... f() ... 
}

या परोक्ष रूप से:

void f() {
    ... g() ...
}

void g() {
   ... f() ...
}

2.) जब प्रत्यावर्तन उपयोग करने के लिए

Q: Does using recursion usually make your code faster? 
A: No.
Q: Does using recursion usually use less memory? 
A: No.
Q: Then why use recursion? 
A: It sometimes makes your code much simpler!

3.) लोग प्रत्यावर्तन का उपयोग केवल जब यह पुनरावृत्ति कोड लिखने के लिए बहुत जटिल है। उदाहरण के लिए, अग्रिम आदेश की तरह पेड़ ट्रेवर्सल तकनीक, क्रंमोत्तर दोनों पुनरावृत्ति और पुनरावर्ती बनाया जा सकता है। लेकिन आम तौर पर हम अपनी सादगी की वजह से पुनरावर्ती का उपयोग करें।

11/03/2014 को 10:47
का स्रोत उपयोगकर्ता

वोट
4

एक पुनरावर्ती बयान एक है जिसमें आप आदानों का एक संयोजन है और क्या आप पहले से ही किया है के रूप में आगे क्या करना है की प्रक्रिया को परिभाषित है।

उदाहरण के लिए, भाज्य ले:

factorial(6) = 6*5*4*3*2*1

लेकिन यह भाज्य देखने के लिए (6) भी है आसान है:

6 * factorial(5) = 6*(5*4*3*2*1).

तो आम तौर पर:

factorial(n) = n*factorial(n-1)

बेशक, प्रत्यावर्तन के बारे में मुश्किल बात करता है, तो आप क्या आप पहले से ही किया है के मामले में चीजें निर्धारित करना चाहते हैं, वहाँ कुछ जगह शुरू करने के लिए होने की जरूरत है।

इस उदाहरण में, हम सिर्फ भाज्य (1) = 1 को परिभाषित करते हुए एक विशेष मामला बनाते हैं।

अब हम यह नीचे से ऊपर देखें:

factorial(6) = 6*factorial(5)
                   = 6*5*factorial(4)
                   = 6*5*4*factorial(3) = 6*5*4*3*factorial(2) = 6*5*4*3*2*factorial(1) = 6*5*4*3*2*1

जब से हम भाज्य (1) = 1 परिभाषित है, हम "नीचे" तक पहुँचते हैं।

सामान्य शब्दों में, पुनरावर्ती प्रक्रियाओं दो भाग होते हैं:

1) पुनरावर्ती हिस्सा है, जो कि तुम क्या उसी प्रक्रिया के माध्यम से "पहले से ही किया" गया है के साथ संयुक्त नया आदानों के मामले में कुछ प्रक्रिया को परिभाषित करता है। (यानी factorial(n) = n*factorial(n-1))

2) एक आधार हिस्सा है, जो लगता है कि इस प्रक्रिया को शुरू करने के लिए यह कुछ जगह देकर हमेशा के लिए दोहराया नहीं जाता है बनाता है (यानी factorial(1) = 1)

यह एक सा पहली बार में चारों ओर अपने सिर प्राप्त करने के लिए भ्रमित किया जा सकता है, लेकिन सिर्फ उदाहरण के एक झुंड को देखो और सभी को एक साथ आना चाहिए। आप अवधारणा का एक बहुत गहरी समझ चाहते हैं, का अध्ययन गणितीय प्रेरण। इसके अलावा, पता है कि कुछ भाषाओं पुनरावर्ती कॉल के लिए अनुकूलन जबकि अन्य को नहीं हो। यह पागलपन की हद तक धीमी गति से पुनरावर्ती कार्यों बनाने के लिए अगर आप सावधान नहीं कर रहे हैं बहुत आसान है, लेकिन वहाँ भी उन्हें ज्यादातर मामलों में performant बनाने के लिए तकनीक है।

उम्मीद है की यह मदद करेगा...

04/05/2010 को 14:30
का स्रोत उपयोगकर्ता

वोट
4

मैं इस परिभाषा की तरह:
प्रत्यावर्तन में, एक नियमित, एक समस्या के ही एक छोटा सा हिस्सा हल करती है छोटे टुकड़ों में समस्या बिताते हैं, और फिर छोटे टुकड़ों में से प्रत्येक को हल करने में ही कहता है।

मैं भी कोड में प्रत्यावर्तन के स्टीव McConnells चर्चा चाहते को पूरा करें जहां वह Recursion पर कंप्यूटर विज्ञान की पुस्तकों में उपयोग किए गए उदाहरणों की आलोचना की।

factorials या फाइबोनैचि संख्या के लिए प्रत्यावर्तन का उपयोग न करें

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

मुझे लगा कि यह बढ़ाने के लिए एक बहुत ही दिलचस्प बात यह थी और एक कारण है कि प्रत्यावर्तन अक्सर गलत समझा जाता है हो सकता है।

संपादित करें: यह Dav के जवाब में एक खुदाई नहीं था - मुझे लगता है कि जबाब नहीं देखा था जब मैं इस पोस्ट

04/05/2010 को 12:29
का स्रोत उपयोगकर्ता

वोट
3

एक उदाहरण: एक सीढ़ी का एक पुनरावर्ती परिभाषा है: एक सीढ़ी के होते हैं: - एक ही चरण और एक सीढ़ी (प्रत्यावर्तन) - या केवल एक ही कदम (समापन)

04/05/2010 को 14:34
का स्रोत उपयोगकर्ता

वोट
3

ठीक है, कि एक बहुत सभ्य परिभाषा आपके पास है। और विकिपीडिया एक अच्छा परिभाषा भी है। इसलिए मैं आप के लिए एक और (शायद बदतर) परिभाषा जोड़ देंगे।

जब लोगों को "प्रत्यावर्तन" का संदर्भ लें, वे आमतौर पर एक समारोह वे लिखा है जो अपने आप को बार-बार कहता है जब तक वह अपने काम के साथ किया जाता के बारे में बात कर रहे हैं। प्रत्यावर्तन सहायक होता है जब डेटा संरचनाओं में पदानुक्रम traversing हो सकता है।

04/05/2010 को 12:27
का स्रोत उपयोगकर्ता

वोट
3

एक हल समस्या पर recurse करने के लिए: कुछ भी नहीं, बस हो गया।
एक खुला समस्या पर recurse करने के लिए: अगले कदम के लिए करते हैं, तो बाकी पर recurse।

06/08/2008 को 04:32
का स्रोत उपयोगकर्ता

वोट
2

यह एक पुरानी सवाल (यानी दृश्य या देखने का प्रदर्शन बिंदु के एल्गोरिथ्म शुद्धता बिंदु से नहीं) है, लेकिन मैं देखने के साजो बिंदु से एक जवाब जोड़ना चाहते हैं।

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

इस प्रकार, मैं अक्सर प्रत्यावर्तन, और उपयोग ढेर आपरेशन बजाय बचने के लिए, क्योंकि प्रत्यावर्तन ही अनिवार्य रूप से एक ढेर ऑपरेशन है।

30/08/2014 को 11:09
का स्रोत उपयोगकर्ता

वोट
2

एक पुनरावर्ती समारोह एक समारोह है जो अपने आप के लिए एक कॉल शामिल हैं। एक पुनरावर्ती struct एक struct कि खुद का एक उदाहरण होता है। आप एक पुनरावर्ती वर्ग के रूप में दो जोड़ सकते हैं। एक पुनरावर्ती आइटम के प्रमुख बात यह है कि यह अपने आप का एक उदाहरण / कॉल शामिल हैं।

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

एक द्विआधारी खोज वृक्ष प्रत्यावर्तन का एक अच्छा प्रोग्रामिंग उदाहरण है। संरचना एक नोड के 2 उदाहरणों वाले प्रत्येक नोड के साथ पुनरावर्ती है। एक द्विआधारी खोज वृक्ष पर काम करने के कार्य भी पुनरावर्ती हैं।

04/05/2010 को 17:46
का स्रोत उपयोगकर्ता

वोट
2

सादे अंग्रेजी में: मान लीजिए आप 3 कर सकते हैं:

  1. एक सेब ले लो
  2. नीचे मिलान रेखाओं लिखें
  3. गणना मिलान रेखाओं

आप एक मेज पर आप के सामने सेब का एक बहुत है और आप को पता है देखते हैं कितने सेब चाहते हैं।

start
  Is the table empty?
  yes: Count the tally marks and cheer like it's your birthday!
  no:  Take 1 apple and put it aside
       Write down a tally mark
       goto start

एक ही बात दोहरा तक आप कर चुके हैं की प्रक्रिया प्रत्यावर्तन कहा जाता है।

मुझे आशा है कि यह "सादे अंग्रेजी" जवाब आप के लिए देख रहे हैं!

04/05/2010 को 14:09
का स्रोत उपयोगकर्ता

वोट
1

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

प्रत्यावर्तन http://cart.kolix.de/wp-content/uploads/2009/12/infinite-recursion.jpg

04/05/2010 को 17:10
का स्रोत उपयोगकर्ता

वोट
1

प्रत्यावर्तन आप एक ऑपरेशन में ही उपयोग करता है जब है। यह शायद एक रोक बिंदु होगा, अन्यथा यह हमेशा के लिए पर जाना होगा।

मान लीजिए कि आप शब्दकोश में एक शब्द को देखने के लिए चाहते हैं। आप अपने निपटान में एक ऑपरेशन "देखो-अप" कहा जाता है।

आपके मित्र कहते हैं, "मैं वास्तव में अभी कुछ हलवा अप चम्मच सकता है!" आप वह क्या मतलब पता नहीं है, तो आप शब्दकोश में "चम्मच" देखो, और यह कुछ इस तरह लिखा है:

चम्मच संज्ञा - अंत में एक दौर स्कूप के साथ एक बर्तन। चम्मच: पीछे से बारीकी से cuddle करने के लिए -: - क्रिया क्रिया कुछ चम्मच पर एक चम्मच का उपयोग करने के

अब, जा रहा है कि तुम सच में अंग्रेजी के साथ अच्छा नहीं कर रहे हैं, यह सही दिशा में बताते हैं, लेकिन आप अधिक जानकारी की जरूरत है। तो अगर आप कुछ और जानकारी के लिए देखने के लिए "बर्तन" और "आलिंगन" का चयन करें।

गले लगाएं: क्रिया - टेकना करने के बर्तन: संज्ञा - एक उपकरण, अक्सर एक खाने बर्तन

अरे! आप क्या snuggling है, और यह हलवा के साथ कोई संबंध नहीं है। आप यह भी जानते हैं कि हलवा कुछ आप खाने के है, इसलिए यह अब समझ में आता है। आपके मित्र एक चम्मच के साथ हलवा खाना चाहता हूँ चाहिए।

ठीक है, ठीक है, यह एक बहुत ही लंगड़ा उदाहरण था, लेकिन यह दिखाता है (शायद खराब) प्रत्यावर्तन के दो मुख्य भागों। 1) यह अपने आप उपयोग करता है। इस उदाहरण में, आप वास्तव में ऊपर एक शब्द सार्थक ध्यान दिया है नहीं जब तक आप इसे समझते हैं, और अधिक शब्दों को देख मतलब हो सकता है कि। यह दो बात करने के लिए हमें लाता है, 2) यह कहीं रुक जाती है। यह आधार दर-मामला किसी तरह का होना आवश्यक है। अन्यथा, आप सिर्फ शब्दकोश है, जो शायद बहुत उपयोगी नहीं है में हर शब्द को देख पहुंचते हैं। हमारा आधार मामला था कि आप आपने पहले किया था और समझ में नहीं आया कि क्या के बीच एक कनेक्शन बनाने के लिए पर्याप्त जानकारी मिल गया।

जहां 5 भाज्य 1 * 2 * 3 * 4 * 5 (जो 120 है) पारंपरिक उदाहरण है कि दिया है, भाज्य है। आधार मामले 0 (या 1, निर्भर करता है) होगा। तो, किसी भी पूरी संख्या n के लिए, आप निम्न कर

n 0 के बराबर है? 1 अन्यथा लौटने के लिए, लौट n * (n-1 के भाज्य)

के 4 के उदाहरण (जिसे हम समय से आगे पता 1 * 2 * 3 * 4 = 24 है) के साथ ऐसा करते हैं।

4 के भाज्य ... यह 0 है? नहीं, तो यह 4 होना चाहिए * 3 के भाज्य लेकिन 3 के भाज्य क्या है? यह 3 * 2 का 2 भाज्य के भाज्य 2 * 1 का 1 भाज्य के भाज्य 1 है * 0 के भाज्य और हम 0 में से भाज्य जानते हैं! :-D यह 1 है, कि 1 की परिभाषा भाज्य 1 है * 0, जो 1 था के भाज्य है ... तो 1 * 1 = 1 2 के भाज्य 2 1, जो 1 था के भाज्य 2 है * ... इसलिए * 3 में से 1 = 2 भाज्य 3 2, जो 2 था के भाज्य है * ... इसलिए 3 * 2 = 6 भाज्य के 4 (अंत में !!) 4 * 3 के भाज्य है, जो था 6 ... 4 * 6 है 24

क्रमगुणित का एक सरल मामला है "आधार मामला है, और खुद का उपयोग करता है"।

अब, नोटिस हम अभी भी पूरी तरह से नीचे 4 के भाज्य पर काम कर रहे थे ... अगर हम 100 के भाज्य चाहता था, हम 0 करने के लिए सभी तरह से नीचे जाने के लिए ... यह करने के लिए भूमि के ऊपर का एक बहुत हो सकता है जो होगा। इसी तरह, अगर हम एक अस्पष्ट शब्द शब्दकोश में खोजने के लिए मिल जाए, इसे दूसरे शब्दों और संदर्भ सुराग के लिए स्कैनिंग की तलाश में लग सकता है जब तक हम एक कनेक्शन हम से परिचित हो पाते हैं। पुनरावर्ती तरीकों एक लंबे समय के माध्यम से अपने तरीके से काम करने के लिए ले जा सकते हैं। हालांकि, जब वे सही ढंग से इस्तेमाल कर रहे हैं, और समझते थे, वे जटिल काम आश्चर्यजनक रूप से सरल बना सकते हैं।

04/05/2010 को 17:04
का स्रोत उपयोगकर्ता

वोट
1

एक महान कई समस्याओं टुकड़े के दो प्रकार में के बारे में सोचा जा सकता है:

  1. बेस मामलों, जो प्राथमिक चीजें हैं जो आप सिर्फ उन्हें देख कर हल कर सकते हैं, और
  2. पुनरावर्ती मामलों, जो छोटे टुकड़ों (प्राथमिक या अन्यथा) से बाहर एक बड़ा समस्या का निर्माण।

तो एक पुनरावर्ती समारोह क्या है? ठीक है, कि जहाँ आप एक समारोह है कि खुद के रूप में परिभाषित किया गया है है, प्रत्यक्ष या परोक्ष रूप। आप आधार मामलों सीधे सुलझाने और पुनरावर्ती कॉल का उपयोग के रूप में एम्बेडेड समस्या के छोटे टुकड़ों को हल करने के द्वारा पुनरावर्ती मामलों से निपटने के: ठीक है, कि हास्यास्पद जब तक आप महसूस करते हैं कि यह एक तरह ऊपर वर्णित की समस्याओं के लिए समझदार है लगता है।

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

struct Tree {
    int leaf;
    Tree *leftBranch;
    Tree *rightBranch;
};

आदेश में इस प्रिंट की सबसे सरल तरीका प्रत्यावर्तन उपयोग करने के लिए है:

function printTreeInOrder(Tree *tree) {
    if (tree->leftBranch) {
        printTreeInOrder(tree->leftBranch);
    }
    print(tree->leaf);
    if (tree->rightBranch) {
        printTreeInOrder(tree->rightBranch);
    }
}

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

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

यह भी अनंत प्रत्यावर्तन के लिए संभव है। ऐसा इसलिए है क्योंकि ढेर ऊपर चल रही है काम नहीं करेगा गन्दा और कई भाषाओं में है। (जहां यह काम करता है, भाषा इंजन सामान्य रूप में निर्धारित करने जाना चाहिए कि समारोह किसी भी तरह वापस नहीं करता है और इसलिए सक्षम ढेर के ध्यान में रखते हुए दूर का अनुकूलन है ट्रिकी सामान;। पूंछ-प्रत्यावर्तन ऐसा करने का सिर्फ सबसे छोटी तरीका है ।)

04/05/2010 को 16:29
का स्रोत उपयोगकर्ता

वोट
1

प्रत्यावर्तन खुद के मामले में एक समारोह, एक सेट या एक एल्गोरिथ्म को परिभाषित करने की तकनीक है।

उदाहरण के लिए

n! = n(n-1)(n-2)(n-3)...........*3*2*1

अब यह पुनरावर्ती के रूप में परिभाषित किया जा सकता है: -

n! = n(n-1)!   for n>=1

प्रोग्रामिंग संदर्भ में, जब एक समारोह या विधि में ही बार-बार कहता है, जब तक कुछ विशिष्ट हालत संतुष्ट हो जाता है, इस प्रक्रिया को Recursion कहा जाता है। लेकिन वहाँ एक समाप्त हालत और समारोह होना चाहिए या विधि कोई एक अनंत लूप में दर्ज करना होगा।

04/05/2010 को 16:22
का स्रोत उपयोगकर्ता

वोट
1

कंप्यूटिंग में प्रत्यावर्तन एक भी समारोह (विधि, प्रक्रिया या ब्लॉक) मंगलाचरण से सामान्य वापसी के बाद एक परिणाम या पक्ष प्रभाव की गणना करने के लिए प्रयोग किया जाता एक तकनीक है।

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

उदाहरण के लिए, यहाँ स्काला में quicksort एल्गोरिथ्म (प्रदर्शन करने के लिए एक समारोह है स्काला के लिए विकिपीडिया प्रविष्टि से नकल )

def qsort: List[Int] => List[Int] = {
  case Nil => Nil
  case pivot :: tail =>
    val (smaller, rest) = tail.partition(_ < pivot)
    qsort(smaller) ::: pivot :: qsort(rest)
}

इस मामले में बाहर निकलने के हालत एक खाली सूची है।

04/05/2010 को 15:14
का स्रोत उपयोगकर्ता

वोट
1

समारोह में ही फोन या अपने स्वयं परिभाषा का उपयोग करें।

04/05/2010 को 14:59
का स्रोत उपयोगकर्ता

वोट
1

किसी भी एल्गोरिथ्म दर्शाती संरचनात्मक एक डेटाप्रकार पर प्रत्यावर्तन अगर मूल रूप से डेटाप्रकार के प्रत्येक मामले के लिए एक मामले के साथ एक स्विच बयान के होते हैं।

उदाहरण के लिए, जब आप एक प्रकार पर काम कर रहे हैं

  tree = null 
       | leaf(value:integer) 
       | node(left: tree, right:tree)

एक संरचनात्मक पुनरावर्ती एल्गोरिदम के रूप होता है

 function computeSomething(x : tree) =
   if x is null: base case
   if x is leaf: do something with x.value
   if x is node: do something with x.left,
                 do something with x.right,
                 combine the results

यह वास्तव में सबसे स्पष्ट तरीका किसी भी algorith है कि एक डेटा संरचना पर काम करता है लिखने के लिए है।

अब, जब आप पूर्णांकों को देखो (अच्छी तरह से, प्राकृतिक संख्या) के रूप में Peano axioms का उपयोग करके परिभाषित

 integer = 0 | succ(integer)

आप देखते हैं कि पूर्णांकों पर एक संरचनात्मक पुनरावर्ती एल्गोरिदम के इस तरह दिखता है

 function computeSomething(x : integer) =
   if x is 0 : base case
   if x is succ(prev) : do something with prev

बहुत-प्रसिद्ध भाज्य समारोह इस फार्म के सबसे तुच्छ उदाहरण के बारे में है।

04/05/2010 को 14:53
का स्रोत उपयोगकर्ता

वोट
1

हे, खेद है मेरी राय किसी के साथ सहमत हैं, मैं सिर्फ सादे अंग्रेजी में प्रत्यावर्तन समझाने के लिए कोशिश कर रहा हूँ।

मान लीजिए कि आप तीन प्रबंधक होते हैं - जैक, जॉन और मॉर्गन। आप हर प्रबंधक $ 300 देने जा रहे हैं और पता है कि यह खर्च आएगा चाहते 5. - 3, और मॉर्गन - जैक 2 प्रोग्रामर, जॉन प्रबंधन करता है। जवाब स्पष्ट है - लेकिन क्या मॉर्गन-s कर्मचारियों की 2 यदि भी प्रबंधकों रहे हैं?

यहाँ प्रत्यावर्तन आता है। आप पदानुक्रम के शीर्ष से शुरू करते हैं। ग्रीष्मकालिन लागत 0 $ है। आप जैक के साथ शुरू करते हैं, तो फिर अगर वह कर्मचारियों के रूप में किसी भी प्रबंधक हैं की जाँच करें। आप उनमें से किसी पाते हैं, की जाँच कर रहे हैं अगर वे कोई प्रबंधक कर्मचारियों के रूप में और इतने पर। ग्रीष्मकालिन लागत के लिए यदि आप एक प्रबंधक को खोजने हर बार $ 300 जोड़ें। जब आप जैक के साथ समाप्त कर लें, मॉर्गन के लिए जॉन, अपने कर्मचारियों के लिए जाना और फिर।

आप कभी पता नहीं चलेगा, कितना चक्र आप एक जवाब प्राप्त करने से पहले जाना होगा, हालांकि आप जानते हैं कि आप कितने प्रबंधकों है और आप कितने बजट खर्च कर सकते हैं।

प्रत्यावर्तन शाखाओं और पत्तियों, माता-पिता को फोन किया और बच्चों क्रमशः के साथ, एक पेड़ है। यदि आप एक प्रत्यावर्तन एल्गोरिथ्म का उपयोग करते हैं, तो आप कम या ज्यादा बूझकर डेटा से एक पेड़ के निर्माण कर रहे हैं।

04/05/2010 को 13:50
का स्रोत उपयोगकर्ता

वोट
1

सादे अंग्रेजी में, प्रत्यावर्तन someting बार बार दोहराने का मतलब है।

प्रोग्रामिंग में एक उदाहरण के भीतर ही फ़ंक्शन को कॉल की है।

किसी संख्या का फ़ैक्टोरियल की गणना के निम्न उदाहरण पर देखो:

public int fact(int n)
{
    if (n==0) return 1;
    else return n*fact(n-1)
}
04/05/2010 को 13:48
का स्रोत उपयोगकर्ता

वोट
1

प्रत्यावर्तन प्रक्रिया है जहाँ iself एक विधि कॉल एक निश्चित कार्य करने के लिए सक्षम होने के लिए है। यह कोड की redundency कम कर देता है। इस अनंत लूप का निर्माण रोकता है - ज्यादातर recurssive कार्यों या तरीकों एक condifiton फोन यानी ही बुला अगर एक की स्थिति उत्पन्न होने से रोकने recussive तोड़ने के लिए होना आवश्यक है। नहीं सभी कार्यों रिकर्सिवली प्रयोग की जाने वाली अनुकूल हैं।

04/05/2010 को 13:42
का स्रोत उपयोगकर्ता

वोट
1

इसकी एक तरह से खत्म हो गया और अनिश्चित काल के इस तरह है कि हर विकल्प प्रयोग किया जाता है से अधिक काम करने की।

उदाहरण के लिए यदि आप एक html पृष्ठ पर सभी लिंक आप recursions है क्योंकि जब आप पेज 1 पर सभी लिंक मिल आप पहले पृष्ठ पर मिलने वाले लिंक में से प्रत्येक पर सभी लिंक प्राप्त करना चाहते हैं जाएगा चाहते हैं प्राप्त करना चाहता था। फिर एक newpage के लिए प्रत्येक लिंक के लिए आप उन लिंक्स चाहते हैं और इतने पर ... दूसरे शब्दों में यह एक समारोह है जो अपने आप ही अंदर से कहता है।

आप कोई तरीका होना चाहिए जब आप ऐसा करते हैं जब रोकने के लिए पता करने के लिए या फिर आप एक अंतहीन लूप में हो जाएगा तो आप चक्र की संख्या को ट्रैक करने के लिए कार्य करने के लिए एक पूर्णांक परम जोड़ें।

सी # में आप कुछ इस तरह होगा:

private void findlinks(string URL, int reccursiveCycleNumb)    {
   if (reccursiveCycleNumb == 0)
        {
            return;
        }

        //recursive action here
        foreach (LinkItem i in LinkFinder.Find(URL))
        {
            //see what links are being caught...
            lblResults.Text += i.Href + "<BR>";

            findlinks(i.Href, reccursiveCycleNumb - 1);
        }

        reccursiveCycleNumb -= reccursiveCycleNumb;
}
04/05/2010 को 13:02
का स्रोत उपयोगकर्ता

वोट
1

"अगर मैं एक हथौड़ा है, सब कुछ एक कील की तरह लग रहे हैं।"

प्रत्यावर्तन के लिए एक समस्या को सुलझाने रणनीति है विशाल समस्याओं, जहां पर हर बस, हर बार एक ही हथौड़ा के साथ "2 छोटी बातों एक बड़ा बात में बदल जाते हैं," कदम।

उदाहरण

मान लीजिए कि आपके डेस्क 1024 पत्र की एक बेतरतीब गड़बड़ से आच्छादित है। कैसे आप गंदगी से एक स्वच्छ, कागज के स्वच्छ ढेर कर सकता हूँ, प्रत्यावर्तन का उपयोग कर?

  1. फूट डालो: सभी पत्रक से बाहर फैला है, तो आप प्रत्येक "ढेर" में केवल एक पत्रक है।
  2. विजय:
    1. चारों ओर जाओ, एक अन्य चादर के शीर्ष पर प्रत्येक शीट डाल। अब आप 2 के ढेर है।
    2. चारों ओर जाओ, एक और 2-ढेर के शीर्ष पर प्रत्येक 2-ढेर डाल। अब आप 4 के ढेर है।
    3. चारों ओर जाओ, एक और 4-ढेर के शीर्ष पर प्रत्येक 4-ढेर डाल। अब आप 8 के ढेर है।
    4. ... इत्यादि ...
    5. अब आप 1024 चादरों की एक विशाल ढेर है!

सूचना यह बहुत सहज है कि, एक तरफ सब कुछ गिनती (जो सख्ती से आवश्यक नहीं है) से। आप सभी तरह से 1 पत्र के ढेर करने के लिए नीचे जाना हो सकता है नहीं, वास्तव में, लेकिन आप और यह अभी भी काम करेगा सकता है। महत्वपूर्ण हिस्सा हथौड़ा है: अपनी बाहों साथ, आप हमेशा दूसरे के ऊपर एक ढेर डाल सकता है एक बड़ा ढेर बनाने के लिए, और यह कोई फर्क नहीं पड़ता (कारण के भीतर) कितना बड़ा या तो ढेर है।

04/05/2010 को 12:54
का स्रोत उपयोगकर्ता

वोट
1

प्रत्यावर्तन के रूप में यह प्रोग्रामिंग करने के लिए लागू होता है मूल रूप से अपनी ही परिभाषा के अंदर से एक समारोह बुला रहा है (के अंदर ही), विभिन्न मापदंडों के साथ इतनी के रूप में एक कार्य को पूरा करने।

04/05/2010 को 12:25
का स्रोत उपयोगकर्ता

वोट
1

आप इसे उपयोग करने के लिए किसी भी समय आप एक वृक्ष संरचना है चाहता हूँ। यह XML पढ़ने में बहुत उपयोगी है।

21/08/2008 को 14:18
का स्रोत उपयोगकर्ता

वोट
1

मारियो, मुझे समझ नहीं आता क्यों आपको लगता है कि उदाहरण के लिए प्रत्यावर्तन इस्तेमाल किया .. बस प्रत्येक प्रविष्टि के माध्यम से लूप क्यों नहीं? कुछ इस तरह:

String ArrangeString(TStringList* items, String separator)
{
    String result = items->Strings[0];

    for (int position=1; position < items->count; position++) {
        result += separator + items->Strings[position];
    }

    return result;
}

उपरोक्त विधि तेजी से होगा, और सरल है। एक साधारण पाश के स्थान पर प्रत्यावर्तन उपयोग करने के लिए कोई ज़रूरत नहीं है। मुझे लगता है कि यही कारण है कि प्रत्यावर्तन एक बुरा आवाज हो जाता है उदाहरण के इन प्रकार है। यहां तक ​​कि विहित भाज्य समारोह उदाहरण बेहतर एक पाश के साथ किया जाता है।

06/08/2008 को 04:19
का स्रोत उपयोगकर्ता

वोट
0

असल में भाज्य के लिए बेहतर पुनरावर्ती समाधान किया जाना चाहिए:

int factorial_accumulate(int n, int accum) {
    return (n < 2 ? accum : factorial_accumulate(n - 1, n * accum));
}

int factorial(int n) {
    return factorial_accumulate(n, 1);
}

इस संस्करण है क्योंकि पूंछ रिकर्सिव

21/08/2008 को 14:39
का स्रोत उपयोगकर्ता

वोट
0

मैं प्रत्यावर्तन का उपयोग करें। क्या है कि (, जो मैं नहीं माध्यम से) एक सीएस डिग्री ... होने के साथ क्या संबंध है

सामान्य उपयोग मैं पाया है:

  1. साइटमैप - दस्तावेज़ जड़ से शुरू फाइल सिस्टम के माध्यम से recurse
  2. मकड़ियों - एक वेबसाइट के माध्यम से रेंगने ईमेल पता, लिंक, आदि को खोजने के लिए
  3. ?
06/08/2008 को 04:13
का स्रोत उपयोगकर्ता

वोट
0

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

String ArrangeString(TStringList* items, int position, String separator)
{
  String result;

  result = items->Strings[position];

  if (position <= items->Count)
    result += separator + ArrangeString(items, position + 1, separator);

  return result;
}

मैं इसे इस तरह कहते हैं:

String columnsList;
columnsList = ArrangeString(columns, 0, ", ");

कल्पना कीजिए कि आप एक सरणी नाम 'है क्षेत्रों इसके अंदर इस डेटा के साथ': ' ALBUMNAME ', ' RELEASEDATE ', ' labelId '। तो फिर तुम फ़ंक्शन को कॉल करें:

ArrangeString(fields, 0, ", ");

समारोह काम करने के लिए शुरू होता है के रूप में, चर ' परिणाम ' सरणी है, जो 'है की स्थिति को 0 में से मूल्य प्राप्त ALBUMNAME '।

तो फिर यह जाँच करता है स्थिति से निपटने के लिए है पिछले एक है अगर। ऐसा नहीं है के रूप में, तो यह विभाजक और एक समारोह है, जो, हे भगवान, यह एक ही समारोह है का परिणाम के साथ परिणाम कोनकैटेनेट्स किया गया। लेकिन इस बार, यह बाहर की जाँच, यह अपने आप में स्थिति के लिए 1 जोड़ने कहते हैं।

ArrangeString(fields, 1, ", ");

यह दोहरा, एक LIFO ढेर बनाने रहता है, जब तक यह एक बिंदु है जहां स्थिति से निपटा जा रहा है कि पिछले एक तक पहुँच जाता है, तो समारोह की सूची पर उस स्थिति पर केवल आइटम देता है, अब और श्रृंखलाबद्ध नहीं। फिर ढेर पीछे की ओर concatenated है।

समझ गया? आप नहीं करते हैं, मैं एक और तरीका यह समझाने के लिए है। : ओ)

06/08/2008 को 04:00
का स्रोत उपयोगकर्ता

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more