遞歸的思想
以此類推是遞歸的基本思想。
具體來講就是把規模大的問題轉化為規模小的相似的子問題來解決。在函數實作時，因為解決大問題的方法和解決小問題的方法往往是同一個方法，是以就産生了函數調用它自身的情況。另外這個解決問題的函數必須有明顯的結束條件，這樣就不會産生無限遞歸的情況了。
遞歸的兩個條件
- 可以通過遞歸調用來縮小問題規模，且新問題與原問題有着相同的形式。（自身調用）
- 存在一種簡單情境，可以使遞歸在簡單情境下退出。（遞歸出口）
遞歸算法的一般形式：
func( mode){
if(endCondition){ //遞歸出口
end;
}else{
func(mode_small) //調用本身，遞歸
}
}
求一個數的階乘是練習簡單而典型的例子，階乘的遞推公式為：factorial(n)=n*factorial(n-1)，其中n為非負整數,且0!=1,1!=1
我們根據遞推公式可以輕松的寫出其遞歸函數：
public static long factorial(int n) throws Exception {
if (n < 0)
throw new Exception("參數不能為負！");
else if (n == 1 || n == 0)
return 1;
else
return n * factorial(n - 1);
}
遞歸的過程
在求解6的階乘時，遞歸過程如下所示。
我們會驚奇的發現這個過程和棧的工作原理一緻對，遞歸調用就是通過棧這種資料結構完成的。整個過程實際上就是一個棧的入棧和出棧問題。然而我們并不需要關心這個棧的實作，這個過程是由系統來完成的。
那麼遞歸中的“遞”就是入棧，遞進；“歸”就是出棧，回歸。
我們可以通過一個更簡單的程式來模拟遞進和回歸的過程：
/**
* 關于 遞歸中 遞進和回歸的了解
* @param n
*/
public static void recursion_display(int n) {
int temp=n;//保證前後列印的值一樣
System.out.println("遞進:" + temp);
if (n > 0) {
recursion_display(--n);
}
System.out.println("回歸:" + temp);
}
遞歸的例子
斐波那契數列
斐波那契數列的遞推公式:Fib(n)=Fib(n-1)+Fib(n-2)，指的是如下所示的數列：
1、1、2、3、5、8、13、21.....
按照其遞推公式寫出的遞歸函數如下：
public static int fib(int n) throws Exception {
if (n < 0)
throw new Exception("參數不能為負！");
else if (n == 0 || n == 1)
return n;
else
return fib(n - 1) + fib(n - 2);
}
遞歸調用的過程像樹一樣，通過觀察會發現有很多重複的調用。
歸并排序
歸并排序也是遞歸的典型應用，其思想：将序列分為若幹有序序列（開始為單個記錄），兩個相鄰有序的序列合并成一個有序的序列，以此類推，直到整個序列有序。
//遞歸過程是：在遞進的過程中拆分數組，在回歸的過程合并數組
public static void mergeSort(int[] source, int[] temp, int first, int last) {
if (first < last) {
int mid = (first + last) / 2;
mergeSort(source, temp, first, mid); //歸并排序前半個子序列
mergeSort(source, temp, mid + 1, last); //歸并排序後半個子序列
merge(source, temp, first, mid, last); //在回歸過程中合并
} else if (first == last) { //待排序列隻有一個，遞歸結束
temp[first] = source[first];
}
}
同樣調用過程向樹一樣，但是它并沒有重複調用的問題。在遞進的過程中拆分數組，在回歸的過程合并數組 。通過遞歸來實作歸并排序，程式結構和條理非常清晰。