递归算法简而言之就是当一个大问题拆分为多个子问题时，如果每个子问题的操作步骤都一样，就可以用递归，其中递归在递的时候要有结束条件，不能一直递下去，结束条件后就归
这里不建议学习递归的时候抠细节，还原每一步递归的结果，要从宏观上来理解递归，将递归函数视为一个小黑盒，绝对无条件相信这个小黑盒能够完成其使命，然后再分析传参哪些参数合适，结束条件是什么就可以写出递归了
题目一：
最经典的递归题目之一，其实不算作简单的递归题，对于刚学习递归还是相当有挑战性
这个挑战性就是让之前抠细节的递归思想转化为宏观递归，造成思想上的转变
图就不画了，一是不好画，递过去归回来的，且容易陷入抠细节流程图，不够宏观
但是会主要展示代码的书写顺序，通过书写顺序来理解递归算法，容易站在宏观视角
思路：
一开始盘子都在起始柱子A，因为大的再最底下，所以要让除了最底下的盘子都拿走放在中转柱子B，才能让最大的盘子移动到目标柱子C，然后再让其他盘子从中转柱子B移动到目标柱子C
那么又如何让其他盘子移动到C呢，那么就要让除了其他盘子中最大的盘子先拿到中转柱子A上，让其他盘子中最大的盘子移动到目标柱子C，再让其他盘子移动到目标柱子C
……
所以这个大问题就拆为上述的子问题，而每一个子问题的操作流程是一样的，根据归纳总结就是：
（此时操作对象为n个盘子）
{
让n-1个盘子先从起始柱子移动到中转柱子
再让最大盘子从起始柱子移动到目标盘子
再让n-1个盘子移动从中转柱子移动到目标柱子
}
由此可以知道我们定义递归的参数应该有四个：起始柱子，中转柱子，目标柱子，操作对象数量n
那么就开始写函数，不要想太多，找到每个子问题的相同的操作流程就写，再思考又代进去递归下一轮，就越来越绕了
第一步：
先确定参数个数（X为起始柱子，Y为中转柱子，Z为目标柱子，n为操作对象个数）
public void bfs(List<Integer> X,List<Integer> Y,List<Integer> Z,int n){
}第二步：
确定该函数的用途，即你想让这个函数能具有什么功能
我们想让n个盘子能够从起始X开始，借助中转Y，到达目标Z
完美解决题目，然后就绝对无条件信任这个函数，管它代码还没写，它就是能做到我的要求
第三步：
将上述子问题相同步骤的流程转化为代码
1.
让n-1个盘子先从起始柱子移动到中转柱子
怎么实现呢？我们创建的递归函数就能直接实现，其中原起始柱子为起始柱子，而原中转柱子为目标柱子了，那么原目标柱子就为中转柱子了，然后操作对象个数n-1，直接调用递归函数传参即可
（绝对无条件信任递归函数）
public void bfs(List<Integer> X,List<Integer> Y,List<Integer> Z,int n){
bfs(X,Z,Y,n-1); //操作1
}2.
再让最大盘子从起始柱子移动到目标盘子
题目给的是List数据结构，那么就直接通过add函数和remove函数实现移动的步骤
public void bfs(List<Integer> X,List<Integer> Y,List<Integer> Z,int n){
bfs(X,Z,Y,n-1); //操作1
Z.add(X.remove(X.size()-1)); //操作2
}注意add是尾插，remove的返回值就是删除的那个值
最重要的是为什么是size（）-1而不是X[0]，很关键的一个混淆地方，那就是我们理解成了要移动的是最底下的盘子，其实是移动当前情况的最上面的盘子，因为此时A只有一个盘子，所以最底下的盘子是它，最上面的盘子也是它，所以会容易搞混
以3个盘子为例，我们默认1操作后，此时为这样的
但其实我们这个状况已经是接近大问题操作流程的尾声了，我们是从后往前递的，但实际上是从前往后归的，可以简单理解成“递”是在找一开始操作的位置（即结束条件），而“归”才是真正在做事的顺序
这里就明显可以看出来是size（）-1而不是X[0]，x[0]还是最底下那个大盘子，而实际我们要移动的最上面那个小盘子，即size（）-1
如果没get到的话可以再思考一下，汉诺塔问题确实操作不算简单，只是太经典了而不是最容易的
3.
再让n-1个盘子移动从中转柱子移动到目标柱子
还是直接调用我们的递归函数，绝对无条件相信它
public void bfs(List<Integer> X,List<Integer> Y,List<Integer> Z,int n){
bfs(X,Z,Y,n-1); //操作1
Z.add(X.remove(X.size()-1)); //操作2
bfs(Y,X,Z,n-1); //操作3
}第四步：
找到结束条件，那就是当n==1时，那么我们就不用借助什么中转柱子了，直接让这个盘子从起始柱子移动到目标柱子，也是通过add和remove来实现移动的操作（和操作2一样的），并return
public void bfs(List<Integer> X,List<Integer> Y,List<Integer> Z,int n){
//结束条件
if(n==1){
Z.add(X.remove(X.size()-1));
return;
}
bfs(X,Z,Y,n-1); //操作1
Z.add(X.remove(X.size()-1)); //操作2
bfs(Y,X,Z,n-1); //操作3
}第五步：
在main方法调用我们的递归函数
绝对无条件信任，我们递归函数的功能是：让n个盘子能够从起始X开始，借助中转Y，到达目标Z
所以最后主函数调用传参
class Solution {
public void bfs(List<Integer> X,List<Integer> Y,List<Integer> Z,int n){
//结束条件
if(n==1){
Z.add(X.remove(X.size()-1));
return;
}
bfs(X,Z,Y,n-1); //操作1
Z.add(X.remove(X.size()-1)); //操作2
bfs(Y,X,Z,n-1); //操作3
}
public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
bfs(A,B,C,A.size());//主函数调用
}
}这道题就解决了，是不是感觉有些莫名其妙的，突然就解决了，所以就是要绝对无条件信任你的递归函数，它不会辜负你的
综上大致总结递归算法就是上述五步
1.确定参数
2.定义你的递归函数功能，并且相信它
3.将子问题的相同流程转化成代码
4.找到结束条件并return
5.主函数调用你的递归函数即可
没有抠所谓的细节递归流程图，一开始刚学可以抠一下，因为确实太莫名其妙了，还不够信任你的递归函数，但之后就不要抠了，要宏观的来写代码，不容易搞混且效率很高，对你的递归函数有足够底气去信任
题目二：
思路：
第一种思路就是用双指针，一个指向第一个链表，另一个指向第二个链表，然后循环比较大小，修改对应的next即可，之前学过就不多赘述了
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//如果出现空链表的情况
if(list1==null){
return list2;
}
if(list2==null){
return list1;
}
//cur1cur2为双指针，cur为当前结点，ret为头结点
ListNode cur1=list1;
ListNode cur2=list2;
ListNode ret=null;
ListNode cur=null;
//确定头结点
if(cur1.val<cur2.val){
ret=cur1;
cur=ret;
cur1=cur1.next;
}else{
ret=cur2;
cur=ret;
cur2=cur2.next;
}
//遍历
while(cur1!=null&&cur2!=null){
if(cur1.val<cur2.val){
cur.next=cur1;
cur=cur1;
cur1=cur1.next;
}else{
cur.next=cur2;
cur=cur2;
cur2=cur2.next;
}
}
//如果其中一个链表遍历完了
if(cur1!=null){
cur.next=cur1;
}
if(cur2!=null){
cur.next=cur2;
}
//返回头结点
return ret;
}
}上述这个方法也就是循环的方法
但其实循环和递归是可以相互转化的，因为每一次循环做的事情都是一样的，也就是说明子问题操作流程也是一样的，递归也是这个特性，那么就可以相互转化了
还是按照五步来走
第一步确定参数，我们子问题的相同操作流程为合并链表，比较两个链表的头结点，然后提取较小的出来，接下来让剩下的链表继续参与合并
所以我们的参数为两个链表的头结点
第二步定义功能，我们定义的递归函数的功能是给两个链表的头结点，使得两个链表能够合并，并返回头结点，还是绝对无条件信任
第三步操作流程转化为代码
无非是让当前结点比较一下头结点的大小，然后选择较小的那一个，让该结点的next指向后面的链表合并后的新结点
第四步找到结束条件
那就是当其中一个链表为空的时候，就返回null就行
第五步主函数调用递归函数
无条件信任就行
代码：
class Solution {
public ListNode bfs(ListNode list1,ListNode list2){
//结束条件
if(list1==null){
return list2;
}
if(list2==null){
return list1;
}
//找到较小的结点
if(list1.val<list2.val){
//next指向后面合并链表返回较小的结点
list1.next=bfs(list1.next,list2);
//返回较小的结点
return list1;
}else{
list2.next=bfs(list1,list2.next);
return list2;
}
}
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//调用递归函数
ListNode ret=bfs(list1,list2);
return ret;
}
}总结：
既然循环和递归可以相互转化，那么什么时候用循环写着舒服，什么时候用递归写着舒服
当像左边这样有很多分支的话，就用递归舒服，像右边这样单边树就用循环
比如遍历数组，它不会出现什么回溯，也没有其他多余的选择，就下标一直往后走就行了，就用循环很舒服
像汉诺塔那道题，因为有三个柱子，所以往那边移动就有多个选择，选择的地方有很多，分支就多，很复杂，所以递归写着就很舒服
题目三：
思路：
之前学链表的时候也做过， 那个时候用的是循环的方法来解决，通过记录前驱后继和当前结点，通过互相修改完成翻转，也不多赘述
代码（循环）：
class Solution {
public ListNode reverseList(ListNode head) {
//如果是空链表
if(head==null){
return head;
}
//记录旧头结点的后继，并修改旧头结点的后继指向null
ListNode cur=head.next;
head.next=null;
//往后遍历直到为空
while(cur!=null){
//记录当前位置的后继
ListNode curN=cur.next;
//让当前位置的后继指向前驱
cur.next=head;
//让当前位置成为前驱
head=cur;
//让后继成为当前位置
cur=curN;
}
return head;
}
}稍微画画图还是很简单的
循环和递归可以相互转化，那么这道题递归其实没循环那么写着舒服，因为递归流程图是单边树情况，所以适合循环，但递归也可以来练一下，看着很简洁
第一步确定参数
大问题是要求给出头结点，将其翻转，并返回新的头结点，那么每个子问题也是需要给出头结点，将其翻转，再返回这个翻转后的头结点，所以需要头结点
第二步定义功能
这个递归函数能够实现链表翻转，并返回新头结点
第三步转化代码
我们让当前结点的next传入递归函数，就能拿到新头结点
那么此时只需要让当前结点的next指向当前结点，并修改当前结点的next指向null就行
然后返回新头结点
第四步结束条件
当结点为空时为结点的next为空就结束
第五步调用递归函数
因为这道题本身的函数参数和返回值与递归函数一样，就直接让当前函数成为递归函数
代码（递归）：
class Solution {
public ListNode reverseList(ListNode head) {
//结束条件
if(head==null||head.next==null){
return head;
}
//将该结点之后的链表全部翻转并返回新头结点
ListNode newHead=reverseList(head.next);
//让当前的next的next指向当前结点
head.next.next=head;
//修改当前的next指向空
head.next=null;
//返回新头结点
return newHead;
}
}虽然写着很简洁但还是会比较绕一点，其中newHead是不会变的，一直都是原链表的末尾结点，如果不理解画画图就明白了，不如循环写着舒服，但是很简洁
题目四：
思路：
因为大问题是将链表中两两结点进行交换，子问题是将剩下的链表两两结点进行交换，而每一个子问题的操作步骤都是一样的，所以可以用递归
假设函数的功能是交换链表的所有两两结点，并返回链表的新头结点
操作步骤：
通过递归函数得到剩下链表交换后的头结点tmp，备份当前大链表的头结点的next为ret，并且让ret的next指向当前大链表的头结点，让当前大链表的头结点指向tmp，最后返回ret就行
主要在顺序上要理清楚，大部分都是调用递归要放在前面，然后操作步骤在后面，因为要先往后递归，所以调用递归函数要放在代码块的前面
其中结束条件就是当只剩一个结点或者为null的情况就直接返回
代码：
class Solution {
public ListNode swapPairs(ListNode head) {
//结束条件
if(head==null||head.next==null){
return head;
}
//先调用
ListNode tmp=swapPairs(head.next.next);
//操作步骤
ListNode ret=head.next;
ret.next=head;
head.next=tmp;
//返回结果
return ret;
}
}题目五：
思路：
按照题意来想非常简单，就是累乘n次的x就行，用循环和递归都可以
虽然结果一定是没问题的，但是这道题加了一些限制，其中n非常大，直接来到整型的最大值和最小值了 ，所以按照常规思路来写循环一定会超时，递归一定会栈溢出
那么接下来就要想优化
根据幂的运算法则我们可以进行下面的拆分
比如3^16，原本就需要16次递归，而现在直接就只需4次递归（当n==0直接返回不再递归），相当于时间复杂度从O（N）来到了O（logN），大大提高了效率，这种方法也叫做快速幂
每个子问题是求得当前n的一半次幂，然后进行相乘，如果幂是奇数就再多乘一下自己本身
其中如果是负数就要转化为x^(-n) ——> 1/x^n
代码1（正确但不完全正确）：
class Solution {
//递归函数
public double pow(double x,int n){
//结束条件
if(n==0){
return 1.0;
}
//求出n的一半次幂
double ret=pow(x,n/2);
//求当前的n次幂
return n%2==0?ret*ret:ret*ret*x;
}
//主函数调用
public double myPow(double x, int n) {
return n<0?1.0/pow(x,-n):pow(x,n);
}
}如果这里直接提交到力扣，会发现通过，但其实有个小错误，但是误打误撞对了
那就是当n为-2^31时，这时负数变正为2^31，但是整型最大也就为2^31-1，会发生溢出，根据溢出的规则，-2^31取反溢出后还是-2^31，而-2^31经过多次的/2，最后会来到-1/2==0，刚好又符合结束条件，所以虽然结果是正确的，但是运行的逻辑与我们构想的其实是不一样的
解决整型溢出这个问题其实很简单，就是将会发生溢出的地方换成long就好
代码2（正确）：
class Solution {
//递归函数
public double pow(double x,long n){
//结束条件
if(n==0){
return 1.0;
}
//求出n的一半次幂
double ret=pow(x,n/2);
//求当前的n次幂
return n%2==0?ret*ret:ret*ret*x;
}
//主函数调用
public double myPow(double x, int n) {
long N=n;
return N<0?1.0/pow(x,-N):pow(x,N);
}
}这里求快速幂的版本是递归，还有一种求快速幂的方法是迭代，会在数学专题算法那里再学习
总结：
递归其实不难，只要发现子问题的操作都相同就可以使用，且无条件相信递归函数，其中调用递归函数往往在前面，后面才是操作步骤，然后找到结束条件就能快速解决，不要抠细节流程图，要宏观来看
