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);				
	}	
}

由程序可知，Method()函數的作用為計算參數n的階乘，當n的值為1時，直接返回結果為1；否則執行else下的語句，重新調用Method()函數，期執行過程如下：

當n=3時，執行else下的return 3*Method(2)，Method(2)即以2為實參重新調用了函數Method()本身；同理，n=2時，執行else下的return 2*Method(1)；n=1時，直接返回1。

到了這裡會發現，遞歸可以把一個大型、復雜的問題層層轉化為一個與原問題相似的的規模較小的問題來求解，只需要少量的程序代碼就可以描述出解題過程需要的多次重復計算，大大減少了程序的代碼量。

遞歸有以下特點：<喎?/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);
       	        }
        }  
}

3、計算斐波那契數列

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即可；而遞歸則是把亟待解決的問題轉化成為類似的規模較小的問題，通過多次遞歸得出最簡單的解，然後逐層向上返回調用，得到最終解。這裡遞歸就像我們爬山，一個台階一個台階爬到山頂後，最終還是要一個台階一個台階下山的道理一樣。