遞歸如何在For循環中工作

Question

我是遞歸的新手，並試圖理解此代碼片段。我正在學習考試，這是我從斯坦福德的CIS教育圖書館（來自Nick Parlante的Binary Trees）發現的「審稿人」。

我理解這個概念，但是當我們在遞歸在循環內部，這一切的打擊！請幫幫我。謝謝。

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個鍵。那麼，其中一個鍵是根，一些項目在左分支，一些項目在右分支。

這些左右分支有多大？那麼這取決於什麼是根元素。既然你需要考慮可能的樹的總數，我們必須考慮所有配置（所有可能的根值） - 所以我們遍歷所有可能的值。

在每次迭代中我就知道，我是在根，我 - 1個節點是在左分支和numKeys - 我節點在右邊的分支。但是，當然，我們已經有了一個函數來計算給定節點數量的樹配置總數！這是我們寫的功能。因此，遞歸調用函數來獲取左側和右側子樹的可能樹配置的數量。那麼在根上可能有i的樹的總數是這兩個數的乘積（對於左子樹的每種配置，所有可能的右子樹都可能發生）。

總結一切後，你就完成了。

所以，如果你有種攤開來有什麼特別從一個循環內遞歸調用函數 - 它只是我們需要爲我們算法的工具。我也建議（如Grammin所做的那樣）通過調試器來運行它，並且看看每一步發生了什麼。

Answer 3

看它是這樣的：有初始呼叫3可能的情況：

numKeys = 0 
numKeys = 1 
numKeys > 1 

的0和1的情況下很簡單 - 函數只是返回1，就大功告成了。對於numkeys 2，你結束了：

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：

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 

等。這個函數很可能是O（n^2），因爲對於每個n個鍵，你都運行2 * n-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; 
    } 

可在純C這樣改寫：

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... 

它實際上是由編譯器類似的東西翻譯，但在彙編。正如你所看到的，循環由一對變量控制，數字和根，並且它們的值不會被修改，因爲執行相同過程的另一個實例。當被調用者返回時，調用者恢復執行，對遞歸調用之前的所有值使用相同的值。

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 
*/