function - समझना कि कैसे पुनरावर्ती कार्य काम करते हैं




recursion language-agnostic (12)

1. जब तक कोई शर्त पूरी नहीं हो जाती है तब तक फ़ंक्शन को रिकर्सिव कहा जाता है। वह स्थिति a > b । जब यह स्थिति पूरी हो जाती है, तो वापसी करें 0. पहली नज़र में, मुझे उम्मीद है कि वापसी मूल्य 0 होना चाहिए जो स्पष्ट रूप से गलत है।

कंप्यूटर कंप्यूटिंग sumInts(2,5) यह सोचने के लिए यहां होगा कि क्या यह सक्षम था:

I want to compute sumInts(2, 5)
for this, I need to compute sumInts(3, 5)
and add 2 to the result.
  I want to compute sumInts(3, 5)
  for this, I need to compute sumInts(4, 5)
  and add 3 to the result.
    I want to compute sumInts(4, 5)
    for this, I need to compute sumInts(5, 5)
    and add 4 to the result.
      I want to compute sumInts(5, 5)
      for this, I need to compute sumInts(6, 5)
      and add 5 to the result.
        I want to compute sumInts(6, 5)
        since 6 > 5, this is zero.
      The computation yielded 0, therefore I shall return 5 = 5 + 0.
    The computation yielded 5, therefore I shall return 9 = 4 + 5.
  The computation yielded 9, therefore I shall return 12 = 3 + 9.
The computation yielded 12, therefore I shall return 14 = 2 + 12.

जैसा कि आप देखते हैं, फ़ंक्शन sumInts कुछ कॉल वास्तव में 0 लौटाते हैं, हालांकि यह अंतिम मान नहीं है क्योंकि कंप्यूटर को अभी भी उस 0 में 5 जोड़ना है, फिर परिणाम के लिए 4, फिर 3, फिर 2, जैसा कि चार अंतिम वाक्यों द्वारा वर्णित है हमारे कंप्यूटर के विचारों के बारे में। ध्यान दें कि रिकर्सन में, कंप्यूटर को केवल रिकर्सिव कॉल की गणना नहीं करना पड़ता है, यह भी याद रखना होगा कि रिकर्सिव कॉल द्वारा लौटाए गए मूल्य के साथ क्या करना है। कम्प्यूटर की मेमोरी का एक विशेष क्षेत्र है जिसे स्टैक कहा जाता है , जहां इस तरह की जानकारी सहेजी जाती है, यह जगह सीमित है और जो कार्य बहुत रिकर्सिव हैं, वे स्टैक को खत्म कर सकते हैं: यह स्टैक ओवरफ्लो है जो इसका नाम हमारी सबसे पसंदीदा वेबसाइट पर देता है।

आपका बयान अंतर्निहित धारणा को प्रतीत होता है कि कंप्यूटर एक रिकर्सिव कॉल करते समय क्या भूल गया था, लेकिन ऐसा नहीं है, यही कारण है कि आपका निष्कर्ष आपके अवलोकन से मेल नहीं खाता है।

2. प्रत्येक पुनरावृत्ति पर 'ए' के ​​मूल्य को मुद्रित करने से एक मूल्य उत्पन्न होता है जो मैं अपेक्षा करता हूं: 2, 3, 4, 5 (जिस बिंदु पर 5 + 1> बी जो पहली स्थिति को पूरा करता है: ए> बी) लेकिन मैं अभी भी देखें कि 14 का मूल्य कैसे प्राप्त किया जाता है।

ऐसा इसलिए है क्योंकि रिटर्न वैल्यू स्वयं नहीं है, लेकिन a के मूल्य का योग और रिकर्सिव कॉल द्वारा लौटाया गया मूल्य है।

जैसा कि शीर्षक बताता है कि मेरे पास एक बहुत ही मौलिक प्रोग्रामिंग प्रश्न है जिसे मैं अभी तक ग्रोक करने में सक्षम नहीं हूं। सभी (अत्यंत चालाक) को फ़िल्टर करना "रिकर्सन को समझने के लिए, आपको पहले रिकर्सन को समझना होगा।" विभिन्न ऑनलाइन धागे से जवाब मैं अभी भी इसे प्राप्त नहीं कर रहा हूँ।

यह समझते हुए कि जब हम नहीं जानते कि हम क्या जानते हैं, तो हम गलत प्रश्न पूछ सकते हैं या सही प्रश्न पूछ सकते हैं, मैं जो कुछ सोचता हूं, वह साझा करूंगा, मेरा प्रश्न यह है कि एक समान दृष्टिकोण वाला कोई व्यक्ति कुछ साझा कर सकता है ज्ञान का थोड़ा सा जो मेरे लिए रिकर्सिव लाइट बल्ब चालू करने में मदद करेगा!

यहां फ़ंक्शन है (सिंटैक्स स्विफ्ट में लिखा गया है):

