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

我试图理解递归的概念。我了解如果代码中只有一个递归语句（例如阶乘），它将如何工作

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

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语句？

最佳答案

发生的情况是，每个对getDepth的连续调用都是完全独立的，因此绑定变量是独立的，并且遵循其参数，并且忽略了从具有不同参数的自身版本中进行调用。

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

如果将前一个节点绑定到变量node并尝试getDepth(new Node(node, node))，它将再次执行left和right，这两个变量都是先前测试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;