搜索
一、什么叫做递归？一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法；递归函数就是直接或间接调用自身的函数，也就是自身调用自己；二、一般什么时候使用递归？递归时常用的编程技术，其基本思想就是“自己调用自己”，一个使用递归技术的方法即是直接或间接的调用自身的方法。递归方法实际上体现了“以此类推”、“用同样的步骤重复”这样的思想，它可以用简单的程序来解决某些复杂的计算问题，但是运算量较大。还有些数据结构如二叉树，结构本身固有递归特性；此外，有一类问题，其本身没有明显的递归结构，但用递归程序求解比其他方法更容易编写程序，如八皇后问题、汉诺塔问题等。正因为递归程序的普遍性，我们应该学会使用递归来求解问题。直接递归程序与间接递归中都要实现当前层调用下一层时的参数传递，并取得下一层所返回的结果，并向上一层调用返回当前层的结果。至于各层调用中现场的保存与恢复，均由程序自动实现，不需要人工干预。因此，在递归程序的设计中关键是找出调用所需要的参数、返回的结果及递归调用结束的条件。三、实例（一）递归求和1+2+3+.....+npublicstaticIntegerrecursionSum(Integern){if(n0){returnn+recursionSum(n-1);}else{return0;}}（二）递归阶乘n!=n*(n-1)*(n-2)*...*1(n0)publicstaticIntegerrecursionMulity(Integern){if(n==1){return1;}returnn*recursionMulity(n-1);}（三）河内塔问题1）分析有三根相邻的柱子，标号为A,B,C，A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘，要把所有盘子一个一个移动到柱子B上，并且每次移动同一根柱子上都不能出现大盘子在小盘子上方，请问至少需要多少次移动，设移动次数为H(n）。首先我们肯定是把上面n-1个盘子移动到柱子C上，然后把最大的一块放在B上，最后把C上的所有盘子移动到B上，由此我们得出表达式：H⑴=1H(n)=2*H(n-1）+1(n1）那么我们很快就能得到H(n）的一般式：H(n)=2^n-1(n0)并且这种方法的确是最少次数的，证明非常简单，可以尝试从2个盘子的移动开始证，你可以试试。进一步加深问题（解法原创*_*）：假如现在每种大小的盘子都有两个，并且是相邻的，设盘子个数为2n，问：⑴假如不考虑相同大小盘子的上下要多少次移动，设移动次数为J(n）；⑵只要保证到最后B上的相同大小盘子顺序与A上时相同，需要多少次移动，设移动次数为K(n）。⑴中的移动相当于是把前一个问题中的每个盘子多移动一次，也就是：J(n)=2*H(n)=2*（2^n-1）=2^(n+1）-2在分析⑵之前，我们来说明一个现象，假如A柱子上有两个大小相同的盘子，上面一个是黑色的，下面一个是白色的，我们把两个盘子移动到B上，需要两次，盘子顺序将变成黑的在下，白的在上，然后再把B上的盘子移动到C上，需要两次，盘子顺序将与A上时相同，由此我们归纳出当相邻两个盘子都移动偶数次时，盘子顺序将不变，否则上下颠倒。现在回到最开始的问题，n个盘子移动，上方的n-1个盘子总移动次数为2*H(n-1），所以上方n-1个盘子的移动次数必定为偶数次，最后一个盘子移动次数为1次。讨论问题⑵，综上两点，可以得出，要把A上2n个盘子移动到B上，首先可以得出上方的2n-2个盘子必定移动偶数次，所以顺序不变，移动次数为：J(n-1）=2^n-2然后再移动倒数第二个盘子，移动次数为2*J(n-1）+1=2^(n+1）-3，最后移动最底下一个盘子，所以总的移动次数为：K(n)=2*（2*J(n-1）+1）+1=2*（2^(n+1）-3）+1=2^(n+2）-5开天辟地的神勃拉玛（和中国的盘古差不多的神吧）在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。计算结果非常恐怖（移动圆片的次数）大约是1.84467440*10^19，众僧们即便是耗尽毕生精力也不可能完成金片的移动了。2）算法介绍其实算法非常简单，当盘子的个数为n时，移动的次数应等于2^n–1（有兴趣的可以自己证明试试看）。后来一位美国学者发现一种出人意料的简单方法，只要轮流进行两步操作就可以了。首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上，根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放ABC；若n为奇数，按顺时针方向依次摆放ACB。⑴按顺时针方向把圆盘1从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘1在柱子A，则把它移动到B；若圆盘1在柱子B，则把它移动到C；若圆盘1在柱子C，则把它移动到A。⑵接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘。这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。⑶反复进行⑴⑵操作，最后就能按规定完成汉诺塔的移动。所以结果非常简单，就是按照移动规则向一个方向移动金片：如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C汉诺塔问题也是程序设计中的经典递归问题，下面我们将给出递归和非递归的不同实现源代码。3）程序实现publicclassHanoi{/****@paramn盘子的数目*@paramorigin源座*@paramassist辅助座*@paramdestination目的座*/publicvoidhanoi(intn,charorigin,charassist,chardestination){if(n==1){move(origin,destination);}else{hanoi(n-1,origin,destination,assist);move(origin,destination);hanoi(n-1,assist,origin,destination);}}//Printtherouteofthemovementprivatevoidmove(charorigin,chardestination){System.out.println(Direction:+origin+---+destination);}publicstaticvoidmain(String[]args){Hanoihanoi=newHanoi();hanoi.hanoi(3,'A','B','C');}}4.判定一系列字符串中是否有相同的内容publicstaticbooleanfun(intn,String[]a){booleanb=false;if(n==a.length){b=true;}else{for(inti=n;ia.length-1;i++){System.out.println(n++(i+1));if(a[n].equals(a[i+1])){returnfalse;}}n++;fun(n,a);}returnb;}