func sumInts(a: Int, b: Int) -> Int {
    if (a > b) {
        return 0
    } else {
        return a + sumInts(a: a + 1, b: b)
    }
}

हम अपने तर्क के रूप में 2 और 5 का उपयोग करेंगे:

println(sumInts(a: 2, b: 5))

जाहिर है, जवाब 14 है। लेकिन मैं इस बात पर स्पष्ट नहीं हूं कि यह मूल्य कैसे प्राप्त किया जाता है।

ये मेरे 2 हैंगअप हैं:

  1. किसी शर्त को पूरा होने तक फ़ंक्शन को रिकर्सिव कहा जाता है। वह स्थिति ए> बी है। जब यह स्थिति पूरी हो जाती है, तो वापसी करें 0. पहली नज़र में, मुझे उम्मीद है कि वापसी मूल्य 0 होना चाहिए जो स्पष्ट रूप से गलत है।

  2. प्रत्येक पुनरावृत्ति पर 'ए' के ​​मूल्य को प्रिंट करना एक मूल्य उत्पन्न करता है जो मैं अपेक्षा करता हूं: 2, 3, 4, 5 (जिस बिंदु पर 5 + 1> बी जो पहली स्थिति को पूरा करता है: ए> बी) लेकिन मैं अभी भी ' टी देखें कि 14 का मूल्य कैसे प्राप्त किया जाता है।

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

var answer = a;
answer += a+1 until a > b;
return answer;   

तो जादू से बाहर निकलना, मुझे कुछ नहीं मिल रहा है। मुझे यह समझना अच्छा लगेगा कि सिर्फ स्पष्ट रूप से क्या हो रहा है।

अगर कोई दयालु तरीके से समझा सकता है कि इस तरह के कार्य के दौरान तकनीकी रूप से क्या होता है और परिणाम 0 क्यों नहीं होता है और अंततः, a + sumInts(a: a + 1, b: b) = 14 , मैं हमेशा आपके कर्ज में a + sumInts(a: a + 1, b: b) = 14


आपके पास अभी तक कुछ अच्छे उत्तर हैं, लेकिन मैं एक और जोड़ दूंगा जो एक अलग tack लेता है।

सबसे पहले, मैंने सरल रिकर्सिव एल्गोरिदम पर कई लेख लिखे हैं जिन्हें आप दिलचस्प पा सकते हैं; देख

http://ericlippert.com/tag/recursion/

http://blogs.msdn.com/b/ericlippert/archive/tags/recursion/

वे नवीनतम-शीर्ष-शीर्ष क्रम में हैं, इसलिए नीचे से शुरू करें।

दूसरा, अब तक सभी उत्तरों ने कार्य सक्रियण पर विचार करके रिकर्सिव अर्थशास्त्र का वर्णन किया है। प्रत्येक, प्रत्येक कॉल एक नई सक्रियण करता है , और रिकर्सिव कॉल इस सक्रियण के संदर्भ में निष्पादित करता है। यह सोचने का एक अच्छा तरीका है, लेकिन एक और समकक्ष तरीका है: स्मार्ट टेक्स्ट सीच-एंड-प्रतिस्थापन

मुझे अपने फ़ंक्शन को थोड़ा अधिक कॉम्पैक्ट फ़ॉर्म में दोबारा लिखने दें; किसी भी विशेष भाषा में होने के बारे में मत सोचो।

s = (a, b) => a > b ? 0 : a + s(a + 1, b)

मुझे उम्मीद है कि इसका कोई अर्थ है। यदि आप सशर्त ऑपरेटर से परिचित नहीं हैं, तो यह फॉर्म की condition ? consequence : alternative condition ? consequence : alternative और इसका अर्थ स्पष्ट हो जाएगा।

अब हम s(2,5) का मूल्यांकन करना चाहते हैं हम फ़ंक्शन बॉडी के साथ कॉल की टेक्स्ट बदलते हुए ऐसा करते हैं, फिर 2 साथ 2 और b को प्रतिस्थापित करें:

s(2, 5) 
---> 2 > 5 ? 0 : 2 + s(2 + 1, 5)

अब सशर्त मूल्यांकन करें। हम false साथ पाठ 2 > 5 को प्रतिस्थापित false

---> false ? 0 : 2 + s(2 + 1, 5)

अब परिणाम के साथ वैकल्पिक और सभी सच्चे सशर्त के साथ सभी झूठी सशर्तयों को टेक्स्ट रूप से बदलें। हमारे पास केवल झूठी सशर्त हैं, इसलिए हम उस अभिव्यक्ति को वैकल्पिक रूप से वैकल्पिक रूप से प्रतिस्थापित करते हैं:

---> 2 + s(2 + 1, 5)

