黑马程序员技术交流社区

标题: 关于递归的问题 [打印本页]

作者: 刘乃宽 时间: 2013-7-28 21:00
标题: 关于递归的问题
本帖最后由杜光于 2013-7-30 10:54 编辑

public class T1{
   public static void main(String[] args){
      int n=8;
      System.out.println("共有"+cattle(n)+"头牛！");
   }
   public static int cattle(int n){
      if(n<=0)
         return 0;
      if(n<=2)
         return 1;
      return cattle(n-1)+cattle(n-2);
   }
}

return cattle(n-1)+cattle(n-2); 这段代码是怎么执行的啊？

作者: jialihong 时间: 2013-7-28 22:49
cattle(n-1)递归一次，cattle(n-2)再递归一次

作者: 张强1 时间: 2013-7-28 23:17
cattle(n-1)递归n次，cattle(n-2)再递归n次

作者: ☆今☆ 时间: 2013-7-29 23:46
n是从8开始,调用cattle(n)就是计算cattle(8);
cattle(8),8>2,返回cattle(7)+cattle(6);结果是cattle(7)+cattle(6)
cattle(7),8大于2,返回cattle(6)+cattle(5);结果是2*cattle(6)+cattle(5)
cattle(6),7大于2,返回cattle(5)+cattle(4);结果是3*cattle(5)+2*cattle(4)
cattle(5),5大于2,返回cattle(4)+cattle(3);结果是5*cattle(4)+3*cattle(3))
cattle(4),4大于2,返回cattle(3)+cattle(2);
结果是8*cattle(3)+5*cattle(2)
cattle(3),3大于2,返回cattle(2)+cattle(1);
结果是13*cattle(2)+8*cattle(1)
cattle(2),是返回1,所以cattle(2)等于1
cattle(1),也是返回1,即cattle(1)等于1
所以结果是13*1+8*1=21.

其实迭代就是要一直就算到能得到值后,在往回计算原来等式的值.

作者: 诸隆隆 时间: 2013-7-30 00:26
说起来还真挺费劲。
cattle(n)先带入了cattle(8)，进入方法体后，8很大所以返回的是cattle(n-1)+cattle(n-2)，也就是cattle(7)+cattle(6)；
同样cattle(7)也是如此它返回的是cattle(6)+cattle(5)...总之一直这样递归下去，一直到这个值为小于2或者小于0为止，再一次一次的返回到上一次的递归，最终出结果。
具体执行说起来太麻烦，把你的代码改了改，你看看应该就能理解了。

作者: 诸隆隆 时间: 2013-7-30 00:27

package cn.itheima;
public class Demo {
public static void main(String[] args){
int n=8;
System.out.println("="+"共有"+cattle(n)+"头牛！");
}
public static int cattle(int n){
if(n<=0)
return 0;
if(n<=2)
return 1;
System.out.print("当n为"+n+"时：");
System.out.println("cattle"+(n-1)+"+"+"cattle"+(n-2)+"+");
return cattle(n-1)+cattle(n-2);
}
}

复制代码

打印看看，从最后打印的结果往回看就能明白了

作者: 赵然 时间: 2013-7-30 10:48
告诉你个分析递归方法的小技巧，虽然笨点但是很实用：列一个计算当次的函数用角标标示下，如果里面用到了其他次的也用函数加角标标示下：比如说今天的数量等于昨天的数量的2倍加一那么就可以写成：sum今=sum昨*2+1，之后你把每天的都列出来这样子等列到最终的时候不仅递归的函数式的大致表示的出来了，递归的条件也弄明白了之后就可以看着分析写代码了这样会很方便，

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2