For 循环内递归如何工作

Question

我是递归新手，并试图理解这个代码片段。我正在准备考试，这是我从斯坦福大学 CIS 教育图书馆找到的一位“审稿人”（来自 Nick Parlante 的二叉树）。

我理解这个概念，但是当我们在循环内递归时，一切都崩溃了！请帮我。谢谢。

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

• 对于递归，在您的脑海中描绘出调用堆栈结构会很有帮助。
• 如果递归位于循环内，则结构类似于（几乎）N 叉树。
• 循环水平控制生成多少个分支，而递归决定树的高度。
• 树沿着一个特定的分支生成，直到到达叶子（基本条件），然后水平扩展以获得其他叶子并返回之前的高度并重复。

我发现这种观点通常是一种很好的思维方式。

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

for 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

只需记住所有局部变量，例如 numKeys、sum、left、right、root 位于堆栈内存中。当您进入递归函数的第 n 层深度时，将会有这些局部变量的 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
 */

Answer 5

您可以从基本情况开始向上思考。

因此，对于基本情况，您有 1 个（或更少）节点。只有 1 棵结构上唯一的树可能有 1 个节点——即节点本身。因此，如果 numKeys 小于或等于 1，则仅返回 1。

现在假设您有超过 1 个密钥。好吧，那么这些键之一就是根，有些项目位于左分支，有些项目位于右分支。

左右枝有多大？那么这取决于根元素是什么。由于您需要考虑可能的树的总数，因此我们必须考虑所有配置（所有可能的根值）——因此我们迭代所有可能的值。

对于每次迭代 i，我们知道 i 位于根，i - 1 个节点位于左分支，numKeys - i 节点位于右分支。但是，当然，我们已经有了一个函数，可以计算给定节点数的树配置总数！这是我们正在编写的函数。因此，递归调用该函数来获取左子树和右子树可能的树配置数。以 i 为根的可能树的总数就是这两个数字的乘积（对于左子树的每种配置，所有可能的右子树都可能发生）。

当你总结完一切之后，你就完成了。

所以，如果你把它列出来，从循环内递归调用函数没有什么特别的——它只是我们算法所需的一个工具。我还建议（正如 Grammin 所做的那样）通过调试器运行它，看看每一步发生了什么。

Answer 6

正如人们所期望的那样，每个调用都有自己的变量空间。复杂性来自这样一个事实：函数的执行被“中断”，以便再次执行相同的函数。
这段代码：

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;
    }

可以用 Plain 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...

它实际上是由编译器翻译成类似的东西，但是用汇编程序。正如您所看到的，循环由一对变量 numkeys 和 root 控制，并且它们的值不会因为另一个实例的执行而被修改。 em> 相同的过程。当被调用者返回时，调用者恢复执行，并使用递归调用之前的所有值相同的值。

Answer 7

IMO，这里的关键要素是理解函数调用框架、调用堆栈以及它们如何协同工作。

在您的示例中，您有一堆局部变量，这些变量在第一次调用中已初始化但未最终确定。观察这些局部变量对于理解整个想法很重要。在每次调用时，局部变量都会更新并最终以向后的方式返回（很可能在每个函数调用帧从堆栈中弹出之前将其存储在寄存器中），直到将其添加到初始函数调用的 sum 变量中。

这里重要的区别是 - 返回哪里。如果您需要像示例中那样的累积总和值，则无法在函数内返回，这会导致提前返回/退出。但是，如果您依赖某个值处于某种状态，那么您可以检查 for 循环内是否达到该状态并立即返回，而无需一路向上。