अब, मुझे उन सभी + संकेतों को टाइप करने के लिए सहेजने के लिए, अपने मूल्य के साथ लगातार अंकगणित को प्रतिस्थापित करें। (यह धोखाधड़ी का थोड़ा सा है, लेकिन मैं सभी कोष्ठकों का ट्रैक रखना नहीं चाहता!)

---> 2 + s(3, 5)

अब खोज के लिए शरीर के साथ खोज और प्रतिस्थापन, 3 लिए 3 और बी के लिए 5 । हम कॉल के लिए प्रतिस्थापन को प्रतिस्थापन में डाल देंगे:

---> 2 + (3 > 5 ? 0 : 3 + s(3 + 1, 5))

और अब हम वही पाठ्यचर्या प्रतिस्थापन चरणों को जारी रखते हैं:

---> 2 + (false ? 0 : 3 + s(3 + 1, 5))  
---> 2 + (3 + s(3 + 1, 5))                
---> 2 + (3 + s(4, 5))                     
---> 2 + (3 + (4 > 5 ? 0 : 4 + s(4 + 1, 5)))
---> 2 + (3 + (false ? 0 : 4 + s(4 + 1, 5)))
---> 2 + (3 + (4 + s(4 + 1, 5)))
---> 2 + (3 + (4 + s(5, 5)))
---> 2 + (3 + (4 + (5 > 5 ? 0 : 5 + s(5 + 1, 5))))
---> 2 + (3 + (4 + (false ? 0 : 5 + s(5 + 1, 5))))
---> 2 + (3 + (4 + (5 + s(5 + 1, 5))))
---> 2 + (3 + (4 + (5 + s(6, 5))))
---> 2 + (3 + (4 + (5 + (6 > 5 ? 0 : s(6 + 1, 5)))))
---> 2 + (3 + (4 + (5 + (true ? 0 : s(6 + 1, 5)))))
---> 2 + (3 + (4 + (5 + 0)))
---> 2 + (3 + (4 + 5))
---> 2 + (3 + 9)
---> 2 + 12
---> 14

हमने जो कुछ किया वह सिर्फ सरल पाठपरक प्रतिस्थापन था । वास्तव में मुझे "2 + 1" के लिए "3" प्रतिस्थापित नहीं किया जाना चाहिए था और तब तक जब तक मुझे नहीं करना था, लेकिन शैक्षणिक रूप से इसे पढ़ने के लिए मुश्किल हो गई होगी।

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

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

तो फिर एक unbounded रिकर्सन क्या है? एक पुनरावर्तन जहां पाठ प्रतिस्थापन बंद नहीं होता है! ध्यान दें कि अंततः हम एक ऐसे कदम पर पहुंचे जहां प्रतिस्थापन करने के लिए और कुछ नहीं था, और फिर हम अंकगणितीय के लिए नियम लागू कर सकते थे।


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

सबसे पहले बेस केस:

sumInts(6, 5) = 0

फिर कॉल स्टैक में बस ऊपर से कॉल :

sumInts(5, 5) == 5 + sumInts(6, 5)
sumInts(5, 5) == 5 + 0
sumInts(5, 5) == 5

फिर कॉल स्टैक में बस ऊपर से कॉल:

sumInts(4, 5) == 4 + sumInts(5, 5)
sumInts(4, 5) == 4 + 5
sumInts(4, 5) == 9

और इसी तरह:

sumInts(3, 5) == 3 + sumInts(4, 5)
sumInts(3, 5) == 3 + 9
sumInts(3, 5) == 12

और इसी तरह:

sumInts(2, 5) == 2 + sumInts(3, 5)
sumInts(4, 5) == 2 + 12
sumInts(4, 5) == 14

ध्यान दें कि हम फ़ंक्शन sumInts(2, 5) == 14 पर हमारी मूल कॉल पर पहुंचे हैं

ऑर्डर जिसमें इन कॉल को निष्पादित किया जाता है:

sumInts(2, 5)
sumInts(3, 5)
sumInts(4, 5)
sumInts(5, 5)
sumInts(6, 5)

जिस क्रम में ये कॉल वापस आती हैं:

sumInts(6, 5)
sumInts(5, 5)
sumInts(4, 5)
sumInts(3, 5)
sumInts(2, 5)

ध्यान दें कि हम इस निष्कर्ष पर पहुंचे कि कैसे कार्य वापस आने के क्रम में कॉल का पता लगाकर कार्य करता है।


प्रत्यावर्तन। कंप्यूटर साइंस रिकर्सन में फिनिट ऑटोमाटा के विषय में गहराई से ढंका हुआ है।

अपने सबसे सरल रूप में यह एक आत्म संदर्भ है। उदाहरण के लिए, यह कहकर कि "मेरी कार एक कार है" एक रिकर्सिव स्टेटमेंट है। समस्या यह है कि कथन एक अनंत पुनरावृत्ति है कि यह कभी खत्म नहीं होगा। "कार" के बयान में परिभाषा यह है कि यह एक "कार" है इसलिए इसे प्रतिस्थापित किया जा सकता है। हालांकि, कोई अंत नहीं है क्योंकि प्रतिस्थापन के मामले में, यह अभी भी "मेरी कार एक कार है" बन जाती है।

