यह रिकर्सन कैसे काम करता है?

Question

इस सुवक्ता जावास्क्रिप्ट से एक उदाहरण है:

संख्या 1 से शुरू करने और बार-बार या तो 3 से 5 या गुणा जोड़ कर, नए नंबर की एक अनंत राशि का उत्पादन किया जा सकता है। आप एक फ़ंक्शन कैसे लिखेंगे, जो किसी संख्या को दिया गया है, जोड़ों और गुणाओं के अनुक्रम को खोजने का प्रयास करता है जो उस संख्या का उत्पादन करते हैं?

मैं मुसीबत को समझने के प्रत्यावर्तन यहाँ काम कर रहा है, अगर किसी को दो बार कैसे पता बुलाया जा रहा है या कुछ अन्य विवरण बाहर लिख सकता है सोच रहा हो रही है।

function findSequence(goal) { 
    function find(start, history) { 
    if (start == goal) 
     return history; 
    else if (start > goal) 
     return null; 
    else 
     return find(start + 5, "(" + history + " + 5)") || 
      find(start * 3, "(" + history + " * 3)"); 
    } 
    return find(1, "1"); 
} 

console.log(findSequence(24)); // => (((1 * 3) + 5) * 3) 

Answer 1

समारोह बल्कि एक सरल brute force searchbacktracking साथ चलाता है: प्रत्येक मंगलाचरण स्तर यह संख्या के लिए 5 जोड़ने की कोशिश करता है पर, और यदि उसके एवज में नंबर से शुरू लक्ष्य के लिए आप हो जाता है देखते हैं। यदि ऐसा होता है, तो परिणाम वापस आ जाता है; अन्यथा, संख्या द्वारा गुणा किया गया है, और लक्ष्य की खोज उस नए नंबर से जारी है। जैसे-जैसे रिकर्सन चलता है, संख्या उत्पन्न करने वाली अभिव्यक्ति का पाठ प्रस्तुतिकरण अगले आमंत्रण स्तर पर जाता है।

14 के लिए खोज इस प्रकार है:

