कैसे लूप के लिए रिकर्सन वर्क्स के अंदर काम करता है

Question

मैं रिकर्सन और इस कोड स्निपेट को समझने की कोशिश करने के लिए नया हूं। मैं एक परीक्षा के लिए पढ़ रहा हूं, और यह एक "समीक्षक" है जो मुझे स्टैंडफोर्ड 'सीआईएस एजुकेशन लाइब्रेरी (निक पार्लैंट द्वारा बाइनरी पेड़ से) से मिला है।

मैं अवधारणा को समझता हूं, लेकिन जब हम लूप के अंदर रिकर्स कर रहे हैं, तो यह सब उड़ाता है! क्रिप्या मेरि सहायता करे। धन्यवाद।

countTrees() समाधान (C/C++)

/* 
For the key values 1...numKeys, how many structurally unique 
binary search trees are possible that store those keys. 
Strategy: consider that each value could be the root. 
Recursively find the size of the left and right subtrees. 
*/ 

int countTrees(int numKeys) { 
    if (numKeys <=1) { 
     return(1); 
    } 

    // there will be one value at the root, with whatever remains 
    // on the left and right each forming their own subtrees. 
    // Iterate through all the values that could be the root... 

    int sum = 0; 
    int left, right, root; 

    for (root=1; root<=numKeys; root++) { 
     left = countTrees(root - 1); 
     right = countTrees(numKeys - root); 
     // number of possible trees with this root == left*right 
     sum += left*right; 
    } 

    return(sum); 
} 

Answer 1

कल्पना कीजिए पाश "ठहराव पर" डाल जा रहा है, जबकि आप समारोह कॉल करने के लिए जाना।

सिर्फ इसलिए कि फ़ंक्शन एक रिकर्सिव कॉल होता है, यह आपके द्वारा लूप के भीतर कॉल किए जाने वाले किसी भी फ़ंक्शन के समान काम करता है।

नया रिकर्सिव कॉल इसे for लूप शुरू करता है और फिर, कार्यों को फिर से कॉल करते समय रोकता है, और इसी तरह।

Answer 2

आप बेस केस से ऊपर की ओर काम कर सकते हैं।

तो, बेस केस के लिए आपके पास 1 (या कम) नोड्स हैं। केवल 1 संरचनात्मक अद्वितीय पेड़ है जो 1 नोड के साथ संभव है - यह नोड स्वयं ही है। इसलिए, यदि numKeys 1 से कम या बराबर है, तो बस 1.

मान लें कि आपके पास 1 से अधिक कुंजी हैं। खैर, फिर उन चाबियों में से एक जड़ है, कुछ वस्तुएं बाएं शाखा में हैं और कुछ वस्तुएं सही शाखा में हैं।

उन बाएं और दाएं शाखाएं कितनी बड़ी हैं? वैसे यह मूल तत्व क्या है पर निर्भर करता है। चूंकि आपको संभावित पेड़ों की कुल राशि पर विचार करने की आवश्यकता है, इसलिए हमें सभी विन्यास (सभी संभावित रूट मान) पर विचार करना होगा - इसलिए हम सभी संभावित मूल्यों पर पुन: प्रयास करते हैं।

प्रत्येक पुनरावृत्ति के लिए, हम जानते हैं कि मैं रूट पर हूं, i-1 नोड बाएं शाखा पर हैं और numKeys - मैं नोड सही शाखा पर हैं। लेकिन, ज़ाहिर है, हमारे पास पहले से ही एक ऐसा फ़ंक्शन है जो नोड्स की संख्या के अनुसार पेड़ कॉन्फ़िगरेशन की कुल संख्या की गणना करता है! यह वह कार्य है जिसे हम लिख रहे हैं। तो, रिकर्सिव बाएं और दाएं उपट्री के संभावित वृक्ष कॉन्फ़िगरेशन की संख्या प्राप्त करने के लिए फ़ंक्शन को कॉल करें। रूट पर मेरे साथ संभव पेड़ों की कुल संख्या तब उन दो संख्याओं का उत्पाद है (बाएं उपट्री के प्रत्येक कॉन्फ़िगरेशन के लिए, सभी संभव दाएं उपट्री हो सकते हैं)।

आप इसे पूरा करने के बाद, आप कर चुके हैं।

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

Answer 3

देखो इस तरह से: प्रारंभिक कॉल के लिए 3 संभावित मामलों नहीं है:

numKeys = 0 
numKeys = 1 
numKeys > 1 

0 और 1 मामलों सरल कर रहे हैं - समारोह बस 1 वापस आती है और आपका काम हो गया।

sum = 0 
loop(root = 1 -> 2) 
    root = 1: 
     left = countTrees(1 - 1) -> countTrees(0) -> 1 
     right = countTrees(2 - 1) -> countTrees(1) -> 1 
     sum = sum + 1*1 = 0 + 1 = 1 
    root = 2: 
     left = countTrees(2 - 1) -> countTrees(1) -> 1 
     right = countTrees(2 - 2) -> countTrees(0) -> 1 
     sum = sum + 1*1 = 1 + 1 = 2 

output: 2 

numKeys = 3 के लिए

: numkeys 2 के लिए, आप के साथ अंत

