92号题中递归的设计思路
来源：5-1 链表，在节点间穿针引线 Reverse Linked List
Poplar_hills
2019-05-09
bobo 老师，
这两天我在研究92号题目 Reverse Linked List II，在看到 Solution 中的 Approach 1: Recursion 时有如下问题想向您请教：
我能理解该解法的思路 —— 先将两个指针移动到数组 m, n 的位置上，再在他们互相逼近的过程中不断 swap 节点中的值。但是因为单向链表没有从后一个节点指向前一个节点的指针，因此若要让右边的指针左移到上一个节点就需要借助递归来实现，因为在每层递归结束回到上一层调用栈时可以获得上一个节点。
但即使理解了这个思路、看了答案中的代码，还是感觉没有吃透这道题，不知道这个递归是怎么设计出来的、为什么会这样设计。
我整理了一下，其中关键部分代码如下：
public ListNode reverseBetween(ListNode head, int m, int n) {
this.left = head;
this.stop = false;
recurseAndReverse(head, m, n);
return head;
}
private void recurseAndReverse(ListNode right, int m, int n) {
if (n == 1) return;
if (m > 1) this.left = this.left.next;
right = right.next;
recurseAndReverse(right, m - 1, n - 1);
if (this.left == right || right.next == this.left)
this.stop = true;
if (!this.stop) {
swapNodeValue(this.left, right);
this.left = this.left.next;
}
}我试着分析了一下，在 recurseAndReverse 中：
递归终止条件：n == 1
递归最小单元：???
进入下一层递归之前做的事：让两个指针向右移动，直到到达 m, n 上
归回上一层递归之后做的事：判断两个指针是否已经撞上，若没有则交换节点值，并让两个指针互相接近一步（让右指针向左移动是由递归结束时原路返回上层（backtracking）实现的）。
想请问 bobo 老师：
递归的最小单元应该是哪部分？
递归逻辑是否应该这样分析？
在设计这个递归时应该怎么去想？感觉即使分析出了上面的四点，离最终写出这样的代码还是有很大距离。
非常感谢！
1回答
-
大赞你的总结和认真：）
首先，我必须要说，如何设计一个递归算法，是没有一定之规的，也没有标准方式的。如果有一个标准方式，可以按照流程去操作，就能设计出递归算法，那么设计一个递归算法也就不是什么难事儿了，人人都能掌握它了。实际上，正是因为算法设计具有相当的灵活性，没有一定之规，所以，他才有难度，才有很多同学望而却步。
所以，最简单的方式，也是我最推荐的方式，是就到这里，不要再和这个问题死磕了。去见识更多的递归问题，对每个问题都这样总结，但千万不要陷入其中，无法自拔。见识的够多了，再找时间，再回头看这个问题，可能你会豁然开朗。可以参考我的公号文章，《高效学习的秘密》：https://mp.weixin.qq.com/s?__biz=MzU4NTIxODYwMQ==&mid=2247483836&idx=1&sn=90854aa76507281403e4dd9cd434a12b&chksm=fd8caefacafb27ec78f999fde4f1217c04c6e2ff28cf51fe511d8fa29d484d9281ff91de8c9c&token=847844479&lang=zh_CN#rd
==========
下面简单说一下我设计递归函数的"秘诀"：
首先，我没有特别理解你说的递归最小单元是什么意思。在我看来，递归韩式只有两部分：
递归终止条件；
递归过程
写一个递归函数，将这两部分想清楚，就足够了。
对于递归终止条件，通常都是非常简单的，不多说。关键是递归过程。
我设计递归过程的秘诀，是定义清楚这个递归函数的语义。换句话说，就是，这个递归函数，输入是什么，输出是什么。
定义清楚之后，在递归过程中，你需要调用这个递归函数，但是，此时，不要把它想成一个递归函数，就把他想成一个普通函数。这个普通函数，有输入，有输出。关键是，使用这个普通的函数提供的输入和输出，如何构建你当前函数的逻辑。
不知道我这么说是不是比较抽象。
举一个最简单的例子，求一个二叉树的高度。代码大概是这样的：
class Solution { public: int maxDepth(TreeNode* root) { // 递归终止条件 if(root==NULL) return 0; // 求左子树的高度 int leftHeight = maxDepth(root->left); // 求右子树的高度 int rightHeight = maxDepth(root->right); // 二者取最大值 return max(leftHeight, rightHeight); } };注意一下注释，其实，这都是建立在，我们定义清楚了int maxDepth(TreeNode* root)这个函数，就是在求，以root为根节点的二分搜索树的高度上。我们内里的逻辑，直接使用这个函数的语义。这一点非常关键。我们调用递归函数的时候，不要去想这个函数的内部逻辑，把他当成一个已经封装好的函数，直接去调用。所谓的递归的宏观语义。我在《玩转数据结构》这门课程中，也特意强调过这个事情。
最后，对于这个问题，逻辑相对比较复杂，还有一个原因，是在够题目要求的one-pass这个条件。我的建议是，从理解递归的角度，先尝试实现two-pass的代码：）
这个课程后续，还会包含大量和递归相关的练习。树，图，回溯，动归，都离不开递归。如果一个问题想不透彻，不要止步不前。看更多的问题，回头再来看这个问题，很有可能豁然开朗。
对于你的问题，尤其关注一下第八点：）
加油！：）
312019-05-10
相似问题