我无法理解函数的递归。 这个怎么运作？ 如何存储值以及所有值？
我无法理解函数的递归。 这个怎么运作？ 如何存储值以及所有值？
int tree_size(struct node* node) { if (node==NULL) { return(0); } else { return(tree_size(node->left) + tree_size(node->right) + 1); } } 输入函数时，会创建一个新的堆栈帧（在内存中的堆栈上）。 堆栈帧跟踪该函数中的本地数据，例如本地定义的变量和传入的参数。 （以及其他诸如返回地址和先前存储的必须保留的寄存器值等。但这与此问题无关。）
使用递归，当您从同一函数中调用函数时，您将创建一个新的堆栈帧（与任何调用一样），并且新的堆栈帧将存储新调用的局部变量。
正如C. Stoll指出的那样，由于+运算符，两个调用的顺序未指定。
考虑以下三点
1
2 3
4 5 6
7
1有两个孩子（2和3）2有两个孩子（4和5）.. 4有一个孩子（7）
并且你想知道1的树的大小：
tree_size(tree1);
因为tree1不为NULL，if-condition不为true，所以else语句将被执行：
tree_size(tree1): return tree_size( tree_size(tree2) + tree_size(tree3) + 1 )
对于tree2和tree3也是如此
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调用，w将得到n次1的一些，n的大小为树
我认为让你最困惑的是……
return(tree_size(node->left) + tree_size(node->right) + 1);
如果您在顶级节点上调用此函数，它将告诉您树中的节点数是左侧的节点数，加上右侧的数字，加上您刚刚调用该函数的节点上的节点数。
现在，我不认为这是令你困惑的递归，如果是，请留下评论，我可以解释一下。
我认为你遇到的问题是该行的执行顺序。 嗯，它遵循“添加”的逻辑数学规则。 注意，我们知道我们不必关心运算符重载，因为tree_size返回一个int ，所以我们有
intA + intB + intC;
我相信我不需要告诉你，添加这三个值的顺序无关紧要，你会得到相同的结果。
但是，这些添加的顺序是明确定义的。 如果你认为+运算符是它的function，它会更清晰一点。 我们基本上（我希望我做对了）：
operator+(intA , operator+( intB, intC);
所以，你可以看到，我们需要首先计算B + C才能添加A，或者如果我们把它带回到有问题的代码行，我们首先得到右边的tree_size ，然后添加一个，然后添加左侧的tree_size 。 这是一个需要注意的重要事项，你可以做一些非常奇怪的事情，例如在获得值时编辑树大小…比如，如果你将节点从一侧移动到另一侧。 当然，如果获得它的大小不是你可以依赖的东西，它将是一棵非常糟糕的树。
我担心我在这里可能会有点太多，所以如果我错过了一点，请发表评论，我很乐意帮助你改善这个答案。
使用纸张的类比（@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 ); } }
想象一下，你面前有一堆厚厚的（几乎取之不尽的）空纸。 您桌面左侧还有各种食谱（function定义），右侧有空白区域。
现在，调用函数意味着将其定义从其配方复制到您面前的纸叠顶部的纸张上，然后将调用的参数值替换为函数参数，并从那里继续。
当你点击一个带有函数调用的行（ 任何函数调用）时，在你面前的纸张上标记该行，将该纸移到右边（面朝上），然后开始处理新的空白页纸在你面前。 将需要调用的函数的配方复制到其上，记下参数值，然后根据您面前的配方继续处理它 。
如果遇到另一个函数调用，请重复此操作序列：标记需要接收函数调用结果的行，将当前的纸张放在右上角（面朝上），复制新配方在你面前的一张纸，然后像往常一样从那里继续。
现在，当你在当前食谱中找到一条return的行时，将返回的值写在那里标记线右边的堆中的纸上，然后丢弃你面前的当前纸张并移动把纸叠上的纸条放回到你面前的一叠纸上。
而已。 你需要的只是两张纸，一张在你面前，另一张在你的右边，还有一堆纸，上面写着function的定义，在你的左边。
注意，我们不关心我们调用的函数是否与我们之前执行的函数调用相同 。 它的工作原理是一样的。