黑马程序员技术交流社区

标题: 递归算法是如何实现的？ [打印本页]

---

作者: 咖啡苏克    时间: 2014-7-10 16:10
标题: 递归算法是如何实现的？
我知道递归算法是在方法的内部，直接或者间接地调用自己的算法，有没有案例，递归都用在什么环境？

---

作者: fantacyleo    时间: 2014-7-10 17:33
案例不计其数。小案例比如求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:02


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


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


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

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

复制代码

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

---

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

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