双递归在C/C++中是如何工作的--比如二叉树的深度？

Question

递归对我来说不是自然而然的。一些我能理解的程序是阶乘，其中n的阶乘是n*阶乘(n-1)。类似地，fibonacci级数- Fn = Fn-1 + Fn-2。还有一个bst- insert，search。所有这些递归函数都有一个共同点--返回具体值的条件。否则，它将使用不同的参数调用自身。一旦返回了具体的值，所有的调用都会展开。然而，我无法理解递归是一个接一个的程序。那里发生了什么。我如何才能自然地思考这些问题呢？例如-这是程序-

下面这几行的意义是什么？

 /* compute the depth of each subtree */
           int lDepth = maxDepth(node->left);
           int rDepth = maxDepth(node->right);



int maxDepth(struct node* node)
{
   if (node==NULL)
       return 0;
   else
   {
       /* compute the depth of each subtree */
       int lDepth = maxDepth(node->left);
       int rDepth = maxDepth(node->right);

       /* use the larger one */
       if (lDepth > rDepth)
           return(lDepth+1);
       else return(rDepth+1);
   }
} 

Answer 1

在搜索树时，返回具体值的条件是if (node==NULL)，返回的具体值是0，这是一棵深度0的树。考虑下面的树(from wikipedia)

​

​

从节点8开始，代码将递归到节点3，然后递归到节点1。当它尝试递归到节点1的左子节点时，它将找到NULL并返回0。然后，它将尝试节点1的右子节点，这也将返回0。此时，节点1转到if语句

   if (lDepth > rDepth)
       return(lDepth+1);
   else return(rDepth+1);

因为lDepth和rDepth都是0，所以节点1向节点3返回1，然后节点3递归到节点6，依此类推。

Answer 2

每次调用maxDepth(node->left)都会立即调用maxDepth(node->left)，直到树的最左边什么也没有留下(没有双关语)。然后最后一个调用返回，将调用maxDepth(node->right)。

这就是所谓的“深度优先”遍历，即我们在树上尽可能地往上走，然后访问每个分支上的叶子，直到我们在分支上完成，然后我们返回到分叉。

也许理解这段代码的最好方法是绘制一个小的二叉树，然后逐步检查代码，看看会发生什么。

Answer 3

在思想上，将逻辑分成两部分可能会有所帮助。如果您有一个可能指向单链表中某个节点的指针，并将空指针的深度定义为0，则可以说任何其他节点的深度都比它所链接的节点的深度大1。

    {node3 p_next_->}---->{node2 p_next_->}---->{node1 p_next_=nullptr}

所以，代码应该是：

int depth(Node* p)
{
     if (p == NULL) return 0;
     return depth(p->p_next_) + 1;
}

那么，你的问题是关于二叉树的。逻辑是相似的，但每次你计算出一个节点的深度，你就会说“好吧，这个节点下面可能有一个节点的右和/或左层次结构……我的深度比它们的深度大一个”。

或者，想想一个家庭可能会有所帮助，比如弗雷德有两个孩子苏和麦克斯，以此类推。

          fred
          /  \
        sue  max
       /  \
    sally charlie
             /
           june

在这里，计算sue的深度有点像是问“她是孩子(深度1)，父母(深度2)，祖父母(深度3)，曾祖父母(深度4)?”

我们可以看到她是sally的母亲(深度2)，但她是6月的祖母(深度3)。

我们可以通过这样系统地计算出3的答案:sue的深度比sally和charlie的深度多1，sally没有孩子(他们想象的深度是0)，所以她的深度是1，所以sue'2至少是2，但是比她想象的孩子(深度0)多1的比6月多1，也就是说，6月的深度是1，charlie的深度是2，sue实际上是3，比sally这边的计数还多。