递归算法 Recursion
递归的本质
递归（Recursion），Recursion 的词根有重复的意思，百科对递归的定义是，通过重复将问题分解为同类的子问题而解决问题的方法，表现在代码上就是 函数自己重复调用自己。
Recursion 中文翻译很信达雅，递是将问题递出去，在递出的过程中问题被不断拆分成子问题，归是答案回归，在归的过程中，子问题的答案被不断合并。
举个例子：数组求和。
比如说一个长度为 10 的数组，怎么求和？最朴素的想法就是一个个加起来喽：
public int sum(int[] arr){
int result = 0;
for(int i=0;i<arr.length;i++){
result = result+arr[i];
}
return result;
}
假设 SnS_nSn 是索引区间 [0,n] 中元素的和，那 S0S_0S0 是索引区间 [0,0] 中元素的和（即 arr[0]）， S1S_1S1 是索引区间 [0,1] 中元素的和（即 arr[0] + arr[0]）...
求长度为 10 的数组的和，就是求 S9S_9S9。
上述代码是先求的 S0S_0S0，再加上后一个元素，得到 S1S_1S1 ，再加上后一个元素，得到 S2S_2S2 ，...，依次迭代，最终得到整个数组的和 S9S_9S9。
这样 从最简单的状态开始，推广到更复杂的状态 的方法，叫作“迭代法”。
现在逆向思考这个求和问题，要想得到 S9S_9S9，必须先得到 S8S_8S8 （S8S_8S8 加上后一个元素就是 S9S_9S9），要想得到 S8S_8S8，就先要得到 S7S_7S7（S7S_7S7 加上后一个元素就是 S8S_8S8），...，要想得到 S1S_1S1，就必须先得到 S0S_0S0，S0S_0S0 只包含一个元素，即 arr[0]。
这种 从最复杂的状态一直推广到最简单的状态 的方法，就是递归中的“递”，也就是拆解问题的核心。
// 计算数组arr，索引区间为 [0,k] 中的和
public int sum(int[] arr,int k){
if(k==0){ // 求解 S0
return arr[0];
}
return sum(arr,k-1) + arr[k]; // Sk = S(k-1) + arr[k]
}
不是什么问题都可以使用递归来解决呢，只要同时满足以下三个条件，就可以用递归来解决。
⨳ 问题可以纵向拆分，进而缩减问题规模
一个问题的解可以分解为几个子问题的解，子问题就是数据规模更小的问题。比如求解 S9S_9S9，可以拆分成 S8S_8S8 + arr[9] , S8S_8S8 可以拆分成 S7S_7S7 + arr[8] ...
⨳ 解决方法与问题规模无关
问题与分解之后的子问题，除了数据规模不同，求解思路完全一样，对于求和问题来说，无论是求S10S_{10}S10，还是 S100S_{100}S100，还是 S1000S_{1000}S1000，求解思路都是：sum(arr,k-1) + arr[k]。
⨳ 存在递归终止条件
递归会使用栈，问题拆分（递）对应的是方法入栈，如没有终止条件（即拆分到什么程度为止），栈会越来越高，最终导致栈溢出。
如求和问题，虽然函数自己重复调用自己，但问题的规模不断缩小，直至求解 S0S_0S0，S0S_0S0 就是递归终止条件。
同理，方法的返回意味着子问题得到答案，对应着方法的出栈，也就是问题答案合并（归）。
请注意，因为问题的拆分意味着方法栈帧入栈，一旦问题规模很大，调用层次很深，一直压入栈，就会有栈溢出的风险。
生产环境一般不会使用递归，一般能用递归写的算法都可以使用循环实现，如果非得用递归，可以限制一下递归调用的最大深度。
比如超过一定1000深度之后，我们就不继续往下再递归了，直接返回报错。
// 全局变量，表示递归的深度。
int depth = 0;
// 计算数组arr，索引区间为 [0,k] 中的和
public int sum(int[] arr,int k){
if (++depth > 1000) throw new Exception("too deep!");
if(k==0){ // 求解 S0
return arr[0];
}
return sum(arr,k-1) + arr[k]; // Sk = S(k-1) + arr[k]
}
斐波那契数
再看一下经典的递归问题：
斐波那契数 （通常用
F(n)表示）形成的序列称为 斐波那契数列 。该数列由0和1开始，后面的每一项数字都是前面两项数字的和。也就是：F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1给定
n，请计算F(n)。
假设 n = 8 ，那斐波那契数列为 1，1，2，3，5，8，13，21
⨳ 要想求解 F(8)，必须先求出 F(7) 和 F(6) ，让 F(7) + F(6)
⨳ 要想求解 F(7)，必须先求出 F(6) 和 F(5) ，让 F(6) + F(5)
⨳ 要想求解 F(6)，必须先求出 F(5) 和 F(4) ，让 F(5) + F(4)
⨳ ...
⨳ 要想求解 F(2)，必须先求出 F(1) 和 F(0) ，让 F(1) + F(0)
⨳ F(1) 已知为 1 ，F(0) 已知为 0 ，此为最小问题，递归终止条件。
class Solution {
public int fib(int n) {
if(n==0) return 0;
if(n==1) return 1;
return fib(n-1) + fib(n-2);
}
}
对于递归，不要迷失在不断调用中，你只需要知道 fib(k) 可以计算出第 k 个斐波那契数是多少，所以求解fib(n)，直接调用 fib(n-1) + fib(n-2) 即可。
当然不要忘了递归终止条件。
递归与链表
链表天然就具有递归的特性：一条链表可以看作是头节点和在头节点后挂了一个更小一点的链表，更小一点的链表可以看作是头节点，和头节点挂了一个更更小一点的链表，一直递下去，直至链表只剩一个头节点：
以反转链表为例： leetcode.cn/problems/re…
给你单链表的头节点
head，请你反转链表，并返回反转后的链表。比如 1->2->3->4->5->NULL 反转后 5->4->3->2->1->NULL‘
原来的解法是使用双指针头插法，即将 fast 指针指向的节点插入到 slow 指针指向的位置。
如果使用递归，先将问题递出去：
⨳ 要想反转 1->2->3->4->5->NULL ，相当于在 5->4->3->2-> 后挂上头节点 1
⨳ 要想反转 2->3->4->5->NULL ，相当于在在 5->4->3-> 后挂上头节点 2
⨳ 要想反转 3->4->5->NULL ，相当于在在 5->4-> 后挂上头节点 3
⨳ 要想反转 4->5->NULL ，相当于在在 5-> 后挂上头节点 4
⨳ 要想反转 5->NULL ，不需要进行处理，此为最小问题，递归终止条件。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
// 反转链表，如 1->2->3->4->5->NULL 反转后为 5->4->3->2->1->NULL
// 返回反转后的链表新头部，如 节点 5
public ListNode reverseList(ListNode head) {
if(head==null || head.next==null ){
return head; // 不需要反转
}
// 反转除 head 节点的后续子节点，如第一次调用是反转 2->3->4->5->NULL
// 宏观上，第一次调用，反转成功，返回的 new_head 为节点 5
ListNode new_head = reverseList(head.next);
// 现在就想办法将反转成功的子链表序列，5->4->3->2-> 挂上头节点 head
// 因方法入参的 head 的后继指针 指向 反转成功的子链表序列的尾节点
// 所以 head.next 为 反转成功的子链表序列的尾节点
head.next.next = head; // 将 head 挂在 子链表序列的尾节点 后
head.next = null; // 更新head为新的尾节点
return new_head;
}
}
相当于双指针头插法，递归进行链表反转不易理解吧，其实不需要深入进入递归，只需要知道 reverseList(head.next) 可以将 head 后的子链表序列反转即可，你需要处理的仅仅是在新生成的反转子链表后挂上 head 节点即可。