यह अलग हो सकता है अगर कथन "मेरी कार एक बेंटले है। मेरी कार नीली है।" इस मामले में कार के लिए दूसरी स्थिति में प्रतिस्थापन "बेंटले" हो सकता है जिसके परिणामस्वरूप "मेरी बेंटले नीली है"। इन प्रकार के प्रतिस्थापन गणितीय रूप से कंप्यूटर विज्ञान में संदर्भ-मुक्त ग्रामर के माध्यम से समझाया गया है।

वास्तविक प्रतिस्थापन एक उत्पादन नियम है। यह देखते हुए कि कथन का प्रतिनिधित्व एस द्वारा किया जाता है और वह कार एक चर है जो "बेंटले" हो सकती है, इस कथन को दोबारा पुनर्निर्मित किया जा सकता है।

S -> "my"S | " "S | CS | "is"S | "blue"S | ε
C -> "bentley"

यह कई तरीकों से बनाया जा सकता है, प्रत्येक के रूप में | मतलब है कि एक विकल्प है। S को उन विकल्पों में से किसी एक द्वारा प्रतिस्थापित किया जा सकता है, और एस हमेशा खाली शुरू होता है। ε मतलब उत्पादन को समाप्त करना है। जैसे S को प्रतिस्थापित किया जा सकता है, तो अन्य चर भी हो सकते हैं (केवल एक ही है और यह C जो "बेंटले" का प्रतिनिधित्व करेगा)।

तो S साथ खाली होना शुरू हो रहा है, और इसे पहली पसंद के साथ बदलना "my"S S बन जाता है

"my"S

S को अभी भी प्रतिस्थापित किया जा सकता है क्योंकि यह एक चर का प्रतिनिधित्व करता है। हम फिर से "मेरा" चुन सकते हैं, या ε इसे समाप्त कर सकते हैं, लेकिन हमारे मूल कथन को जारी रखने देते हैं। हम उस जगह का चयन करते हैं जिसका अर्थ है S को S " "S साथ बदल दिया गया है

"my "S

अगला सी चुनने देता है

"my "CS

और सी में प्रतिस्थापन के लिए केवल एक विकल्प है

"my bentley"S

और एस के लिए फिर से अंतरिक्ष

"my bentley "S

और इसलिए "my bentley is"S , "my bentley is "S , "my bentley is blue"S , "my bentley is blue" (ε के लिए एस को बदलकर उत्पादन समाप्त होता है) और हमने अपने बयानले को फिर से बनाया है" नीला है"।

इन प्रोडक्शंस और प्रतिस्थापन के रूप में रिकर्सन के बारे में सोचें। प्रक्रिया में प्रत्येक चरण अंतिम परिणाम उत्पन्न करने के लिए अपने पूर्ववर्ती को बदल देता है। रिकर्सिव योग के सटीक उदाहरण में 2 से 5 तक, आप उत्पादन के साथ समाप्त होते हैं

S -> 2 + A
A -> 3 + B
B -> 4 + C
C -> 5 + D
D -> 0

यह बन जाता है

2 + A
2 + 3 + B
2 + 3 + 4 + C
2 + 3 + 4 + 5 + D
2 + 3 + 4 + 5 + 0
14

मुझे लगता है कि पुनरावर्ती कार्यों को समझने का सबसे अच्छा तरीका यह महसूस कर रहा है कि उन्हें रिकर्सिव डेटा संरचनाओं को संसाधित करने के लिए बनाया गया है। लेकिन आपके मूल कार्य sumInts(a: Int, b: Int) जो संख्याओं की संख्या को b से संख्याओं की गणना करता है, ऐसा लगता है कि यह एक पुनरावर्ती डेटा संरचना नहीं है ... आइए थोड़ा संशोधित संस्करण sumInts(a: Int, n: Int) जहां n है कि आप कितनी संख्या जोड़ देंगे।

अब, sumInts n , एक प्राकृतिक संख्या पर रिकर्सिव है। अभी भी एक रिकर्सिव डेटा नहीं है, है ना? खैर, पेनो सिद्धांतों का उपयोग करके एक प्राकृतिक संख्या को एक पुनरावर्ती डेटा संरचना माना जा सकता है:

enum Natural = {
    case Zero
    case Successor(Natural)
}

तो, 0 = शून्य, 1 = उत्तराधिकारी (शून्य), 2 = उत्तराधिकारी (उत्तराधिकारी (शून्य)), और इसी तरह।

