为什么我思考的递归总和老师的不一样...

Question

我喜欢每次看到要敲代码的时候，都先自己敲一遍，再对照老师的。我发现涉及到递归，我总使用了一种和老师不一样的思路，比如删除最小值节点的递归我这么写的：

public E removeMin() {
    return removeMin(root, null);
}

public E removeMin(Node<E> node, Node<E> parent) {
    if (node.left == null) {
        if (parent == null) {
            root = node.right;
        }else {
            parent.left = node.right;
        }
        size--;
        return node.e;
    }

    return removeMin(node.left, node);
}

之前的别的递归也是，我似乎总第一反应总是会把递归的中间值当作参数传进去，比如这次的parent。如果是累加的递归，我第一反应会把sum当作参数传到递归里面。我经过了测试，递归方法执行结果是正确的。我可以看懂老师的递归，但每次要写的时候，都写不出来老师那种递归，最后写出一种上面的递归，我现在链表的一些递归操作，都是会把中间值当作递归方法参数传进去。我是哪里思考的方式与老师不同呢？我应该怎么思考，才能写出老师那种递归呢？

Answer 1

liuyubobobo 2020-02-07 01:12:10

如果对递归接触不多，能写出正确的逻辑，已经很不错了：）

我感觉了一下，你的这种思考的关键在与没有充分利用返回值。

比如“累加的递归，你的第一反应会把sum当作参数传到递归里面”，而我的写法，实际上 sum 是返回值。

比如这个“删除最小值节点”，你传入 parent，是为了维护删除节点后树的形态，需要改变 parent 连接的节点，但我的写法，这个维护可以靠返回值完成。（注意，我的返回值是 Node，而你的写法，如果不是因为顶层调用要返回删除节点的值的话，完全不需要返回值。）

我的建议是，再仔细体会一下递归的“宏观语义”（我在上一章“链表和递归”时有介绍）。整个递归函数的语义定下来，返回值也是语义的一部分，可以用来组建逻辑。

没有好的办法，多练习递归，多积累。每一次都这样，自己先写，然后比较别人的写法，仔细思考自己的思考和别人的思考之间的区别，慢慢就能融会贯通了。

不过依然是，能写出正确的逻辑，是基本要求，达到这个要求，已经挺不错的了：）

继续加油！：）

• 提问者 慕码人1018289 #1

  非常感谢！

• 提问者 慕码人1018289 #2

  非常感谢老师！老师晚上1点多还没有休息呀。我今早看了您的回复，非常激动。仔细看了您的回复，我写出了removeMax方法。感受到这样的removeMax方法，宏观语义是“把传入的节点的最大值删除，还返回这个节点”，所以才会
  root = removeMax(root); 
  node.right = removeMax(node.right); 
  
  我起初有些许理解不了，后来思考List假如有一个removeRepeat的方法，它是为了去重复：
  List list = new ArrayList();
  list = removeRepeat(list);
  得到去重复后的list，就会好理解的多，removeMin也可以这样理解。
  
  而我写的方法public E removeMin(Node<E> node, Node<E> parent)的宏观语义是是“删除传入节点的最大值，并返回这个最大值”。如果parent是BST维护的一个成员变量，就显得我“传入parent维护删除节点后树的形态”不那么刻意了，removeMin(root, null)也就不那么奇怪了
  
  我觉得，这两种递归语义不同可能导致这样几个不同：
  1，我那种递归思路可以logn一次找到并删除节点，老师的似乎需要logn两次，但这样不并是性能问题。之所以logn两次，是因为“找到最小值”和“删除最小值”封装成了两个方法，而我们要求removeMax返回了被删除对象，所以被迫调用了2次logn的方法。如果不要求，让用户自己选择是否先int max = bst.maximum()再bst.removeMax()，则可能不会logn两次。
  2，老师的方法可以是Util方法，比如有一个BSTUtil，它有一个静态方法是public Node<E> removeMax(Node<E> node)，可以删除传入节点的最大值，变成这样使用：
  BST bst = new BST({2,3,5,1,7,6});
  bst = BSTUtil.removeMax(bst);
  因为那个方法的语义比较纯粹，而我那种方法要求传入parent，弄成BSTUtil会有一些奇怪。Util类最大的好处是可以增加别人创造的类