A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 咖啡苏克 中级黑马   /  2014-7-10 16:10  /  1031 人查看  /  2 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

我知道递归算法是在方法的内部,直接或者间接地调用自己的算法,有没有案例,递归都用在什么环境?

2 个回复

倒序浏览
案例不计其数。小案例比如求n的阶乘即n! = n*(n-1)*(n-2)*....*1

  1. int factorial(int n) {
  2.     if(n <= 1)
  3.         return n;
  4.     return n * factorial(n - 1);
  5. }
复制代码


大一点的案例,比如快速排序(http://bbs.itheima.com/forum.php?mod=viewthread&tid=127727 3楼),比如老毕视频里的递归遍历目录树。

递归的思想是把一个规模较大的问题(比如n! = n * (n-1) * (n-2)*... *1)不断分成规模较小但和原问题结构一致的子问题(n! = n * (n -1)!,因此只要求出(n-1)!,就可以算出n!),最后能分解到一种非常简单、可以直接求解的情况(n=1时,n! = 1),然后逐步往回代入,就可以解决原问题
回复 使用道具 举报
本帖最后由 jwx555 于 2014-7-10 22:05 编辑

总要重复一个行为的时候就可以想想递归。


现实中,下楼梯,人从上面开始一层一层台阶的重复下楼动作,直到到了一楼才停止。
有无限的楼梯么?没有!
所以用递归的时候特别要注意结束条件。


举个例子吧
从1加到100,我们初中就会,Java要怎么表现呢? 你要写“1+2+3+...+100” 把一百个数都打出来吗?
这样当然可笑。


  1. public class Test05 {
  2.         public static void main(String args[]){
  3.                 System.out.println(sum(100)) ;
  4.         }
  5.         
  6.         public static int sum(int a){
  7.                 if (a!=1){   //设置递归结束条件
  8.                         return a+sum(a-1) ;    //把重复的加法动作化为递归!
  9.                 }
  10.                 return 1 ;
  11.         }

  12. }
复制代码

这里用递归就可以很少量的代码完成功能,但是注意:数不能太大,递归会大量消耗内存,如果数字太大,递归量太多就会发生内存溢出错误!!

回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马