एक बार आपके पास एआर रिकर्सिव डेटा स्ट्रक्चर हो जाने के बाद, आपके पास फ़ंक्शन के लिए टेम्पलेट होगा। प्रत्येक गैर रिकर्सिव केस के लिए, आप सीधे मूल्य की गणना कर सकते हैं। रिकर्सिव मामलों के लिए आप मानते हैं कि रिकर्सिव फ़ंक्शन पहले से ही काम कर रहा है और मामले की गणना करने के लिए इसका उपयोग करता है, लेकिन तर्क को रद्द कर देता है। प्राकृतिक के मामले में, इसका मतलब है कि Succesor(n) बजाय हम n बजाय, या समकक्ष उपयोग करेंगे, हम n - 1 उपयोग करेंगे।

// sums n numbers beginning from a
func sumInts(a: Int, n: Int) -> Int {
    if (n == 0) {
        // non recursive case
    } else {
        // recursive case. We use sumInts(..., n - 1)
    }
}

अब रिकर्सिव फ़ंक्शन प्रोग्राम के लिए आसान है। सबसे पहले, आधार मामला, n=0 । अगर हम कोई संख्या नहीं जोड़ना चाहते हैं तो हमें क्या करना चाहिए? जवाब निश्चित रूप से 0 है।

रिकर्सिव केस के बारे में क्या? यदि हम n शुरू होने वाली संख्याओं को जोड़ना चाहते हैं और हमारे पास पहले से ही एक काम करने वाला sumInts फ़ंक्शन है जो n-1 लिए काम करता है? खैर, हमें a जोड़ने की आवश्यकता है और उसके बाद sumInts a + 1 sumInts को a + 1 साथ sumInts , इसलिए हम इसके साथ समाप्त होते हैं:

// sums n numbers beginning from a
func sumInts(a: Int, n: Int) -> Int {
    if (n == 0) {
        return 0
    } else {
        return a + sumInts(a + 1, n - 1)
    }
}

अच्छी बात यह है कि अब आपको निम्न स्तर के रिकर्सन में सोचने की आवश्यकता नहीं है। आपको बस यह सत्यापित करने की आवश्यकता है कि:

  • रिकर्सिव डेटा के मूल मामलों के लिए, यह रिकर्सन का उपयोग किए बिना उत्तर की गणना करता है।
  • रिकर्सिव डेटा के रिकर्सिव मामलों के लिए, यह विनाशकारी डेटा पर रिकर्सन का उपयोग करके उत्तर की गणना करता है।

मैं इसे जाने दूंगा।

समीकरण ए + sumInts (ए + 1, बी) निष्पादित, मैं दिखाऊंगा कि अंतिम जवाब 14 है।

//the sumInts function definition
func sumInts(a: Int, b: Int) -> Int {
    if (a > b) {
        return 0
    } else {
        return a + sumInts(a + 1, b)
    }
}

Given: a = 2 and b = 5

1) 2 + sumInts(2+1, 5)

2) sumInts(3, 5) = 12
   i) 3 + sumInts(3+1, 5)
   ii) 4 + sumInts(4+1, 5)
   iii) 5 + sumInts(5+1, 5)
   iv) return 0
   v) return 5 + 0
   vi) return 4 + 5
   vii) return 3 + 9

3) 2 + 12 = 14.

यदि आगे आपके कोई भी प्रश्न हों, तो हमें बताएं।

निम्नलिखित उदाहरण में रिकर्सिव फ़ंक्शंस का एक और उदाहरण यहां दिया गया है।

एक आदमी ने अभी कॉलेज स्नातक किया है।

टी वर्षों में समय की मात्रा है।

सेवानिवृत्त होने से पहले काम की गई कुल वास्तविक संख्या, निम्नानुसार गणना की जा सकती है:

public class DoIReallyWantToKnow 
{
    public int howLongDoIHaveToWork(int currentAge)
    {
      const int DESIRED_RETIREMENT_AGE = 65;
      double collectedMoney = 0.00; //remember, you just graduated college
      double neededMoneyToRetire = 1000000.00

      t = 0;
      return work(t+1);
    }

