大家好，我是bigsai，之前有个师兄说不懂递归，今天给大家讲讲递归。什么是递归？递归：函数调用自身。子问题必须与原始问题相同，或者更简单。递归通常是处理子问题的一种简单方法，但不一定是最佳解决方案。对于递归，要区分以下几个概念：递归是调用自身。递归通常不关心具体的操作，只关心初始条件、结束条件以及上下层变化的关系。递归函数需要有一个临界停止点（结束条件），即递归不能无限执行下去。通常这个点是一个必须通过的数字。递归可以用栈代替。可以优化一些递归。比如遇到重复性的问题，可以借助空间内存记录来减少递归的次数来理解递归。递归函数通常看起来很简单，但初学者可能很难理解。以递归函数为例。staticvoiddigui(){System.out.println("beforebigsai");digui();System.out.println("afterbigsai");}这是递归吗？它不是一个正常的递归，没有结束条件，并且它被持续调用本身会导致无限循环。正确的递归应该是这样的时间-1);System.out.println("timeafterbigsai:"+time);}}对于这样一个递归，其过程大致如下：定义递归算法和参数-停止递归算法条件-（可能存在）其他逻辑-递归调用(需要改参数)-(可能存在)其他逻辑所以，调用digui(5)，控制台输出是这样的。那么，我想你应该对递归函数执行的流程有所了解。递归求阶乘初学递归，接触最多的就是递归阶乘，为什么阶乘可以用来求递归呢？我们先来看阶乘，n的阶乘表示为：n!=n*(n-1)*...*1n的阶乘由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);}}其实，它的调用过程是：但是这个Fibonacci是这样的找方法的效率不高，后面会提到。递归求解汉诺塔汉诺塔是一个经典的递归问题：相传在古印度神庙中，有一种游戏叫汉诺塔（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)。如果有更多，那么它会爆炸。可以发现，每增加一步，就会多出很多步。如果一步一步去想，是很难理解的，所以要用递归全局的思路看问题。当有一个要从A->C走时，这里用函数move(A,C)来表示（其他移动操作同理）。用hannuo(n)函数表示从A->C一共需要走n个盘子。递归，其实就是找上下层的关系。把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(需要往下用),所以在汉诺(n-1,A,B,C)中传B首先表示为从A开始从n-1开始(带帮助B执行几个操作）转到C。这一系列操作使得从A移动n个板->B但我们想要的是A->C是所需的hannuo（n，A，B，C）。这很容易。我们只需要第一步移动n-1个就可以移动到B了。经过上面的分析，完整的操作就是：包递归；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移动到b移动(a,c);//将第n个（最后一个）从a移动到c。hannuota(n-1,b,a,c);//通过a将n-1从b移动到c}}publicstaticvoidmain(String[]args){hannuota(5,'a','b','c');}}这样，汉诺塔问题就明白了吗？RecursionVSMemoization很多时候递归的效率很低（将一个递归拆分成两个或多个子问题效率不高。），我们需要使用动态规划或者memoization来优化，为什么需要memoization？因为递归成子问题，再把子问题拆分成子问题，导致重复计算很多！比如上面提到的递归斐波那契数列，就是一个非常低效的算法。比如你看F(5)是怎么走的：当F(4)递归计算的时候，F(4)会递归求解F(3)，但是右边的又会重新执行一次。如果它是一个非常大的数字，它将花费很多时间。所以我们可以采用记忆！第一次计算结果时保存。如果是线性且规则的（大部分），就用数组，否则用HashMap来存储。具体实现代码为：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很大的时候（递归是指数增长，memoization是线性的）。比如一个F(6)的解法过程：当然，记忆的问题要多得多，需要自己去学习。递归VS数据结构递归在很多场景下都有很好的应用，在链表、二叉树、图（搜索算法）中都有很多应用。这里有一些非常经典的例子。比如在链表中，经典的问题就是链表的逆序输出和链表的倒序。链表），可以这样巧妙的实现：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深度优先遍历、回溯算法、分而治之算法等，这里只是简单介绍一下。递归只是计算机执行的一种方式，一个来回的过程，所以这个过程可以被一些算法巧妙地利用。分而治之算法：将问题分解成多个子问题，求解子问题并组合得到结果。这个过程可以使用递归来实现（也可以不使用递归），但是大部分都会使用递归，因为实现起来更简洁。它与Fibonacci契据递归的区别在于，它拆分出来的子问题一般不会有重复（即直到拆分结束，子问题才会重复计算）。常见的快速排序和归并排序都是使用分而治之算法，算法是借助递归实现的。例如合并排序的过程：算法实现为：privatestaticvoidmergesort(int[]array,intleft,intright){intmid=(left+right)/2;if(left