(1, "1") 
(5, "1+5") 
(10, "(1+5)+5") 
(15, "((1+5)+5)+5") <<= Fail 
(30, "((1+5)+5)*3") <<= Fail 
(15, "(1+5)*3") <<= Fail 
(3, "1*3") 
(8, "(1*3)+5") 
(13, "((1*3)+5)+5") 
(18, "(((1*3)+5)+5)+5") <<= Fail 
(39, "(((1*3)+5)+5)*3") <<= Fail 
(24, "((1*3)+5)*3") <<= Fail 
(9, "(1*3)*3") 
(14, "((1*3)*3)+5) <<= Success! 

Answer 2

इस समारोह 1 के साथ शुरू होता है और फिर या तो यह करने के लिए 5 जोड़ सकते हैं या तो उस लक्ष्य के बराबर है 3. से गुणा करने की कोशिश करता, समारोह समाप्त हो जाता है और अभिव्यक्ति बाहर प्रिंट पाया। यदि नहीं, तो यह उस स्तर पर मूल्य के साथ खुद को फिर से कॉल करता है जब तक कोई मिलान नहीं मिलता है या जब तक मान बहुत अधिक न हो जाए।

क्या इससे मदद मिलती है?

Answer 3

कोई भी दो बार लिख सकता है कि कैसे खोजा जा रहा है।

ये रहा:

find(1, "1") -> find(3, "(1 * 3)") 
      -> find(8, "((1 * 3) + 5)") 
      -> find(24, "(((1 * 3) + 5) * 3)") 

Answer 4

सीधे शब्दों में कहा जाए तो find(start,goal) रिकर्सिवली जब तक goal मूल्य तक पहुँच नहीं किया गया है बुलाया जाएगा। प्रत्येक कॉल में, वर्तमान संख्या या तो 3 से गुणा हो जाएगी या 5 से बढ़ी जाएगी। history परिवर्तनीय संचालन के साथ स्ट्रिंग को संग्रहीत करता है। वर्तमान ऑपरेशन प्रत्येक पुनरावृत्ति में उस स्ट्रिंग में जोड़ा जाता है।

स्पष्टीकरण:

function findSequence(goal) { 

    // This inner function will be called recursively. 
    // 'history' is a string with the current operations "stack" 
    function find(start, history) { 
    if (start == goal)   // if goal is achieved, simply return the result 
           // ending the recursion 
     return history; 
    else if (start > goal)  // return null to end the recursion 
     return null; 
    else 
     // One of the 'find' calls can return null - using || 
     // ensures we'll get the right value. 
     // Null will be returned if 'start+5' or 'start*3' is 
     // greater than our 'goal' (24 in your example). 
     // The following line is where a recursion happens. 
     return find(start + 5, "(" + history + " + 5)") || 
      find(start * 3, "(" + history + " * 3)"); 
    } 

    // Start with '1' 
    return find(1, "1"); 
} 

Answer 5

5 जोड़ने और एक द्विआधारी पेड़ की तरह 3 से गुणा करने के अनंत संयोजन के Think। शीर्ष पर गणना करने के लिए सबसे आसान संख्या है, 1 (असल में "कोई कदम आवश्यक नहीं" उत्तर)। नीचे एक स्तर और बाईं ओर 1+5 है, और दाईं ओर 1*3 है। प्रत्येक स्तर पर समीकरण एक नए मूल्य (अधिक जटिल इतिहास के साथ) का समाधान करता है। यह समीकरण उस पेड़ के माध्यम से नेविगेट कर रहा है जब तक कि यह goal के बराबर नोड पाता है। पेड़ की एक शाखा पर एक नोड एक मूल्य के अपने लक्ष्य से अधिक उत्पादन करता है, तो यह रिटर्न अशक्त (इस प्रकार है कि शाखा और नीचे recusing रोकने, इस वजह से दोनों के संचालन सिर्फ इसलिए एक बार आप अधिक से अधिक कोई तुलना में अंत मूल्य में वृद्धि देखने के लिए इंगित करें), यदि नोड का मान लक्ष्य के बराबर होता है तो इसे उत्तर के रूप में वापस किया जाता है (जिस पथ के साथ वह वहां पहुंचता था)। जब मान कम से कम होता है तो दोनों पथ संभावित रूप से उत्तर धारण कर सकते हैं ताकि यह प्रत्येक पर मिल सके। यहाँ जहां जावास्क्रिप्ट की "truthy" बूलियन तर्क में आता है। || (या) ऑपरेटर का उपयोग करके जावास्क्रिप्ट पहले पेड़ के +5 ओर नीचे दिखेगा। यदि 0 या शून्य वापस लौटाए जाते हैं तो दूसरी कॉल (*3 को देखने के लिए) निष्पादित की जाएगी। किसी भी वापसी के लिए एक गैर false मूल्य का आकलन करती है तो यह ढेर तक लौटाए जाएगा और खोज खत्म हो जाएगा।

Answer 6

find के शरीर तीन से बाहर निकलने के रास्तों, दो कि एक शर्त है कि प्रत्यावर्तन बंद हो जाता है और एक कि recurses के अनुरूप है:

if (start == goal) 
    return history; // stop recursion: solution found 
else if (start > goal) 
    return null; // stop recursion: solution impossible 
else 
    // ... 

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

return find(start + 5, "(" + history + " + 5)") || 
     find(start * 3, "(" + history + " * 3)"); 

तो यहां क्या हो रहा है?

सबसे पहले, ध्यान दें कि इनमें से प्रत्येक find कॉल या तो एक गैर-खाली स्ट्रिंग (संचालन का इतिहास) या null पर मूल्यांकन करेगा। चूंकि एक गैर-खाली स्ट्रिंग एक "सच्चाई" मान है और null एक "झूठा" मान है, इसलिए हम || ऑपरेटर के साथ उनसे जुड़कर इसका लाभ उठाते हैं; यह ऑपरेटर अपने पहले ऑपरेंड का मूल्यांकन करता है यदि यह सच है, अन्यथा दूसरे ऑपरेंड के लिए।

इसका मतलब है कि पहली बार रिकर्सन शाखा (+5) का मूल्यांकन पहले किया जाएगा। यदि संचालन का अनुक्रम है जो 5 जोड़कर शुरू होता है और लक्ष्य तक पहुंच जाता है तो इस अनुक्रम का विवरण वापस कर दिया जाएगा। अन्यथा, यदि कोई अनुक्रम है जो 3 से गुणा करके शुरू होता है और लक्ष्य तक पहुंच जाता है तो उस इतिहास का विवरण वापस कर दिया जाएगा।

यदि लक्ष्य तक पहुंचने का कोई तरीका नहीं है तो वापसी मूल्य दूसरी शाखा द्वारा उत्पादित null होगा।

Answer 7

यह जानने के लिए आपके लिए सबसे अच्छा तरीका जावास्क्रिप्ट डीबगर में कोड के माध्यम से पता लगाना होगा।

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

बस debugger; कथन जोड़ें जहां आप कोड को रोकना चाहते हैं। एक अच्छा स्थान हो बस से पहले आप findSequence() कहेंगे:

debugger; 
console.log(findSequence(24)); 

अब खुला डेवलपर उपकरण के साथ क्रोम में अपने पेज लोड। आपका कोड उस debugger; लाइन पर रुक जाएगा। वह बटन ढूंढें जो आपको अपने कोड में कदम (वॉच एक्सप्रेशन पैनल के ऊपर दाईं ओर) देता है। findSequence() कॉल में जाने के लिए उस बटन पर क्लिक करें। प्रत्येक बार जब आप इसे क्लिक करते हैं, तो यह कोड की अगली पंक्ति में कदम रखेगा, जिसमें प्रत्येक रिकर्सिव कॉल में शामिल होना शामिल है।

जब भी कोड बंद हो जाता है, तो आप इसे देखने के लिए किसी भी चर पर माउस को घुमा सकते हैं, या दाईं ओर पैनल में चर को देख सकते हैं। एक कॉल स्टैक भी है जो आपको दिखाएगा कि आप रिकर्सिव कॉल में कहां हैं।

मुझे यकीन है कि कोई आपके लिए रिकर्सन समझा सकता है, लेकिन अगर आप वास्तव में डीबगर में अपने कोड से कदम उठाकर अनुभव करते हैं तो आप बहुत कुछ सीखेंगे।

Answer 8

आप सुंदर मुद्रण सामान से छुटकारा पाने के लिए, कोड थोड़ा आसान है पढ़ने के लिए:

function findSequence(goal) { 
    function find(start) { 
     if (start == goal) { 
      return true; 
     } else if (start > goal) { 
      return false; 
     } else { 
      return find(start + 5) || find(start * 3); 
     } 
    } 

    return find(1); 
} 

बाहरी समारोह, findSequence, गतिशील रूप से एक नई समारोह find कहा जाता है जहां goal से लिया जाता है बनाता है पैरेंट समारोह का दायरा। आप इसे इस तरह फिर से लिख सकता है स्पष्टता के लिए:

function findSequence(start, goal) { 
    if (start == goal) { 
     return true; 
    } else if (start > goal) { 
     return false; 
    } else { 
     return findSequence(start + 5, goal) || findSequence(start * 3, goal); 
    } 
} 

अब, आप अधिक स्पष्ट रूप से क्या होता है एक छोटे से देख सकते हैं। रिकर्सिव चरण अंतिम return कथन में है, जो प्रत्येक चरण में start + 5 और start * 3 दोनों की कोशिश करता है और शाखा को चुनता है जो अंततः true देता है।

हाथ से findSequence(1, 23) के तर्क का पालन करें और आप समझेंगे कि यह कैसे काम करता है।

Answer 9

इतिहास पैरामीटर छोड़ने दें, हम बाद में इसे प्राप्त करेंगे।

रिकर्सन सभी संभावित परिचालनों में फैलता है। यह 1 के साथ start के साथ शुरू होता है।

1. हम पहले अगर हम हमारे गंतव्य तक पहुँच की जाँच करें:, goal अगर हम true लौट did-, पथ हम ले लिया जिसका अर्थ है सही है।

2. दूसरा, हम पूछते हैं- क्या हम बाध्य (goal) पर गए थे? अगर हमने किया, तो हमें false वापस करना चाहिए क्योंकि यह पथ हमारी मदद नहीं कर सकता है।

3. अन्यथा, की सुविधा देता है हमारे दोनों possiblities कोशिश (हम का उपयोग करें या क्योंकि हम कम से कम एक की जरूरत है):

   • कॉल एक ही समारोह है, लेकिन करने के लिए start + 5
   • कॉल एक ही समारोह start सेट है, लेकिन सेट startstart * 3 को

इतिहास चर कदम हम ले रहता है। तो यदि कोई फ़ंक्शन कॉल start == goal पहचानता है तो यह इसे वापस कर देता है।

Answer 10

goal अपने उद्देश्य है और यह 24

goal == 24 

पर सेट है अब हम इस आंतरिक समारोह find() अगर start 24 के बराबर है देखने के लिए जाँच करता है कि है, यह। यह भी अगर शुरू अधिक से अधिक तो 24 है यह भी सच नहीं है देखने के लिए जाँच करता है,

find(1 "1") 
1 == 24 //false 
1 > 24 //false 

तो यह किसी और बयान जहां दोबारा इसे कॉल मारता है, इस जहां else if() से शून्य मान में आता है।अगर वापसी शून्य है तो यह || भाग तब तक जब तक यह सही जवाब नहीं मिल जाता है।

return find(6, "(1 + 5)") 
     find(11, "((1 + 5) + 5)") 
     find(16, "(((1 + 5) + 5) +5)") 
     find(21, "((((1+5) + 5) + 5) +5)") 
     //next one returns null! 
     //tries * by 3 on 21, 16, and 11 all return null 

इसलिए यह ||

return find(3, "(1 * 3)") 
     find(8, "((1 * 3) +5)") 
     //some calls down +5 path but that returns null 
     find(24, "(((1 * 3) + 5) * 3)") 

अंत में! हमारे पास एक सच्ची वापसी है और हमने इतिहास में हमने जिस मार्ग को लिया है, उसे लॉग किया है।

Answer 11

आप सिर्फ इस यह पता लगाने की आमंत्रण के वृक्ष बनाने के लिए:

findSequence(24) 
    find(1, "1") 
     find(1 + 5, "(1 + 5)") 
      find(6 + 5, "((1 + 5) + 5)") 
       find(11 + 5, "(((1 + 5) + 5) + 5)" 
        find(16 + 5, "((((1 + 5) + 5) + 5) + 5)" 
         find(21 + 5, "(((((1 + 5) + 5) + 5) + 5) + 5)" 
          start > goal: return null 
         find(21 * 3, "(((((1 + 5) + 5) + 5) + 5) + 5)" 
          start > goal: return null 
        find(16 * 3, "((((1 + 5) + 5) + 5) * 3)" 
         start > goal: return null 
       find(11 * 3, "(((1 + 5) + 5) * 3)" 
        start > goal: return null 
      find(6 * 3, "((1 + 5) * 3)") 
       find(18 + 5, "(((1 + 5) * 3) + 5)") 
        find(23 + 5, "((((1 + 5) * 3) + 5) + 5)") 
         start > goal: return null 
        find(23 * 3, "((((1 + 5) * 3) + 5) * 3)") 
         start > goal: return null 
       find(18 * 3, "(((1 + 5) * 3) * 3)") 
        start > goal: return null 
     find(1 * 3, "(1 * 3)") 
      find(3 + 5, "((1 * 3) + 5)") 
       find(8 + 5, "(((1 * 3) + 5) + 5)") 
        find(13 + 5, "((((1 * 3) + 5) + 5) + 5)") 
         find(18 + 5, "(((((1 * 3) + 5) + 5) + 5) + 5)") 
          find(23 + 5, "((((((1 * 3) + 5) + 5) + 5) + 5) + 5)") 
           start > goal: return null 
          find(23 + 5, "((((((1 * 3) + 5) + 5) + 5) + 5) + 5)") 
           start > goal: return null 
         find(18 * 3, "(((((1 * 3) + 5) + 5) + 5) * 3)") 
          start > goal: return null 
        find(13 * 3, "((((1 * 3) + 5) + 5) * 3)") 
         start > goal: return null 
       find(8 * 3, "(((1 * 3) + 5) * 3)") 
        return "(((1 * 3) + 5) * 3)" 
      find(3 * 3, "((1 * 3) * 3)") 
       find(9 + 5, "(((1 * 3) * 3) + 5)") 
        find(14 + 5, "((((1 * 3) * 3) + 5) + 5)") 
         find(19 + 5, "(((((1 * 3) * 3) + 5) +5) + 5)") 
         return "(((((1 * 3) * 3) + 5) +5) + 5)" 
         find(19 * 3, "((((1 * 3) * 3) + 5) *3)") 
          start > goal: return null 
       find(9 * 3, "(((1 * 3) * 3) * 3)") 
        start > goal: return null