    public int work(int time)
    {
      collectedMoney = getCollectedMoney();

      if(currentAge >= DESIRED_RETIREMENT_AGE 
          && collectedMoney == neededMoneyToRetire
      {
        return time;
      }

      return work(time + 1);
    }
}

और यह किसी को भी निराश करने के लिए पर्याप्त होना चाहिए, lol। ;-P


रिकर्सन समझने का एक मुश्किल विषय है और मुझे नहीं लगता कि मैं इसे न्यायपूर्वक पूरी तरह से कर सकता हूं। इसके बजाए, मैं आपके यहां मौजूद कोड के विशेष टुकड़े पर ध्यान केंद्रित करने की कोशिश करूंगा और समाधान के काम के बारे में अंतर्ज्ञान का वर्णन करने का प्रयास करूंगा और कोड के परिणाम की गणना कैसे करता है या नहीं।

आपके द्वारा यहां दिया गया कोड निम्न समस्या हल करता है: आप ए से बी के सभी पूर्णांकों के योग को जानना चाहते हैं। आपके उदाहरण के लिए, आप संख्याओं की राशि 2 से 5 तक, समावेशी, जो चाहते हैं

2 + 3 + 4 + 5

एक समस्या को फिर से हल करने का प्रयास करते समय, पहले चरण में से एक को यह समझना चाहिए कि समस्या को एक ही संरचना के साथ छोटी समस्या में कैसे तोड़ना है। तो मान लीजिए कि आप संख्याओं को 2 से 5 तक जोड़ना चाहते हैं, समावेशी। इसे सरल बनाने का एक तरीका यह है कि उपर्युक्त राशि को फिर से लिखा जा सकता है

2 + (3 + 4 + 5)

यहां, (3 + 4 + 5) 3 और 5 के बीच सभी पूर्णांक का योग होता है, समावेशी। दूसरे शब्दों में, यदि आप 2 और 5 के बीच सभी पूर्णांकों के योग को जानना चाहते हैं, तो 3 और 5 के बीच सभी पूर्णांकों की गणना करके प्रारंभ करें, फिर 2 जोड़ें।

तो आप 3 और 5 के बीच सभी पूर्णांक के योग की गणना कैसे करते हैं? खैर, वह राशि है

3 + 4 + 5

इसके बजाय इसके बारे में सोचा जा सकता है

3 + (4 + 5)

यहां, (4 + 5) 4 और 5 के बीच सभी पूर्णांकों का योग शामिल है। इसलिए, यदि आप 3 और 5 के बीच सभी संख्याओं के योग की गणना करना चाहते हैं, तो आप 4 और 5 के बीच सभी पूर्णांक के योग की गणना करेंगे, फिर 3 जोड़ें।

यहां एक पैटर्न है! यदि आप ए और बी के बीच पूर्णांक के योग की गणना करना चाहते हैं, तो आप निम्न कार्य कर सकते हैं। सबसे पहले, एक + 1 और बी, समावेशी के बीच पूर्णांक के योग की गणना करें। इसके बाद, उस कुल में जोड़ें। आप देखेंगे कि "एक +1 और बी के बीच पूर्णांक के योग की गणना करें, समावेशी" एक ही तरह की समस्या होती है जिसे हम हल करने की कोशिश कर रहे हैं, लेकिन थोड़ा अलग पैरामीटर के साथ। ए से बी तक कंप्यूटिंग करने के बजाय, समावेशी, हम एक + 1 से बी तक कंप्यूटिंग कर रहे हैं। यह एक पुनरावर्ती कदम है - बड़ी समस्या को हल करने के लिए ("ए से बी, समावेशी"), हम समस्या को अपने आप के एक छोटे संस्करण ("एक + 1 से बी, समावेशी" में) को कम करते हैं।

यदि आप ऊपर दिए गए कोड को देखते हैं, तो आप देखेंगे कि इसमें यह कदम है:

return a + sumInts(a + 1, b: b)

यह कोड केवल उपर्युक्त तर्क का अनुवाद है - यदि आप एक से बी तक sumInt चाहते हैं, समावेशी, + 1 से बी को संक्षेप में शुरू करना, समावेशी (यह sumInt के लिए रिकर्सिव कॉल है), फिर a जोड़ें।

बेशक, स्वयं ही यह दृष्टिकोण वास्तव में काम नहीं करेगा। उदाहरण के लिए, आप 5 और 5 के बीच सभी पूर्णांक के योग की गणना कैसे करेंगे? खैर, हमारे वर्तमान तर्क का उपयोग करके, आप 6 और 5 के बीच सभी पूर्णांकों की गणना की गणना करेंगे, फिर 5 जोड़ें। तो आप 6 और 5 के बीच सभी पूर्णांक के योग की गणना कैसे करते हैं? खैर, हमारे वर्तमान तर्क का उपयोग करके, आप 7 और 5 के बीच सभी पूर्णांकों की गणना की गणना करेंगे, फिर 6 जोड़ें। आपको यहां एक समस्या दिखाई देगी - यह बस चलती है और जा रही है!

रिकर्सिव समस्या हल करने में, समस्या को सरल बनाने के लिए कुछ तरीका होना चाहिए और इसके बजाय बस इसे सीधे हल करें। आम तौर पर, आपको एक साधारण मामला मिल जाएगा जहां उत्तर तुरंत निर्धारित किया जा सकता है, फिर जब वे उत्पन्न होते हैं तो सरल मामलों को हल करने के लिए अपने समाधान की संरचना करें। इसे आम तौर पर बेस केस या रिकर्सिव आधार कहा जाता है।

तो इस विशेष समस्या में आधार मामला क्या है? जब आप ए से बी तक पूर्णांक को जोड़ते हैं, समावेशी, यदि बी से बड़ा होता है, तो उत्तर 0 है - सीमा में कोई संख्या नहीं है! इसलिए, हम अपने समाधान को निम्नानुसार ढांचे देंगे:

