J2SE快速进阶――递归算法

递归算法

递归，百度百科对其定义为：程序调用自身的编程技巧。说白了就是一个函数或者过程在执行时会调用自身。

先用一个 “ 求一个数的阶乘 ” 的例子来说明 ：

public class Test {
	public static void main(String[] args) {
		System.out.println(Method(3));
	}
	public static int Method(int n){
		if(n==1)
			return 1;
		else
			return n*Method(n-1);				
	}	
}

当n=3时，执行else下的return 3*Method(2)，Method(2)即以2为实参重新调用了函数Method()本身；同理，n=2时，执行else下的return 2*Method(1)；n=1时，直接返回1。

到了这里会发现，递归可以把一个大型、复杂的问题层层转化为一个与原问题相似的的规模较小的问题来求解，只需要少量的程序代码就可以描述出解题过程需要的多次重复计算，大大减少了程序的代码量。

递归有以下特点：<??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+ICAgICAgIDGhorXduenKtc/WyrGjrMrHsNHSu7j2zsrM4tequ6/OqsDgJiMyMDI4NDu1xLnmxKO9z9ChtcTOyszio6y2+NXiuPbQwrXEzsrM4tPr1K3OyszitcS94r72t723qM/gzayjrNa7yse0psDtttTP87K7zayjrM2ouf224LTOtd256bXDs/bX7rzytaW1xL3io6zIu7rz1vCy48/yyc+3tbvYtffTw6OstcO1vdfu1tW94qGjo7s8L3A+CjxwPiAgICAgICAyoaK13bnp0qrT0L3hyvjM9bz+o6zTw8C01tXWudGtu7e199PDo6y8tLWxwvrX49XiuPbM9bz+yrGjrL7NsrvU2b340NC13bnpo6y38dTy0rvWsbX308Oxvsnto6zWqrXAwvrX49XiuPbM9aGjo6jJz8D91tC1xGlmKG49PTEpvs3Kx73hyvjM9bz+o6k8L3A+CjxwPiAgICAgICAzoaLL5Mi7td256dTa0ru2qLPMtsjJz8q5tPrC67Tvtb24tNPDo6y1q8nusuO0zrXEtd256bvhyea8sLW9xrW3sb341buz9tW7us231sXkxNq05r/VvOSjrMv50tTUy9DQ0KfCyrHIvc+1zaOstbHOysziuebEo73PtPPKsaOssrvNxrz2yrnTw6GjIDwvcD4KPHA+ICAgICAgIDShotTatd256bn9s8zW0KOsw7+0zrX308PW0LXEss7K/aOst723qLe1u9i146Osvtayv7Hkwb+2vMrHtOa3xdTattHVu9bQtcSjrMjnufu1sc7KzOK55sSjt8ezo7TzyrGjrMjd0tfU7LPJttHVu9Lns/ahozwvcD4KPHA+IDwvcD4KPGgzPiAgICAgICA8c3Ryb25nPrXduenKtc/WtcTKtcD9PC9zdHJvbmc+PC9oMz4KPHA+ICAgICAgzqrBy7zTye7Toc/zo6zV4sDvt9bP7by4uPa/ydLU08O13bnpwLTKtc/WtcTQocD919M8L3A+CjxwPiAgICAgIDGhosfzMSYjNDM7MiYjNDM7MyYjNDM7oa2hrSYjNDM7MTAwILXEus0gICA8L3A+CjxwcmUgY2xhc3M9"brush:java;">public class Sum { public static void main(String[] args) { System.out.println(sum(100)); } public static int sum(int num){ if(num <= 0){ return 0; //当num=0时，循环结束 }else{ return num + sum(num-1); //调用递归方法 } } 2、十进制数转化为二进制数

public class DecimalToBinary {
	public static void main(String[] args) {
		DecimalToBinary(118);
	}
	public static void DecimalToBinary(int num){
        	if(num ==0){                    //当num=0时，循环结束
               	       return;
       	        }else{
                      DecimalToBinary(num/2);  //调用递归方法
                      System.out.print (num%2);
       	        }
        }  
}

public class Fibonacci{
	public static void main(String[] args) {
		System.out.println(fib(4));
	}
   static int fib(int n)  
	{  
	   if(n==0||n==1)  
	       return n;  	    
	   else  
	       return fib(n-1)+fib(n-2);  
	}  
}

递归与迭代的区别

一些初学者有时可能会把递归和迭代这两种算法混淆，递归是一个函数（或过程）通过不断对自己的调用而求得最终结果的一个算法，迭代则可以看做循环。

文章开头的例子可以用迭代实现如下：

public class Test {
	public static void main(String[] args) {
		System.out.println(Method(3));
	}
	public static int Method(int n){
		int product=1;
		for(int i=n;i>0;i--){
			product=product*i;
		}
		return product;		
	}
}

从代码中可以发现，迭代只是单纯的循环，从i=n一直循环到i=1，最后直接返回最终解product即可；而递归则是把亟待解决的问题转化成为类似的规模较小的问题，通过多次递归得出最简单的解，然后逐层向上返回调用，得到最终解。这里递归就像我们爬山，一个台阶一个台阶爬到山顶后，最终还是要一个台阶一个台阶下山的道理一样。