Java遞歸方法

什么是方法遞歸？我們先來看一段代碼：

public class RecursionTest01 {
	public static void main(String[] args) {
		m();
	}
	public static void m(){
		System.out.println("m begin");
		m();
		System.out.println("m over");
	}
}

以上代碼的執行結果如下圖所示：

圖7-17：遞歸執行結果

我們可以看到以上代碼的執行過程中，一直輸出“m begin”，“m over”一次也沒有輸出，直到最終發生了錯誤：java.lang.StackOverflowError，這個錯誤是棧內存溢出錯誤，錯誤發生后，JVM退出了，程序結束了。

實際上以上代碼在m()方法執行過程中又調用了m()方法，方法自身調用自身，這就是方法遞歸調用。以上程序實際上等同于以下的偽代碼（說明問題，但是無法執行的代碼）：

圖7-18：說明遞歸執行原理的偽代碼

通過偽代碼我們可以看出，m()方法一直在被調用（方法中的代碼必須遵循自上而下的順序依次逐行執行，不能跳行執行），對于棧內存來說一直在進行壓棧操作，m()方法從未結束過，所以沒有彈棧操作，即使棧內存足夠大（也是有限的內存），總有一天棧內存會不夠用的，這個時候就會出現棧內存溢出錯誤。通過以上研究得出遞歸必須要有合法的結束條件，沒有結束條件就一定會發生StackOverflowError。我們再來看看有結束條件的遞歸，例如以下代碼：

圖7-19：遞歸的過程中滿足了某個條件，遞歸結束了

綜上所述，遞歸其實就是方法在執行的過程中調用了另一個方法，而另一個方法則是自己本身。在代碼角度來看就是在a()方法中調用a()方法，使用遞歸須謹慎，因為遞歸在使用的時候必須有結束條件，沒有結束條件就會導致無終止的壓棧，棧內存最終必然會溢出，程序因錯誤的發生而終止。

大家再來思考一個問題，一個遞歸程序有合法有效的結束條件就一定不會發生棧內存溢出錯誤嗎？在實際開發中遇到這個錯誤應該怎么辦？

一個遞歸程序有的時候存在合法有效的終止條件，但由于遞歸的太深，在還沒有等到條件成立的時候，棧內存已經發生了溢出，這種情況也是存在的，所以實際開發中我們盡可能使用循環來代替遞歸算法，原則是：能不用遞歸盡量不用，能用循環代替的盡可能使用循環。當然，如果在開發中遇到了由于使用遞歸導致棧內存溢出錯誤的發生，首先，我們要檢查遞歸的終止條件是否合法，如果是合法的還是發生棧內存溢出錯誤，那么我們可以嘗試調整堆棧空間的大小。怎么調整堆棧大小呢，大家可以研究一下下圖中的一些參數，這里就不再講解內存大小的調整了，這不是初級程序員應該掌握的。

圖7-20：java虛擬機內存設置參數

接下來我們來研究一下在不使用遞歸的前提下，完成1~N的求和，這個應該很簡單，請看下面代碼：

public class RecursionTest02 {
	public static void main(String[] args) {
		int n = 5;
		int result = accumulate(n);
		System.out.println("1到" + n + "的和是：" + result);
	}
	public static int accumulate(int n){
		int result = 0;
		for(int i = 1;i <= n; i++){
			result += i;
		}
		return result;
	}
}

運行結果如下圖所示：

圖7-21：不使用遞歸計算1~N的和

那么，使用遞歸應該怎么寫呢？請看以下代碼：

public class RecursionTest03 {
	public static void main(String[] args) {
		int n = 5;
		int result = accumulate(n);
		System.out.println("1到" + n + "的和是：" + result);
	}
	public static int accumulate(int n){
		if(n == 1){
			return 1;
		}
		return n + accumulate(n - 1);
	}
}

運行結果如下圖所示：

圖7-22：使用遞歸計算1~N的和

我們來使用偽代碼對以上代碼的執行過程進行分析，請看以下偽代碼：

public static int accumulate(int n){ //假設n是5
	if(n == 1){
		return 1;
	}
	return n + accumulate(n - 1);
	//return 5 + accumulate(4);   		return 5 + 4 + 3 + 2 + 1;
}
public static int accumulate(int n){
	if(n == 1){
		return 1;
	}
	return n + accumulate(n - 1);
	//return 4 + accumulate(3);				return 4 + 3 + 2 + 1;
}
public static int accumulate(int n){
	if(n == 1){
		return 1;
	}
	return n + accumulate(n - 1);
	//return 3 + accumulate(2);				return 3 + 2 + 1;
}
public static int accumulate(int n){
	if(n == 1){
		return 1;
	}
	return n + accumulate(n - 1);
	//return 2 + accumulate(1);				return 2 + 1;
}
public static int accumulate(int n){
	if(n == 1){
		return 1; //這行代碼執行了			return 1;
	}
}

以上程序的內存變化是這樣的，請看下圖：

圖7-23：1~N遞歸求和內存圖

為了加強大家對遞歸算法的理解，我們再來看一張圖：

圖7-24：另一種形式的遞歸內存圖

其實大家把上圖逆時針旋轉90度，你會看到一個棧數據結構對嗎？