黑马程序员技术交流社区

标题: 怎么才能写好递归? [打印本页]

作者: 苹果核的梦想    时间: 2015-11-18 19:45
标题: 怎么才能写好递归?
  1. public static List<Department> findTopLevelDepartmentList() {
  2.         Department dept_1_1 = new Department();
  3.         dept_1_1.setId(new Long(11));
  4.         dept_1_1.setName("宣传部");

  5.         Department dept_1_2 = new Department();
  6.         dept_1_2.setId(new Long(12));
  7.         dept_1_2.setName("业务部");

  8.         Department dept_1_2_1 = new Department();
  9.         dept_1_2_1.setId(new Long(121));
  10.         dept_1_2_1.setName("业务一部");

  11.         Department dept_1_2_2 = new Department();
  12.         dept_1_2_2.setId(new Long(122));
  13.         dept_1_2_2.setName("业务二部");

  14.         dept_1_2_1.setParent(dept_1_2);
  15.         dept_1_2_2.setParent(dept_1_2);
  16.         Set<Department> children_0 = new LinkedHashSet<Department>();
  17.         children_0.add(dept_1_2_1);
  18.         children_0.add(dept_1_2_2);
  19.         dept_1_2.setChildren(children_0);

  20.         // ================================

  21.         Department dept_1 = new Department();
  22.         dept_1.setId(new Long(1));
  23.         dept_1.setName("市场部");

  24.         dept_1_1.setParent(dept_1);
  25.         dept_1_2.setParent(dept_1);
  26.         Set<Department> children_1 = new LinkedHashSet<Department>();
  27.         children_1.add(dept_1_1);
  28.         children_1.add(dept_1_2);
  29.         dept_1.setChildren(children_1);

  30.         // ---

  31.         Department dept_2_1 = new Department();
  32.         dept_2_1.setId(new Long(21));
  33.         dept_2_1.setName("开发一部");

  34.         Department dept_2_2 = new Department();
  35.         dept_2_2.setId((new Long(22)));
  36.         dept_2_2.setName("开发二部");

  37.         Department dept_2 = new Department();
  38.         dept_2.setId(new Long(2));
  39.         dept_2.setName("开发部");

  40.         dept_2_1.setParent(dept_2);
  41.         dept_2_2.setParent(dept_2);
  42.         Set<Department> children_2 = new LinkedHashSet<Department>();
  43.         children_2.add(dept_2_1);
  44.         children_2.add(dept_2_2);
  45.         dept_2.setChildren(children_2);

  46.         // ---

  47.         List<Department> depts = new ArrayList<Department>();
  48.         depts.add(dept_1);
  49.         depts.add(dept_2);
  50.         return depts;
  51.     }
复制代码

遍历方法:
  1. private void showTreeList(Collection<Department> topList) {
  2.         for (Department top : topList) {
  3.             // 顶点
  4.             System.out.println(top.getName());
  5.             // 子树
  6.             showTreeList(top.getChildren());
  7.         }
  8.     }
复制代码

递归遍历这个树,我可以看懂示例代码,可到自己写就绕晕了,有没有什么技巧?请指教。。。
作者: 半指流沙    时间: 2015-11-18 20:23
感谢分享....................
作者: Aaron_wang    时间: 2015-11-19 21:36
递归调用使用的场景是能将问题的规模逐渐减小,并且有一个递归结束条件,问题规模会趋于这个结束条件,搞清这两点我觉得就好了。下面给你两个例子感受下,很简单:
  1. /**
  2. * 需求:有5个人坐在一起,问第五个人多少岁,他说比第4个人大2岁,第4个人比第3个人大2岁
  3. * 第3个人比第二个人大2岁,第2个人又比第1个人大2岁,第一个人说他/她10岁,求第5个人多大。
  4. *
  5. * 分析:使用递归调用:递归调用是指所处理的问题的规模在递增或递减,并且有一个结束递归的条件,递归函数有返回值。
  6. */
  7. class  DiGui
  8. {
  9.         //static int age;//定义成员变量:全局的;静态变量:被静态方法调用
  10.         public static void main(String[] args)
  11.         {
  12.                 System.out.println(getAge(5));
  13.         }
  14.         public static int getAge(int i)
  15.         {
  16.                 int age;
  17.                 if(i==1)//递归结束的条件
  18.                 {
  19.                         age = 10;
  20.                 }
  21.                 else
  22.                         age = getAge(--i)+2;//反复调用自身,使问题规模变小,趋于结束
  23.                 return age;
  24.         }

  25. }
复制代码

  1. /**
  2. * 需求:用递归方法求n!
  3. * 分析:递归结束条件是变量为1时,返回1
  4. */
  5. class  DiGui1
  6. {
  7.         public static void main(String[] args)
  8.         {
  9.                 int n = 10;
  10.                 System.out.println(n+"!="+muti(n));
  11.         }
  12.         public static int muti(int n)
  13.         {
  14.                 int result;
  15.                 if(n==1)//递归结束条件
  16.                         result = 1;
  17.                 else
  18.                         result = muti(n-1)*n;//
  19.                 return result;
  20.         }

  21. }
复制代码


作者: 苹果核的梦想    时间: 2015-11-22 14:33
Aaron_wang 发表于 2015-11-19 21:36
递归调用使用的场景是能将问题的规模逐渐减小,并且有一个递归结束条件,问题规模会趋于这个结束条件,搞清 ...

谢谢你,我研究研究
作者: Little_jie    时间: 2015-11-22 14:43
研究下,学习下




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