大家好，我是bigsai，之前有老弟说弄不懂递归，今天给大家讲讲递归。
什么是递归？
递归：就是函数自己调用自己。子问题须与原始问题为同样的事，或者更为简单。
递归通常可以简单的处理子问题，但是不一定是最好的解决方式。
对于递归要分清以下概念：
递归是自己调用自己递归通常不在意具体操作，只关心初始条件、结束条件和上下层的变化关系。递归函数需要有临界停止点(结束条件)，即递归不能无限制的执行下去。通常这个点为必须经过的一个数。递归可以被栈替代。有些递归可以优化。比如遇到重复性的可以借助空间内存记录而减少递归的次数认识递归，递归函数通常看起来简易但是对于初学者可能很难去理解它，拿一个递归函数来说。
staticvoiddigui(){System.out.println(bigsai前);digui();System.out.println(bigsai后);}这是一个递归嘛？不是正常递归，没有结束条件，自己一致调用自己导致无限循环。
那正确的递归应该这样
staticvoiddigui(inttime){if(time==0){}//time==0不执行else{System.out.println(bigsai前time
time);digui(time-1);System.out.println(bigsai后timetime);}}对于这样一种递归，它的流程大致是这样的
定义递归算法及参数-停止递归算法条件-(可存在)其他逻辑-递归调用(参数需要改变)-(可存在)其他逻辑
所以，调用digui(5)在控制台输出是这样的
那么，我想你对递归函数执行的流程应该有所了解了吧。
递归求阶乘
初学递归，接触最多的就是递归求阶乘，为啥阶乘可以用递归来求呢?我们首先看下阶乘，n的阶乘表示为：
n!=n*(n-1)*……*1
n的阶乘就是从1开始叠乘到n，那么n-1的阶乘为：
(n-1)!=(n-1)*(n-2)*……*1
通过观察就能知道n的阶乘和n-1的阶乘有这样的关系：
n!=n!=n*(n-1)!
所以，我们要求n的阶乘，我们知道n-1的阶乘乘以n就可以得到，这就是最核心的关系。
0的阶乘为1，通过阶乘上下级的关系，我们假设一个函数jiecheng(n)为求n的阶乘的函数，那么这个函数为：
staticintjiecheng(intn){if(n==0)//0的阶乘为1{return1;}else{returnn*jiecheng(n-1);//returnn*(n-1)*jiecheng(n-2)=-------}}运行流程为这样：
递归求斐波那契
斐波那契数列，已经跟随我们成长很久很久了，除了直接的斐波那契，爬楼梯等问题也和斐波那契问题差不多。
首先，求斐波那契的公式为：
F[n]=F[n-1]+F[n-2](n=3,F[1]=1,F[2]=1)
也就是除了n=1和2特殊以外，其他均是可以使用递推式，按照上述递归思想，我们假设求斐波那契设成F(n)；
那么递推实现的代码为：
staticlongF(intn){if(n==1
n==2){return1;}else{returnF(n-1)+F(n-2);}}其实它的调用流程为：
不过这个斐波那契这样的求法效率并不高，后面会提一嘴。
递归解决汉诺塔
汉诺塔是经典递归问题：
相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。
在这里插入图片描述如果A只有一个（A-C）如果A有两个（A-B）,(A-C),(B-C)如果A有三个（A-C）,(A-B),(C-B),(A-C),(B-A),(B-C),(A-C).如果更多，那么将会爆炸式增长。
可以发现每增加一步，其中的步骤会多很多，如果一步步想，很难想明白，所以要用递归全局的想法看问题。
当有1个要从A-C时，这里使用函数move(A,C)表示(其他move操作同理)。
用hannuo(n)函数表示总共n个盘子要从A-C。
递归，其实就是要找上下层的关系，n个盘子从A挪到C和n-1个盘子从A挪到C有啥联系(hannuo(n)—hannuo(n-1)有啥关系)。下面带你一步步分析。
假设有n个盘子
hannuo(n-1)之后n-1个盘子从A—C.
此时剩下底下最大的，只能移动到B，move(A,B)
那么你是否发现什么眉目了，只需原先的huannuo(n-1)相同操作从C—B即可完成转移到B，所以这个需要加参数表示其方向性，那么我们的之前函数应该写成hannuo(n-1,A,C),但是这里肯定又用到B(向下需要用到)，所以把B传进来hannuo(n-1,A,B,C)先表示为从n-1个从A(借助B执行若干操作)转到C。
这一系列操作使得将n个盘子从A—B但是我们要的是A—C才是需要的hannuo(n,A,B,C)，这个很容易啊我们只需要第一步将n-1挪到B上就可以了啊。
经过上面分析，那么完整的操作为：
package递归;publicclasshannuota{staticvoidmove(chara,charb){System.out.println(移动最上层的+a+到+b+\t);}staticvoidhannuota(intn,chara,charb,charc)//主要分析每一大步对于下一步需要走的。{if(n==1){move(a,c);}//从a移到celse{hannuota(n-1,a,c,b);//将n-1个从a借助c移到bmove(a,c);//将第n（最后一个）从a移到c。hannuota(n-1,b,a,c);//再将n-1个从b借助a移到c}}publicstaticvoidmain(String[]args){hannuota(5,a,b,c);}}这样，汉诺塔问题是不是搞懂了？
递归VS记忆化
很多时候，递归的效率是很低的(一个递归拆分成两个及以上子问题效率就不太行了)，我们要用动态规划或者记忆化去优化，为什么要记忆化？因为递归成子问题，子问题再拆分成子问题，造成很多的重复计算！
比如上面说到的递归求斐波那契数列，就是一个效率非常低的算法，比如你看看F(5)是这样走的：
在递归求F(4)时候，F(4)递归会求解F(3)，但是右侧的还会再执行一遍。如果是数量非常大的数，那么将耗费很大的时间。所以我们就可以采取记忆化！第一次算出结果的时候就存储一下，如果是线性有规律(大部分)就用数组，否则就用HashMap存储。
具体实现的代码为
/p>
staticlongF(intn,longrecord[]){if(n==1
n==2){return1;}if(record[n]0)returnrecord[n];elserecord[n]=F(n-1,record)+F(n-2,record);returnrecord[n];}publicstaticvoidmain(String[]args){intn=6;long[]record=newlong[n+1];System.out.println(F(n,record));}这样可以节省很多时间，尤其是n非常大的情况(递归是指数级别增长，记忆化是线性级别)。例如一个F(6)求解过程：
当然，记忆化的问题远远不止这么多，具体还需要自行学习。
递归VS数据结构
递归在很多场景都有很好的应用，在链表中、二叉树、图中(搜索算法)都有很多的应用，这里就举一些非常经典的例子。
比如在链表中，很经典的就是链表逆序输出、链表反转问题，比如链表反转问题，对应力扣(给你单链表的头节点head，请你反转链表，并返回反转后的链表)，可以这样巧妙的实现：
/***Definitionforsingly-linkedlist.*publicclassListNode{*intval;*ListNodenext;*ListNode(){}*ListNode(intval){this.val=val;}*ListNode(intval,ListNodenext){this.val=val;this.next=next;}*}*/classSolution{publicListNodereverseList(ListNodehead){if(head==null
head.next==null)returnhead;ListNodenode=reverseList(head.next);//返回最后的链表节点head.next.next=head;//后一个节点指向自己head.next=null;//自己next指向nullreturnnode;}}对于二叉树，最经典的就是二叉树的前序、中序、后序遍历的递归实现方式：
例如二叉树前序遍历：
publicvoidqianxu(nodet)//前序递归前序遍历：根结点---左子树---右子树{if(t!=null){System.out.print(t.value+);//当前节点qianxu(t.left);qianxu(t.right);}}二叉树中序遍历：
publicvoidzhongxu(nodet)//中序遍历中序遍历：左子树---根结点---右子树{if(t!=null){zhongxu(t.left);System.out.print(t.value+);//访问完左节点访问当前节点zhongxu(t.right);}}二叉树的后序遍历：
publicvoidhouxu(nodet)//后序遍历后序遍历：左子树---右子树---根结点{if(t!=null){houxu(t.left);houxu(t.right);System.out.print(t.value+);//访问玩左右访问当前节点}}递归VS常见算法
在我们熟知很多算法都与递归有着很大关系。比如dfs深度优先遍历、回溯算法、分治算法等，这里只是简单介绍一下。
递归只是计算机执行一种方式，一个来回的过程，所以这个过程可以被一些算法很巧妙的运用。
分治算法：将问题分解成多个子问题，子问题求解完合并得到结果，这个过程可以使用递归实现(也可能不使用递归)，但大部分会用递归因为实现更加简洁，它和斐波那契递归不同的是它分裂的子问题一般没有重复的(即分完为止而不会重复计算)。常见的快排、归并排序都是使用分治算法，其算法实现借助递归。例如归并排序其流程：
算法实现为：
privatestaticvoidmergesort(int[]array,intleft,intright){intmid=(left+right)/2;if(leftright){mergesort(array,left,mid);mergesort(array,mid+1,right);merge(array,left,mid,right);}}privatestaticvoidmerge(int[]array,intl,intmid,intr){intlindex=l;intrindex=mid+1;intteam[]=newint[r-l+1];intteamindex=0;while(lindex=midrindex=r){//先左右比较合并if(array[lindex]=array[rindex]){team[teamindex++]=array[lindex++];}else{team[teamindex++]=array[rindex++];}}while(lindex=mid)//当一个越界后剩余按序列添加即可{team[teamindex++]=array[lindex++];}while(rindex=r){team[teamindex++]=array[rindex++];}for(inti=0;iteamindex;i++){array[l+i]=team;}}dfs、回溯法通常想着枚举尽可能多的情况,很多时候我们并不能很好知道运行界限是在哪，并且运行中状态可能会有所变化，所以我们可以写好限定条件使用递归去实现，递归的归过程也可很好的复原去进行其他试探。包括二叉树的前中后遍历都蕴涵dfs算法思想,而回溯算法则是经典全排列、八皇后问题代表。
其流程通常为：
定义回溯算法及参数-(符合条件)跳出-(不符合)不跳出：--遍历需要操作的列表该元素可操作可以继续试探---标记该元素已使用以及其他操作---递归调用(参数改变)---清除该元素标记以及其他操作此外，递归还在很多算法中有广泛的应用，这里就不具体列举啦！
结语
今天递归就讲到这里啦，学好递归没那么容易，还是要具体掌握各种算法、题目才能慢慢领略递归精髓，递归用好可以写出很多骚代码！
不过实际题目注重效率和便捷，不能盲目追求效率，也不能盲目使用递归不注意算法优化。
其他：汉诺塔动图截取自开源作者isea的开源作品，原创不易，希望大家点赞、在看三连支持一下！
