大家好，我是吴师兄。
先给大家看一张图，知乎上回复量挺多的一个提问：会写递归超越了多少程序员？
在这个话题下，回答者们旗帜鲜明的分为了两派：
1、会写递归就和学英语学会了 ABC 那么简单。
2、会写递归，至少超越了 50% 甚至 90% 的程序员。
我搜了一下我的微信聊天记录，惊讶的发现，每一周都有算法训练营的学员问我和递归相关的算法题，很多时候，同学们明明上一周搞懂了，这一周却又绕不出来了。
递归还是挺难的一个算法知识点。
我在回答他们问题的时候，非常喜欢用反转链表这道题目来举例子和分析。
给大家看一段可以解决反转链表这道算法题的递归代码。
代码语言：javascript复制class Solution {
public ListNode reverseList(ListNode head) {
// 寻找递归终止条件
// 1、head 指向的结点为 null
// 2、head 指向的结点的下一个结点为 null
// 在这两种情况下，反转之后的结果还是它自己本身
if( head == null || head.next == null) return head;
// 不断的通过递归调用，直到无法递归下去，递归的最小粒度是在最后一个节点
// 因为到最后一个节点的时候，由于当前节点 head 的 next 节点是空，所以会直接返回 head
ListNode cur = reverseList(head.next);
// 比如原链表为 1 --> 2 --> 3 --> 4 --> 5
// 第一次执行下面代码的时候，head 为 4，那么 head.next = 5
// 那么 head.next.next 就是 5.next ，意思就是去设置 5 的下一个节点
// 等号右侧为 head，意思就是设置 5 的下一个节点是 4
// 这里出现了两个 next
// 第一个 next 是「获取」 head 的下一节点
// 第二个 next 是「设置」 当前节点的下一节点为等号右侧的值
head.next.next = head;
// head 原来的下一节点指向自己，所以 head 自己本身就不能再指向原来的下一节点了
// 否则会发生无限循环
head.next = null;
// 我们把每次反转后的结果传递给上一层
return cur;
}
}
去掉注释阅读的话，就只有 5 行代码。
代码语言：javascript复制class Solution {
public ListNode reverseList(ListNode head) {
if( head == null || head.next == null) return head;
ListNode cur = reverseList(head.next);
head.next.next = head;
head.next = null;
return cur;
}
}
万变不离其宗，绝大部分递归的代码都和上述的代码类似，或者也是如下图所示。