sum = 0 
loop(root = 1 -> 3): 
    root = 1: 
     left = countTrees(1 - 1) -> countTrees(0) -> 1 
     right = countTrees(3 - 1) -> countTrees(2) -> 2 
     sum = sum + 1*2 = 0 + 2 = 2 
    root = 2: 
     left = countTrees(2 - 1) -> countTrees(1) -> 1 
     right = countTrees(3 - 2) -> countTrees(1) -> 1 
     sum = sum + 1*1 = 2 + 1 = 3 
    root = 3: 
     left = countTrees(3 - 1) -> countTrees(2) -> 2 
     right = countTrees(3 - 3) -> countTrees(0) -> 1 
     sum = sum + 2*1 = 3 + 2 = 5 

output 5 

और इतने पर।यह फ़ंक्शन ओ (एन^2) की संभावना है, क्योंकि प्रत्येक एन कुंजी के लिए, आप 2 * एन -1 रिकर्सिव कॉल चला रहे हैं, जिसका अर्थ है कि इसका रनटाइम बहुत तेज़ी से बढ़ेगा।

Answer 4

प्रत्येक कॉल की अपनी चरणीय जगह होती है, जैसा कि कोई उम्मीद करेगा। जटिलता इस तथ्य से आती है कि फ़ंक्शन का निष्पादन निष्पादित करने के लिए "बाधित" होता है- एक ही फ़ंक्शन। इस कोड:

for (root=1; root<=numKeys; root++) { 
     left = countTrees(root - 1); 
     right = countTrees(numKeys - root); 
     // number of possible trees with this root == left*right 
     sum += left*right; 
    } 

सादा सी में इस तरह से फिर से लिखा जा सकता है:

root = 1; 
Loop: 
    if (!(root <= numkeys)) { 
     goto EndLoop; 
    } 

    left = countTrees(root -1); 
    right = countTrees (numkeys - root); 
    sum += left * right 

    ++root; 
    goto Loop; 
EndLoop: 
// more things... 

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

Answer 5

बस है कि इस तरह numKeys, sum, left, right, root के रूप में सभी स्थानीय चर, ढेर स्मृति में हैं याद करने के लिए। जब आप रिकर्सिव फ़ंक्शन की n-th गहराई पर जाते हैं, तो इन स्थानीय चर के n प्रतियां होंगी। जब यह एक गहराई को निष्पादित करता है, तो इन चर की एक प्रति ढेर से पॉप अप हो जाएगी।

इस तरह, आप समझेंगे कि, अगली-स्तर की गहराई वर्तमान-स्तर की गहराई स्थानीय चर को प्रभावित नहीं करेगी (जब तक आप संदर्भों का उपयोग नहीं कर रहे हैं, लेकिन हम इस विशेष समस्या में नहीं हैं)।

इस विशेष समस्या के लिए, समय-जटिलता को ध्यान से ध्यान देना चाहिए। यहां मेरे समाधान हैं:

/* Q: For the key values 1...n, how many structurally unique binary search 
     trees (BST) are possible that store those keys. 
     Strategy: consider that each value could be the root. Recursively 
     find the size of the left and right subtrees. 
     http://stackoverflow.com/questions/4795527/ 
      how-recursion-works-inside-a-for-loop */ 
/* A: It seems that it's the Catalan numbers: 
     http://en.wikipedia.org/wiki/Catalan_number */ 
#include <iostream> 
#include <vector> 
using namespace std; 

// Time Complexity: ~O(2^n) 
int CountBST(int n) 
{ 
    if (n <= 1) 
     return 1; 

    int c = 0; 
    for (int i = 0; i < n; ++i) 
    { 
     int lc = CountBST(i); 
     int rc = CountBST(n-1-i); 
     c += lc*rc; 
    } 

    return c; 
} 

// Time Complexity: O(n^2) 
int CountBST_DP(int n) 
{ 
    vector<int> v(n+1, 0); 
    v[0] = 1; 

    for (int k = 1; k <= n; ++k) 
    { 
     for (int i = 0; i < k; ++i) 
      v[k] += v[i]*v[k-1-i]; 
    } 

    return v[n]; 
} 

/* Catalan numbers: 
      C(n, 2n) 
    f(n) = -------- 
      (n+1) 
       2*(2n+1) 
    f(n+1) = -------- * f(n) 
       (n+2) 

    Time Complexity: O(n) 
    Space Complexity: O(n) - but can be easily reduced to O(1). */ 
int CountBST_Math(int n) 
{ 
    vector<int> v(n+1, 0); 
    v[0] = 1; 

    for (int k = 0; k < n; ++k) 
     v[k+1] = v[k]*2*(2*k+1)/(k+2); 

    return v[n]; 
} 

int main() 
{ 
    for (int n = 1; n <= 10; ++n) 
     cout << CountBST(n) << '\t' << CountBST_DP(n) << 
           '\t' << CountBST_Math(n) << endl; 

    return 0; 
} 
/* Output: 
1  1  1 
2  2  2 
5  5  5 
14  14  14 
42  42  42 
132  132  132 
429  429  429 
1430 1430 1430 
4862 4862 4862 
16796 16796 16796 
*/