java - 内存堆栈如何寻找背靠背的递归调用？

Question

我正在尝试理解递归的概念。我明白如果代码中有一个递归语句(示例阶乘)它是如何工作的

我不明白这样的代码如何计算二叉树的深度:

public int getDepth(Node root)
{
    if ( root == null) return 0;

    int left = getDepth(root.left);
    int right = getDepth(root.right);
    if (left > right) 
       return left + 1;
    else
       return right + 1;
}

我明白为什么会这样，但不知道如何运作。有人可以向我解释第二个递归调用 (getDepth(root.right)) 是如何工作的吗？这段代码在内存中会是什么样子？当递归调用 getDepth(root.left) 时，该堆栈是否会转到每个底部的 if 语句？

Answer 1

发生的情况是，每次连续调用 getDepth 都是完全独立的，因此绑定(bind)变量是独立的，并且它遵循其参数，并且忘记了它是从具有不同参数的自身版本调用的。

当你执行getDepth(null)时，你会得到0，因为它是第一行的基本情况。但是，如果您发送 getDepth(new Node(null, null))，它将调用 getDepth(root.left)，这与 getDepth(null) 相同，并且 left 和 right 都变为 0，结果为 0 + 1。

如果您将前一个节点绑定(bind)到变量 node 并尝试 getDepth(new Node(node, node))，它将再次执行 left 和 right，其中两者都是之前测试 1 的答案。结果将是 1 + 1，即 2。

您可以继续这样，并根据之前的计算假设结果。通过查看复杂的参数，您需要想象每个连续的递归都以其参数重新开始，并且遵循相同的模式。当结果传回时，调用者继续执行下一行。在树结构中，例如:

     1
    / \
   2   3
  /\   /\
 4  5 6  7

我只是对节点进行了编号，不包括空节点。您将看到执行按此顺序进行。标识指示堆栈深度/有多少调用正在等待恢复。

getDepth(1)
  getDepth(2)         // left
    getDepth(4)       // left
      getDepth(null)  // left base
      getDepth(null)  // right base
      return 0
    getDepth(5)       // right
      getDepth(null)  // left base
      getDepth(null)  // right base
      return 0
    return 0 + 1;
  getDepth(3)         // right
    getDepth(6)       // left
      getDepth(null)  // left base
      getDepth(null)  // right base
      return 0
    getDepth(7)       // right 
      getDepth(null)  // left base
      getDepth(null)  // right base
      return 0
    return 0 + 1;
  return 1 + 1;
return 2 + 1;