java - 通过递归方法跟踪激活记录

Question

因此，为了很好地学习递归思想背后的逻辑，我在使用调试器学习数据结构的同时进行练习。这个问题看似简单，但却会引起轰动。该方法查找二叉搜索树中的最大元素。 - 通常，二叉搜索树(完整实现为click here)是一棵树，其中左子元素的元素比根元素少，右子元素的元素比根元素高。 - 在找到它之前，该方法进入新的激活帧并将其插入堆栈顶部。找到后，它们会按相反的顺序(LIFO)弹出。我的问题是，为什么该方法返回第二条语句(return findMax(node.right))？如果调试器显示激活帧弹出，为什么它只显示一次？我希望图像也有助于更好地理解我的问题。

/* bST.add(1),bST.add(3),bST.add(7),bST.add(6),bST.add(4),
   bST.add(13),bST.add(14),bST.add(10),bST.add(8); */

/**
 * Find max element in the BST
 * @param node local node being given
 * @return max element
 */
public E findMax(Node<E> node) {
        if (node.right == null)
            return node.data;
        return findMax(node.right);
}

Answer 1

代码沿着树的右侧向下运行，直到遇到最大的元素:没有右子元素的元素。然后它返回该节点的数据值——到调用它的实例。这是从节点 13 调用的实例。

特定语句return node.data是此递归的基本情况。第二个，return findMax(node.right)，是递归情况。当您达到值14时，您将有四个返回堆积起来，等待结果。

然后，来自节点 13 的调用会将值 14 传递回来自节点 7 的调用，继续沿着堆栈向下传递，直到来自节点 1 的调用将值 14 返回到首先调用的 findMax 。

我不知道为什么你的调试器只显示第一次激活“pop”的证据。我不知道你用的是什么设置。如果您是单步执行，或者在返回(以及findMax调用)处设置了断点，您应该会看到它的两端:下降到另一个级别，然后按 LIFO 顺序返回。

这对你来说有什么意义吗？