java递归算法(经典实例——1加到100)

java递归算法

信任小伙伴们都有听说过斐波那契数列。这个著名的数列也叫“兔子数列”。
没听说的话也没关系，咱们一起来探究一下所谓的兔子数列。
话说我家兔子在出世两个月后，就有了繁衍能力可以生下小兔子。假设一对有繁衍力的兔子每个月能生出一对小兔子（一雄一雌）来。假如一年后所有兔子都不死，那么我家刚出世的一对小兔子一年以后可以繁衍多少只兔子？
这是个风趣的问题。依照推算，咱们可以得到这样的一组数列：0、1、1、2、3、5、8、13、21、34……
咱们分析得知：3月=2月+1月；4月=3月+2月……12月=11月+10月。
所以咱们最终得到12月=11月+10月=10月+9月+10月=……
那么运用java，怎样写出这个算法呢？如图：
咱们界说一个办法m，该办法入参是月份，出参是该月出世的兔子的对数。咱们想得到12月出世多少对兔子，所以调用该办法应该是：m(12);咱们知道每个月出世的兔子为上两个月之和，于是m(12)办法的主要逻辑是m(11)+m(10);也就是代码中的：
inti=m(month-1)+m(month-2);
然后在该代码中又调用了两次m办法，分别传入前两个月的月份，由此m(month-1)和m(month-2)又可以再次拆分。可是这样拆分的话，会出现死循环。所以，咱们必须要跳出循环。咱们必须让拆分在某个月得到详细的成果，不再进行办法自己内部调用自己，这样就可以计算出成果了。
这种通过反复自调用来解决问题的思想叫做递归。
有些互联网公司在面试时，会经常出一些相似的笔试题。比方经典的山公吃桃的问题：山公有一树桃子，每天吃掉桃子总数的一半，可是不过瘾，又多吃掉一个。到了第十天，树上还剩下一个桃子。那么第一天树上原始的桃子数量是多少？
这一题咱们本次不做讨论，留给小伙伴们自己去用代码实现。下一篇文章里咱们会给出代码。

经典实例——1加到100

剖析：首先咱们要明白标题的意思指的是每个月的兔子总对数；假设将兔子分为小中大三种，兔子从出世后三个月后每个月就会生出一对兔子，
那么咱们假定榜首个月的兔子为小兔子，第二个月为中兔子，第三个月之后就为大兔子，那么榜首个月分别有1、0、0，第二个月分别为0、1、0，
第三个月分别为1、0、1，第四个月分别为,1、1、1，第五个月分别为2、1、2，第六个月分别为3、2、3，第七个月分别为5、3、5……
兔子总数分别为：1、1、2、3、5、8、13……
所以得出了一个规则，从第三个月起，后面的兔子总数都等于前面两个月的兔子总数之和，即为斐波那契数列。
publicclassTest{
publicstaticvoidmain(String[]args){
inti=1;
for(i=1;i<=20;i++){
System.out.println(“兔子第”+i+”个月的总数为:”+f(i));
}
}
publicstaticintf(intx){
if(x==1||x==2){
return1;
}else{
returnf(x-1)+f(x-2);
}
}
}
从1到100相加：
publicclassDigui{
publicintsum(inti){
if(i==1){
return1;
}
returni+sum(i-1);
}
publicstaticvoidmain(String[]args){
Diguitest=newDigui();
System.out.println(“核算结果：”+test.sum(100)+”!”);
}
}
从1到100阶乘：
需求留意的是核算后的结果数值过大程序无法回来，一般状况会回来0！那么用int、long是无法满足的，所以要用BigInteger
publicclassDigui{
publicBigIntegersum(inti){
if(i==1){
returnBigInteger.ONE;
}
returnBigInteger.valueOf(i).multiply(sum(i-1));
}
publicstaticvoidmain(String[]args){
Diguitest=newDigui();
try{
System.out.println(“核算结果：”+test.sum(50)+”!”);
}catch(Exceptione){
//TODOAuto-generatedcatchblock
e.printStackTrace();
}
}
}
别的提别提醒下真实项目中要稳重运用递归算法，大致总结下递归算法的优缺点：
长处：
代码更简练明晰，可读性更好
缺点：
由于递归需求系统堆栈，所以空间耗费要比非递归代码要大很多。并且，如果递归深度太大，可能系统撑不住。