引言
对于很多程序员来说，写递归程序是比较头疼的一件事，即使是把程序看懂了，轮到自己写的时候也是一脸懵逼，那么到底写递归有没有方法论呢？当然！本文就将从数学归纳法的角度教你如何写递归程序。
数学归纳法与递归的关系
有人会疑惑，不是说好写递归嘛，怎么扯到数学归纳法了？别急慢慢往下看你就知道了。
首先我们来温习一下数学归纳法的定义：
数学归纳法：用于证明断言对所有自然数成立。
证明过程：
- 证明对于N=1成立
- 证明N>1时：假设对于N-1成立，那么对于N成立
咋一看你或许有点蒙，没事，我们来举个例子你就差不多懂了。
怎么样，总结一下就是：先证明第一个自然数成立，然后假设对于n-1成立，在用这个假设去推导证明对于n也成立。
对于自然数的第一个数字究竟是0还是1，是一个学术界至今没有统一的问题，我们这里使用1作为自然数的第一个数。
接下来重点来了！！！我们来看看如何用递归写上面那个例子
是不是惊人的相似啊！原来递归的思路和数学归纳法的证明思路是一样的啊！
铺垫了这么多，终于引出我们今天要讲的递归书写方法论。
递归书写方法
1. 先一般，后特殊（边界）
先写递归的主体部分，再回头写边界（一行行读主体部分的代码，寻找特殊的边界情况）
2. 每次调用必须缩小问题规模
3. 每次问题规模缩小程度必须为1（不要贪心）
这里的1并不是狭义的，比方说如果二分查找的时候，每次缩小一半的规模也是可以的
上面四点非常重要，为了帮助大家理解，接下来我举几个例子让大家热热身。
例1：创建链表
我们想要创建一个五节点的单向链表（如下图所示）：
该怎么做呢？首先我们先假设如果已经得到了后四个节点的链表：
那么此时我们只需要将第一个节点的next指针指向（n-1）结果的头节点即可
代码如下：
public ListNode createLinkedList(List<Integer> data) { ListNode firstNode = new Node(data.get(0)); // 将第一个节点的next指针指向n-1已经创建好链表的头节点 firstNode.next = createLinkedList(data.subList(1, data.size())); return firstNode; // 返回头节点 }
此时我们先一般的步骤就完成了，看看是不是每次调用函数都缩小问题规模了，是不是问题规模每次都缩小1，都满足条件！接下来就是后特殊了，划重点：一行行查看此时的代码，想想每一行代码在什么情况下出异常，一旦发现这就是特殊情况了！
例如：上面函数中的第一行，如果data为空的话，是不是就报错了，那么此时就需要做特殊情况处理：
public ListNode createLinkedList(List<Integer> data) { if (data.isEmpty()) return null; ListNode firstNode = new Node(data.get(0)); // 将第一个节点的next指针指向n-1已经创建好链表的头节点 firstNode.next = createLinkedList(data.subList(1, data.size())); return firstNode; // 返回头节点 }
那么到此为止，我们就完成了创建链表的递归程序编写。不过瘾？那我们再来一个！
例2：反转链表
还是老样子，我们先假设n-1个链表已经反转完成了：
那么此时我们应该怎么做呢？此时1这个元素的next指针还是指向2的，因为后面的反转并不会影响1元素的next指针：
所以此时我们只需要将节点2的next设为1，将节点1的next设为null即可完成反转！
代码如下：
public ListNode ReverseList(ListNode head) { // 这里得到n-1反转后链表的头节点，也就是反转前的最后一个节点 ListNode newHead = ReverseList(head.next); // 将节点2的next设为节点1 head.next.next = head; // 将节点1的next设为null head.next = null; return newHead; }
那么此时先一般就完成了，接下来就是寻找特殊（边界）情况了，一行行代码看下来发现head和head.next为null时会报异常，于是处理异常情况：
public ListNode ReverseList(ListNode head) { if(head == null || head.next == null) return head; ListNode newHead = ReverseList(head.next); head.next.next = head; head.next = null; return newHead; }
到此为止，反转链表函数就已经完成，是不是感觉按照数学归纳法的思路写递归还是蛮清晰的呢！
总结
数学归纳法是递归的依据。
书写递归的思路跟数学归纳法的证明过程相似，不过需要注意的是，先书写一般情况，后根据一般情况考虑特殊情况；同时要牢记递归函数每次缩小规模程度必须为“1”！
方法已经教给你了，接下去就是多练习了，赶紧找点题目练练手吧！