这篇文章比较长，建议大家仔细耐心的看完，相信会有很大的收获。一、最有启发的汉诺塔问题1、汉诺塔问题描述有A、B、C三个极点，A杆上有N（N>1）个穿孔圆盘，圆盘的大小从下往上递减到达顶点。要求将所有圆盘按照以下规则移动到C杆上：一次只能移动一个圆盘；大圆盘不能叠放在小圆盘上面。问：最少的步数是多少？并打印每一步的情况。2、从一开始，我们的目标是将圆盘1、2、3从左边的杆子移到右边的杆子上，可以拆解为以下三个步骤1）（大步）将圆盘1、2从lefttothemiddlepole2)从左边移动3个盘子到右边的杆子3)（大步）从中间的杆子移动1和2个盘子到右边的杆子代码如下：/***@authorJavaandAlgorithm学习：星期一*/publicstaticvoidleftToRight(intn){if(n==1){//基本情况System.out.println("从左到右移动1");返回;}//1,1到n-1圈磁盘从左到中leftToMid(n-1);//2、从左到右System.out.println("从左到右移动"+n+"");//3,1ton-1DiscfrommiddletorightmidToRight(n-1);}整个从左到右的方法，你会发现第一个大步依赖于从左到中的子方法，第三个大步取决于中间到右边的子方法，然后你去补左边到中间的方法，中间到右边的方法；这时候你会发现，左到中依赖于左到右和右到中的方法，中间到右依赖于中到左和左到右的方法……/***@authorJava和算法学习：周一*/privatestaticvoidleftToMid(intn){if(n==1){System.out.println("从左到中移动1");返回;}leftToRight(n-1);系统。out.println("从左到中移动"+n+"");rightToMid(n-1);}privatestaticvoidmidToRight(intn){if(n==1){System.out.println("从中间向右移动1");返回;}midToLeft(n-1);System.out.println("莫ve"+n+"从中到右");leftToRight(n-1);}privatestaticvoidrightToMid(intn){if(n==1){System.out.println("将1从右移到mid");return;}rightToLeft(n-1);System.out.println(“移动”+n+“从右到中”);leftToMid(n-1);}privatestaticvoidmidToLeft(intn){if(n=1){System.out.println("从中间向左移动1");return;}midToRight(n-1);System.out.println("从中间移动1+n+"向左");rightToLeft(n-1);}privatestaticvoidrightToLeft(intn){if(n==1){System.out.println("将1从右移到左");返回;}rightToMid(n-1);System.out.println("Move"+n+"从右到左");midToLeft(n-1);}最后你会发现左到中、左到右、中到左、中到右、右到左、右到中这6个方法相互依赖完成了汉诺塔问题不是有点神奇，递归有时是有点玄学，但只是要把把子吅基地过，程渘惘（（（）需要一点点点思维点点宏观点宏观点点思维点，，，优化，优化个个个个个from、to、other三个变化量，他们都可以表示左、中、右。当我从左到右时，from=left,to=right,other=middle;从左到中，from=left，to=middle，other=right...六合一的龙能召唤出来吗？也拆解成以下三步1）（大步）将1、2个圆盘（即上面的n-1个圆盘）从左边移动到中间的极点2）移动3个圆盘（即最大的圆盘)fromMovelefttotherightpole3)(bigstep)从中间向右极点移动1和2个圆盘（即上面的n-1个圆盘）/***第一次调用该函数时：from=left,to=right,other=middle*表示使用other=middle将磁盘从from=left移动到to=right**@authorJava与算法学习：星期一**@paramn磁盘总数*@paramfromstartingposition*@paramtotargetposition*@paramotherremainingpole*/publicstaticvoidfunction(intn,Stringfrom,Stringto,Stringother){if(n==1){System.out.println("将1从"+from+"移动到"+to);返回;}//1.将上面的n-1个盘子从左边移到中间的极点，//即起始位置在左边，当前from=Left;目标位置，当前other=middlefunction(n-1,from,other,to);//2.将最大的圆盘从左极移到右极System.out.println("Move"+n+"from"+from+"to"+to);//3.将上面的n-1个棋子从中间移到右边的极点//即起始位置为middle，当前other=middle;targetpositionisright,Currentlyto=rightfunction(n-1,other,to,from);}这个时候我们学会了一个trick，一个递归函数可以通过加参数来表达更多的可能性，听起来有点废话，但现在你又尝到了。但是，如果没有前面的启蒙过程，直接理解有点困难；在悟的过程中，看是不是一下子就清楚了。上课听老师讲解汉诺塔的时候，你有没有发现自己一头雾水？如果那时老师能这么说，你一定会明白的。掌声（和喜欢）就在这里。让我们一起来看看几个递归过程。二、打印一个字符串的所有子序列1、子序列定义对于字符串“12345”，0、1、2、3、4、5中的任意一个都是它的子序列，同时不能改变相对顺序。对于字符串“123”，我们可以很容易地分析出如下递归过程2.代码/***@authorJava与算法学习：Monday*/publicstaticListgetAllSubSequences(Strings){char[]str=s.toCharArray();Listanswer=newArrayList<>();字符串路径="";process1(str,0,答案,路径);returnanswer;}/***当前在str[index]字符*str[0..index-1]已经过去了，之前的选择都在路径上，之前的选择不能改变，就是路径。*但str[index....]也可以自由选择，将str[index....]生成的所有子序列都放入答案中**@paramstr指定字符串（固定）*@paramindex当前位置*@paramanswer之前的决策依据产生的答案*@parampath之前已经做出的选择*/publicstaticvoidprocess1(char[]str,intindex,Listanswer,Stringpath){//目前在字符串的末尾，不能再做决定，answer只能放到之前的决定中if(index==str.length){answer.add(path);返回;}//当前没有索引位置的字符process1(str,index+1,answer,path);//索引位置的当前字符process1(str,index+1,answer,path+str[index]);}process1方法就是上面递归分析出来的方法。3.打印一个字符串的所有子序列，没有重复值。打印字符串的所有子序列而不重复文字子序列。只需将上面的List替换为Set即可删除重复项。/***打印一个字符串的所有子序列，不需要重复字面值的子序列**@authorJava与算法学习：星期一*/publicstaticSetgetAllSubSequencesNoRepeat(Strings){char[]str=s.toCharArray();Setanswer=newHashSet<>();字符串路径="";process2(str,0,答案,路径);返回答案;}publicstaticvoidprocess2(char[]str,intindex,Setanswer,Stringpath){if(index==str.length){answer.add(path);返回;}process2(str,index+1,answer,path);process2(str,index+1,answer,path+str[index]);}4.打印一个字符串的所有全排列1.全排列定义需要所有字符，只是顺序不同。2.使用舍弃相加的方法(1)递归过程如下。当我在第一列中选??择a时，会形成一些结果。我在第二列递归的时候，要加一个back，保持原来的abc，在第二大列选择b的时候递归得到的结果是正确的。对于每列中的每个位选择都是如此。递归结束后，必须还原场景。(2)代码/***1.增删改查方式**@authorJava与算法学习：星期一*/publicstaticListpermutation1(Strings){Listanswer=newArrayList<>();如果(s==null||s.length()==0){返回答案;}ArrayListstrList=newArrayList<>();对于(charc:s.toCharArray()){strList.添加（c）；}}字符串路径="";process1(strList,path,answer);returnanswer;}/***递归获取全数组**@paramstrList当前参与选择的所有字符*@parampath之前做出的选择*@paramanswer最后结果*/privatestaticvoidprocess1(ArrayListstrList,Stringpath,Listanswer){//当前没有可以选择的字符，answer只能放在之前的选择中if(strList.isEmpty()){answer.add(path);返回;}for(inti=0;ipermutation2(Strings){Listanswer=newArrayList<>();如果(s==null||s.length()==0){返回答案;}char[]str=s.toCharArray();process2(str,0,答案);returnanswer;}/***递归获取完整数组**@paramstr当前交换后的字符*@paramindex当前交换位置在哪里*@paramanswer结果*/privatestaticvoidprocess2(char[]str,intindex,Listanswer){//目前在字符串的最后位置，不能再交换，answer只能把交换后的字符放在前面if(index==str.length){answer.add(String.valueOf(str));返回;}}//之前的index已经交换过，不能再改变，所以可以从index往前交换for(inti=index;ipermutation3(Strings){Listanswer=newArrayList<>();如果(s==null||s.length()==0){返回答案;}char[]str=s.toCharArray();process3(str,0,答案);returnanswer;}/***递归获取全数组，无重复字符串**@paramstr交换后的当前字符*@paramindex当前交换位置在哪里*@paramanswerresult*/privatestaticvoidprocess3(char[]str,intindex,Listanswer){//我们已经到了字符串的最后位置，不能再交换了。answer只能放交换后的字符if(index==str.length){answer.add(String.valueOf(str));返回;}boolean[]visited=newboolean[256];//在index之前已经交换过，不能再改变，所以可以从index往前交换str[i]的位置之前没有出现过，否则忽略if(!visited[str[i]]){visited[str[i]]=true;//index,i交换swap(str,index,i);indexc(str,index+1,answer)后继续交换；//index,i位置恢复现场交换(str,index,i);}}}}2.为什么不使用Set去重呢？仔细看上面的代码，发现并没有使用Set这个方法去重，为什么呢？因为使用Set去重，程序会重复对同一个字符做很多递归操作，将同一个字符串放入Set中，由Set去重；并且采用上述方法，不会对同一个字符重复递归，有效减少了重复分支的递归操作。俗称剪枝，相当于对Set的结果进行过滤和去重，而上面的方法就是在中间进行去重。六、栈的倒序给你一个栈，请把这个栈倒序，不能申请额外的数据结构，只能用递归函数。如何实现？1.获取栈底元素(1)代码/***获取栈底元素，其余元素直接下沉**比如从栈顶到栈底的元素分别是1,2,3,4,5*this方法返回5，从栈顶到栈底剩下的元素分别是1,2,3,4**@authorJava与算法学习：星期一*/privatestaticintgetDown(Stackstack){intresult=stack.pop();如果(stack.isEmpty()){返回结果；}else{intlast=getDown(stack);stack.push（结果）；最后返回；/***@authorJava和算法学习：星期一*/publicstaticvoidreverse(Stackstack){if(stack.isEmpty()){return;}intdown=getDown(堆栈);反向（堆栈）；stack.push(down);}(2)Process本文所有代码Github地址：https://github.com/monday-pro/algorithm-study/tree/master/src/basic/dynamicprogramming/recursionGitee地址：https://gitee.com/monday-pro/algorithm-study/tree/master/src/basic/dynamicprogramming/recursion怎么样，是不是如沐春风？
