黑马程序员技术交流社区

标题: 这递归哪用错了？ [打印本页]
作者: 陈延真    时间: 2013-6-6 23:01
标题: 这递归哪用错了？
本帖最后由 陈延真 于 2013-6-9 22:59 编辑

//求出这列数列的第20项的值：  1,1,2,4,7,13...
public class Demo {
public static void main(String[] args) {
  System.out.println(f(20));
}

public static int f(int n) {
  if (n == 1 || n == 2) {
   return 1;
  } else {
   return f(n - 1) + f(n - 2) + f(n - 3);
  }
}
}
作者: 张歆明    时间: 2013-6-7 00:13
我先说递归使用的条件是什么
1. 基准情形：必须有某些基准情形，不用递归就能解决
2. 不断推进：就是对于那些要被递归的清形， 递归调用必须总能够朝着一个基准的情形推进。
现在 我按照毕向东老师的画图的方法  给你指一下你的问题：
见图
所以 就出现问题了

对于这样的含有递推公式的递归程序 你这样做你比较好
f(n) =f(n-1)+ f(n-2) +f(n-3)这个是递推公式吧

那么  你的起始项是不是n=1  所以 你这里面 是不是要
n-1 >=1
n-2>=1
n-3>=1
三个不等式取交集  得到的n的范围是 n>=4
所以 f(n) =f(n-1)+ f(n-2) +f(n-3)成立的条件必须是n>=4才能使用  那么 n<4 (n为整数)  也就是 n=1 n=2和n =3的时候  上面的递推公式不满足 你是不是要自己定义取值啊


f(1) =1
f(2) =1
f(3) =2
这三个值才叫基准值 你少定义了一个


我写了一下代码 你看看：
//求出这列数列的第20项的值：  1,1,2,4,7,13...
public class Demo {
        public static void main(String[] args) {
                System.out.print("f("+1+") ="+ f(1)+" ");
                System.out.print("f("+2+") ="+ f(2)+" ");
                System.out.print("f("+3+") ="+ f(3)+" ");
                System.out.print("f("+4+") ="+ f(4)+" ");
                System.out.print("f("+5+") ="+ f(5)+" ");
                System.out.print("f("+6+") ="+ f(6)+" ");
                System.out.print("f("+7+") ="+ f(7)+" ");
        }

        public static int f(int n) {
          if (n == 1 || n == 2)
           return 1;
          else if( n==3)
                  return 2;
          else
           return f(n - 1) + f(n - 2) + f(n - 3);
        }
}



xls.jpg (27.58 KB, 下载次数: 0)

你的递归出现的问题

你的递归出现的问题

result.jpg (14.64 KB, 下载次数: 0)

我运行的结果

我运行的结果
作者: 花心々小土豆    时间: 2013-6-7 08:31
  1. //求出这列数列的第20项的值：  1,1,2,4,7,13...
  2. public class DiguiDemo
  3. {
  4.         public static void main(String[] args)
  5.         {
  6.                 System.out.println(f(5));
  7.         }

  9.         public static int f(int n)
  10.         {
  11.                 if (n == 1 || n == 2)
  12.                 {
  13.                         return 1;
  14.                 }
  15.                 else if (n==3)                                //少了一个初始条件
  16.                 {
  17.                         return 2;
  18.                 }
  19.                 else
  20.                 {
  21.                         return f(n - 1) + f(n - 2) + f(n - 3);
  22.                 }
  23.         }
  24. }
复制代码
作者: 刘晓    时间: 2013-6-7 08:54
本帖最后由 刘晓 于 2013-6-7 08:58 编辑

问题出在：当n=3时，方法中的f（n-3）=f（0），而f（0）你没有在程序中声明出来，也没有f（0）这一项。因此你必须改成上面说的，你应该n从4取值。或者你也可以改成这样..........
  1. public class test
  2. {     
  3.         
  4.                 public static void main(String[] args) {
  5.                   System.out.println(f(20));
  6.                 }

  8.                 public static int f(int n) {
  9.                   if (n == 1 || n == 2)
  10. {
  11.       return 1;
  12. }
  13.                   else
  14. {
  15.       return f(n-1 ) + f(n-2 ) ;  //后面一项等于前面两项相加，那干嘛要来三个f（）呢。俩足够！！！
  16. }
  17.                 }
  18.                 }
复制代码
作者: 陈延真    时间: 2013-6-7 18:43
张歆明 发表于 2013-6-7 00:13
我先说递归使用的条件是什么
1. 基准情形：必须有某些基准情形，不用递归就能解决
2. 不断推进：就是对于那 ...

也太牛了点。。。
作者: 张歆明    时间: 2013-6-7 18:56
陈延真 发表于 2013-6-7 18:43
也太牛了点。。。

不客气 好  帮到你我很高兴
作者: xiaohu1218    时间: 2013-6-8 16:51
这个递归类似斐波那契数列，算法很容易理解。
但是在使用递归的时候，就需要弄清楚需要指定数值的那些项，并将其全部赋值；
在这个递归程序中，楼主考虑情况时忽略了f(3)这个基础数据值;
由于没有指定f(0)的值，因而会出错。
在这里给楼主提几点小建议：
1函数命名时最好选择有异议的名字，养成好的习惯很重要哦；
2分条件时考虑全面一些，比方说 如果输入负数 或者是 0 ，应提示输入的数据错误；
相信楼主细心些就不会再出现类似的问题
作者: 袁梦希    时间: 2013-6-9 14:57
楼主你好  如果帖子的问题已经解决，请把帖子的类型改为“已解决”。{:soso_e102:}



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