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

- Scared

---

我会说它的工作方式完全相同，但我猜这不是你想要的答案。不要让“for”欺骗你——范围才是重点。 - rsenna

你的意思是什么意思：“it all blows”？ 你是否遇到了崩溃？ 还是你的大脑不肯合作？ - user3458

Answer 1

想象一下，在进入函数调用时，“暂停”循环。

只是因为这个函数恰好是一个递归调用，它的工作方式与您在循环中调用其他任何函数的方式相同。

新的递归调用开始其for循环，并且再次在调用函数时暂停，以此类推。

- Tony

Answer 2

• 对于递归，形象地想象调用栈结构有助于理解。
• 如果一个递归嵌套在循环中，其结构类似于（几乎是）一棵 N 叉树。
• 循环控制水平上生成多少分支，而递归则决定树的高度。
• 该树沿着一个特定分支生成，直到达到叶子节点（基本条件），然后向水平方向扩展以获取其他叶子并返回之前的高度，并重复上述过程。

我认为这种观点通常是一种好的思考方式。

- Albert

---

这是您分享的内容 @Albert 的可视化图表：https://java2blog.com/find-subsets-set-power-set/#comment-34683 - Reejesh PK

Answer 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次递归调用，这意味着它的运行时间会非常快地增长。

- Marc B

---

如果您像OP一样使用递归函数，我认为时间复杂度是~O(2^n)；如果您使用动态规划，则为O(n^2)；实际上有一种O(n)的解决方案。请查看我的答案 :-) - Peter Lee

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.
      https://dev59.com/02445IYBdhLWcg3wkLLU
             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
 */

- Peter Lee

Answer 5

你可以从基本情况开始，向上工作。

因此，对于基本情况，您有1个（或更少）节点。只有1个结构独特的树是可能的，其中只有1个节点本身。因此，如果numKeys小于或等于1，则返回1。

现在假设您有多个键。那么，其中一个键是根，一些项目位于左分支中，一些项目位于右分支中。

这些左侧和右侧的分支有多大？这取决于根元素是什么。由于您需要考虑可能树的总数，因此我们必须考虑所有配置（所有可能的根值）-因此，我们遍历所有可能的值。

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

将它们全部加起来后，你就完成了。

因此，如果您将其展开，从循环中递归调用函数没有什么特别之处--它只是我们算法所需的工具。我也建议（像Grammin一样）通过调试器运行它，并查看每个步骤的情况。

- vmpstr

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

可以用普通的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控制，它们的值不会因为执行同一过程的另一个实例而被修改。当被调用者返回时，调用者恢复执行，并且所有在递归调用之前的值都保持不变。

- Baltasarq

Answer 7

在我看来，关键要理解函数调用帧、调用栈以及它们如何协同工作。

在你的例子中，有一堆本地变量在第一次调用时被初始化但没有完成。观察这些本地变量对于理解整个思路非常重要。在每次调用时，本地变量都会更新，并以反向方式（很可能在从堆栈中弹出每个函数调用帧之前存储在寄存器中）返回，直到它被添加到初始函数调用的总和变量中。

这里的重要区别是——在哪里返回。如果你需要像你的例子中那样累积总和值，你不能在函数内部返回，否则会导致过早返回/退出。然而，如果你依赖于某个值处于特定状态，那么你可以在 for 循环中检查是否达到了这个状态，并立即返回，而不必一直往上走。

- stdout