  1. यदि ए> बी, तो उत्तर 0 है।
  2. अन्यथा (एक ≤ बी), निम्नानुसार उत्तर प्राप्त करें:
    1. एक +1 और बी के बीच पूर्णांक के योग की गणना करें।
    2. उत्तर पाने के लिए एक जोड़ें।

अब, इस स्यूडोकोड की तुलना अपने वास्तविक कोड से करें:

func sumInts(a: Int, b: Int) -> Int {
    if (a > b) {
        return 0
    } else {
        return a + sumInts(a + 1, b: b)
    }
}

ध्यान दें कि स्यूडोकोड और इस वास्तविक कोड में उल्लिखित समाधान के बीच लगभग एक-एक-एक नक्शा है। पहला चरण आधार मामला है - यदि आप संख्याओं की खाली सीमा के योग के लिए पूछते हैं, तो आपको 0 मिलते हैं। अन्यथा, + 1 और बी के बीच की राशि की गणना करें, फिर एक जोड़ें।

अब तक, मैंने कोड के पीछे सिर्फ एक उच्च स्तरीय विचार दिया है। लेकिन आपके पास दो अन्य, बहुत अच्छे प्रश्न थे। सबसे पहले, यह हमेशा 0 क्यों नहीं लौटाता है, यह देखते हुए कि समारोह 0 वापस लौटने के लिए कहता है यदि कोई> बी? दूसरा, 14 वास्तव में कहां से आता है? आइए इन्हें बदले में देखें।

चलो एक बहुत ही सरल मामला आज़माएं। यदि आप sumInts(6, 5) कहते हैं तो क्या होता है? इस मामले में, कोड के माध्यम से ट्रेसिंग, आप देखते हैं कि फ़ंक्शन सिर्फ 0 देता है। यह करने के लिए सही बात है - श्रेणी में कोई संख्या नहीं है। अब, कुछ कठिन कोशिश करें। क्या होता है जब आप sumInts(5, 5) ? खैर, यहां क्या होता है:

