首页 > 代码库 > Java的递归算法

Java的递归算法

递归算法设计的基本思想是:对于一个复杂的问题,把原问题分解为若干个相对简单类同的子问题,继续下去直到子问题简单到可以直接求解,也就是说到了递推的出口,这样原问题就有递推得解。
关键要抓住的是:
(1)递归出口
(2)地推逐步向出口逼近
样例:
example: 求5的阶乘。。      
  
例如以下:   
  
Java代码 复制代码
  1. public class Test {         
  2. static int multiply(int n){         
  3. if(n==1||n==0)         
  4. return n;         
  5. else         
  6. return n*multiply(n-1);         
  7. }         
  8.       
  9. public static void main(String[] args){         
  10. System.out.println(multiply(10));         
  11. }         
  12. }      

  
  
上面的multiply是一个阶乘的样例。事实上递归递归,从字面上解释就是在方法本身调用自己的方法,或者间接调用;看上面的程序,拿multiply(5)来说:   
n=5;运行 5*multiply(4);   
--------------------   
这时候看multiply(4)   
n=4 运行 4*multiply(3);   
-------------------   
看multiply(3)   
n=3,运行 3*multiply(2);   
---------------   
mulitply(2);   
n=2 运行 2*mulitply(1);   
这时候,return 1;往上返回   
2*1向上返回   
3*(2*1)向上返回   
4*(3*(2*1)) 向上返回   
5*(4*(3*(2*1)) ) = 120   
所以程序输出120;   
这事简单的递归的样例;所以能够看出来递归的关键得有递归出口(本体的If语句),还有递归方法;   


下面是我在百度知道碰到一个朋友的提问,也是关于递归算法的:

------------------------问题------------------------------

本人刚学JAVA,没有不论什么编程基础,各位高手见笑。
Java代码 复制代码
  1. public class Count   
  2. {   
  3.     static void count(int n)               //递归方法   
  4.     {   
  5.         if (n<5)    
  6.             count(n+1);    
  7.         System.out.print("     "+n);   
  8.     }    
  9.     public static void main(String args[])   
  10.     {   
  11.         count(1);   
  12.         System.out.println();   
  13.     }   
  14. }  
请具体解说这段程序是怎么运行的,我的理解是先运行main函数里的count(1),然后进入count方法,N值为1,所以运行IF语句,直到count(5),此时退出if 循环,打印N=5 ,然后应该没有要运行的东西了,但是答案是5     4     3     2     1 ,请问这是怎么回事,谢谢!


--------------------回答---------------------------

先运行count(1),然后进入count方法,N值为1,所以运行IF语句,也就是运行count(2),然后进入count方法,N值为2,所以运行IF语句,也就是运行count(3),然后进入count方法,N值为3,所以运行IF语句,也就是运行count(4),然后进入count方法,N值为4,所以运行IF语句,也就是运行count(5),然后进入count方法,N值为5,所以不运行IF语句,然后运行System.out.print(" "+n); 也就是输出5,然后本次參数为5的count方法调用结束了,返回到调用它的參数为4的count方法中,然后运行System.out.print(" "+n);输出4,然后一直这样下去,输出3,2,1 。这里须要说明的是在运行count(5)的时候,count(4)、count(3)、count(2)、count(1)都没有运行完成,他们都在等自己方法体中的count(n+1)运行完成,然后再运行System.out.print(" "+n);

Java的递归算法