0

I am not able to understand the recursion of functions. How it works? how the values are stored and all? 

int tree_size(struct node* node) { 
  if (node==NULL) {
    return(0); 
  } else { 
    return(tree_size(node->left) + tree_size(node->right) + 1); 
  } 
}
4

4 回答 4

2

进入函数时，会创建一个新的堆栈帧（在内存中的堆栈上）。堆栈帧跟踪该函数内的本地数据，例如本地定义的变量和传入的参数。（以及必须保留的其他内容，例如返回地址和先前存储的寄存器值。但是，这与此问题无关。）

使用递归，当您从同一个函数中调用一个函数时，您会创建一个新的堆栈框架（与任何调用一样），并且该新堆栈框架将存储新调用的局部变量。

正如 C. Stoll 所指出的，由于 + 运算符，这两个调用的顺序是未指定的。

于 2012-07-26T08:23:50.260 回答
0

我认为最让你困惑的是..

return(tree_size(node->left) + tree_size(node->right) + 1);

如果您在顶部节点上调用此函数，它会告诉您树中的节点数是左侧的节点数加上右侧的数，再加上您刚刚调用函数的节点上的 this。

现在，我不认为是递归让您感到困惑，如果是，请发表评论，我可以再解释一下。

我认为您遇到的问题是该行的执行顺序。好吧，它遵循“加法”的逻辑数学规则。注意，我们知道我们不必关心运算符重载，就像tree_size返回 an一样int，所以我们有

intA + intB + intC;

我相信我不需要告诉你添加这三个值的顺序无关紧要，你会得到相同的结果。

但是，这些添加的顺序是明确定义的。如果您将+运算符视为它的功能，它会更清晰一些。我们基本上有（我希望我做对了）：

operator+(intA , operator+( intB, intC);

所以，你可以看到，我们需要先计算 B + C，然后才能加 A，或者如果我们把它带回到有问题的代码行，我们tree_size首先得到右边的，加一个，然后加在tree_size左边。这是需要注意的重要事项，您可以做一些非常奇怪的事情，例如在获得值时编辑树大小......例如，如果您将节点从一侧移动到另一侧。当然，如果获取它的大小不是您可以依赖的东西，那将是一棵非常糟糕的树。

我担心我可能在这里做得太多了，所以如果我有点错过了标记，请发表评论，我很乐意帮助您改善这个答案。

于 2012-07-26T08:57:47.800 回答
0

考虑以下三个

     1
  2 3
 4 5 6
7

1 有两个孩子（2 和 3） 2 有两个孩子（4 和 5）.. 4 有一个孩子（7）
，您想知道树在 1 处的大小：

tree_size(tree1);

因为 tree1 不为 NULL 且 if 条件不成立，所以 else 语句将被执行：

tree_size(tree1): return tree_size( tree_size(tree2) + tree_size(tree3) + 1 )

树 2 和树 3 相同

tree_size(tree2): return tree_size( tree_size(tree4) + tree_size(tree5) + 1 )
tree_size(tree3): return tree_size( tree_size(tree6) + tree_size(NULL) + 1 )

等等。现在如果我们用 tree_size(tree1) 替换 tree_size(tree2) 和 tree_size(tree3) 的返回值，我们会得到：

tree_size(tree1): return tree_size( tree_size(tree4) + tree_size(tree5) + 1 + tree_size(tree6) + tree_size(NULL) + 1 + 1 )

现在您可以看到术语 1+1+1，这是前两个 niveau 的树的大小，如果我们继续替换 tree_size 调用，将得到 n 乘以 1 的一些，其中 n 的大小树

于 2012-07-26T08:38:08.633 回答
0

使用纸片的类比（@nhahtdh 在对 Q 的评论中）非常好。让我详细说明一下。

首先，以更线性的方式重新编写代码：

int tree_size(struct node* node) { 
  if (node==NULL) {
    return(0); 
  } else { 
    x = tree_size(node->left);
    y = tree_size(node->right);
    z = x + y;
    r = z + 1;
    return( r ); 
  } 
}

想象一下，您面前有一叠厚厚的（实际上取之不尽的）空纸。您的办公桌左侧还有各种食谱（功能定义），右侧有一个空白空间。

现在，调用一个函数意味着将它的定义从它的配方复制到你面前一堆纸上的纸上，然后将调用的参数值替换为函数参数，然后从那里继续。

当你碰到一个函数调用的行（任何函数调用）时，在你面前的纸上标记那条线，把那张纸移到你的右边（面朝上），然后开始处理新的空纸纸在你面前。将您需要调用的函数的配方复制到其上，记下参数值，然后根据您面前的配方继续处理它。

如果您遇到另一个函数调用，请重复以下操作：标记需要接收函数调用结果的行，将当前纸张放在您右侧的纸堆顶部（面朝上），将新配方复制到你面前的最上面的一张纸，然后像以前一样从那里继续。

现在，当您点击当前配方中的一行时return，将返回的值写在您右侧标记行的纸堆的最上面一张纸上，然后丢弃您面前的当前纸并向后移动从你面前的那摞纸中取出最上面的那张纸。

而已。你只需要两摞纸，一张在你面前，另一张在你的右边，还有一堆写着函数定义的纸，在你的左边。

请注意，我们不关心我们调用的函数是否与我们执行的先前函数调用之一相同。它的工作原理是一样的。

于 2012-07-26T09:54:52.693 回答