  1. आप sumInts(5, 5) । हम else शाखा में आते हैं, जो `ए + sumInts (6, 5) के मूल्य वापस कर देता है।
  2. sumInts(5, 5) निर्धारित करने के लिए sumInts(6, 5) लिए, हमें जो करना है हम उसे रोकने और sumInts(6, 5) कॉल करने की sumInts(6, 5)
  3. sumInts(6, 5) बुलाया जाता है। यह शाखा में प्रवेश करता है और 0 देता है। हालांकि, sumInts इस उदाहरण को sumInts sumInts(5, 5) द्वारा बुलाया गया था, इसलिए वापसी मूल्य को शीर्ष-स्तर कॉलर पर नहीं sumInts(5, 5) वापस भेज दिया sumInts(5, 5)
  4. sumInts(5, 5) अब 5 + sumInts(6, 5) वापस पाने के लिए 5 + sumInts(6, 5) गणना कर सकते हैं। फिर यह इसे शीर्ष-स्तरीय कॉलर पर लौटा देता है।

ध्यान दें कि मूल्य 5 कैसे बनाया गया था। हमने sumInts एक सक्रिय कॉल के साथ sumInts । उसने एक और रिकर्सिव कॉल बंद कर दिया, और उस कॉल द्वारा लौटाए गए मूल्य को सूचनाओं को वापस sumInts(5, 5) सूचित किया गया। sumInts(5, 5) कॉल ने बदले में कुछ गणना की और कॉलर को एक मान वापस कर दिया।

यदि आप sumInts(4, 5) साथ प्रयास करते हैं, तो यह होगा कि क्या होगा:

  • sumInts(4, 5) 4 + sumInts(5, 5) वापस करने की कोशिश करता है। ऐसा करने के लिए, यह sumInts(5, 5)
    • sumInts(5, 5) 5 + sumInts(6, 5) वापस करने की कोशिश करता है। ऐसा करने के लिए, यह sumInts(6, 5)
    • sumInts(6, 5) 0 वापस sumInts(5, 5).</li> <li> पर sumInts(5, 5).</li> <li> sumInts (5, 5) now has a value for sumInts (6, 5) , namely 0. It then returns now has a value for , namely 0. It then returns 5 + 0 = 5`।
  • sumInts(4, 5) अब sumInts(5, 5) , अर्थात् sumInts(5, 5) लिए एक मान है। फिर यह 4 + 5 = 9

दूसरे शब्दों में, जो मूल्य लौटाया जाता है वह एक समय में मूल्यों को एक साथ जोड़कर बनाया जाता है, हर बार एक विशेष रिकर्सिव कॉल द्वारा एक मूल्य को sumInts पर sumInts और उसके वर्तमान मूल्य को जोड़ता a । जब रिकर्सन बोतलबंद हो जाता है, तो गहरा कॉल 0 देता है। हालांकि, वह मान तुरंत रिकर्सिव कॉल श्रृंखला से बाहर नहीं निकलता है; इसके बजाए, यह सिर्फ ऊपर की ओर एक परत को रिकर्सिव कॉल पर मान देता है। इस तरह, प्रत्येक रिकर्सिव कॉल सिर्फ एक और संख्या में जोड़ता है और श्रृंखला में इसे ऊपर देता है, जो समग्र सारांश के साथ समाप्त होता है। एक अभ्यास के रूप में, sumInts(2, 5) लिए इसे ढूंढने का प्रयास करें, जो आप शुरू करना चाहते हैं।

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


A little bit off-topic, I know, but... try looking up recursion in Google... You'll see by example what it means :-)

Earlier versions of Google returned the following text (cited from memory):

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

See Recursion

On September 10th 2014, the joke about recursion has been updated:

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

Did you mean: Recursion

For another reply, see this answer .


Many of the answers above are very good. A useful technique for solving recursion though, is to spell out first what we want to do and code as a human would solve it . In the above case, we want to sum up a sequence of consecutive integers (using the numbers from above):

2, 3, 4, 5  //adding these numbers would sum to 14

Now, note that these lines are confusing (not wrong, but confusing).

if (a > b) {
    return 0 
}

Why the test a>b ?, and why return 0

Let's change the code to reflect more closely what a human does

func sumInts(a: Int, b: Int) -> Int {
  if (a == b) {
    return b // When 'a equals b' I'm at the most Right integer, return it
  }
  else {
    return a + sumInts(a: a + 1, b: b)
  }
}

Can we do it even more human like? हाँ! Usually we sum up from left to right (2+3+...). But the above recursion is summing from right to left (...+4+5). Change the code to reflect it (The - can be a little intimidating, but not much)

func sumInts(a: Int, b: Int) -> Int {
  if (a == b) {
    return b // When I'm at the most Left integer, return it
  }
  else {
    return sumInts(a: a, b: b - 1) + b
  }
}

Some may find this function more confusing since we are starting from the 'far' end, but practicing can make it feel natural (and it is another good 'thinking' technique: Trying 'both' sides when solving a recursion). And again, the function reflects what a human (most?) does: Takes the sum of all left integers and adds the 'next' right integer.


One really good tip I came across in learning and really understanding recursion is to spend some time learning a language that doesn't have any form of loop construct other than via recursion. That way you'll get a great feel for how to USE recursion via practice.

I followed http://www.htdp.org/ which, as well as being a Scheme tutorial, is also a great introduction on how to design programs in terms of the architecture and design.

But basically, you need to invest some time. Without a 'firm' grasp of recursion certain algorithms, such as backtracking, will always seem 'hard' or even 'magic' to you. So, persevere. :-D

I hope this helps and Good Luck!


There are already a lot of good answers. Still I am giving a try.
When called, a function get a memory-space allotted, which is stacked upon the memory-space of the caller function. In this memory-space, the function keeps the parameters passed to it, the variables and their values. This memory-space vanishes along with the ending return call of the function. As the idea of stack goes, the memory-space of the caller function now becomes active.

For recursive calls, the same function gets multiple memory-space stacked one upon another. That's all. The simple idea of how stack works in memory of a computer should get you through the idea of how recursion happens in implementation.


Think recursion as a multiple clones doing same thing...

You ask to clone[1]: "sum numbers between 2 and 5"

+ clone[1]               knows that: result is 2 + "sum numbers between 3 and 5". so he asks to clone[2] to return: "sum numbers between 3 and 5"
|   + clone[2]           knows that: result is 3 + "sum numbers between 4 and 5". so he asks to clone[3] to return: "sum numbers between 4 and 5"
|   |   + clone[3]       knows that: result is 4 + "sum numbers between 5 and 5". so he asks to clone[4] to return: "sum numbers between 5 and 5"
|   |   |   + clone[4]   knows that: result is 5 + "sum numbers between 6 and 5". so he asks to clone[5] to return: "sum numbers between 6 and 5"
|   |   |   |   clone[5] knows that: he can't sum, because 6 is larger than 5. so he returns 0 as result.
|   |   |   + clone[4]   gets the result from clone[5] (=0)  and sums: 5 + 0,  returning 5
|   |   + clone[3]       gets the result from clone[4] (=5)  and sums: 4 + 5,  returning 9
|   + clone[2]           gets the result from clone[3] (=9)  and sums: 3 + 9,  returning 12
+ clone[1]               gets the result from clone[2] (=12) and sums: 2 + 12, returning 14

and voilá!!





language-agnostic