遞歸：一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解。本案例很清楚的說明了遞歸是如何將一個復雜的問題轉化為規模較小的問題來解決的。下面通過一個小例子來說明遞歸的原理。
代碼如下：
/**
* @fileName Test.java
* @description 遞歸學習比較，求階乘
* @date 2012-11-25
* @time 17:30
* @author wst
*/
public class Test {
static int multiply(int n) {
int factorial;// 階乘
if (n == 1 || n == 0) {
factorial = n;
} else {
factorial = n * multiply(n - 1);
}
return factorial;
}
public static void main(String[] args) {
System.out.println(multiply(5));
}
}
當函數被調用時，它的變量的空間是創建於運行時堆棧上的。以前調用的函數的變量扔保留在堆棧上，但他們被新函數的變量所掩蓋，因此 是不能被訪問的。
程序中的函數有兩個變量：參數n和局部變量factorial。下面的一些圖顯示了堆棧的狀態，當前可以訪問的變量位於棧頂。所有其他調用的變量飾以灰色的陰影，表示他們不能被當前正在執行的函數訪問。
假定我們以5這個值調用遞歸函數。堆棧的內容如下，棧頂位於最下方：
代碼如下：
n multiply(n) factorial
5 multiply(5) 5*multiply(4) //第一次調用
4 multiply(4) 4*multiply(3) //第二次調用
3 multiply(3) 3*multiply(2) //第三次調用
2 multiply(2) 2*multiply(1) //第四次調用
1 multiply(1) 1 //第五次調用
從上面的信息可以很容易的看出，遞歸是如何將一個問題逐漸最小化來解決的，從方法調用開始，factorial結果都會被壓入棧，直到方法調用結束，最後從棧頂逐個返回得到結果。經過逐個代入，結果如下:
n=1 1 向上返回 1
n=2 2*multiply(1) 向上返回 2*1=2
n=3 3*multiply(2) 向上返回 3*(2*1)=6
n=4 4*multiply(3) 向上返回 4*(3*(2*1))=24
n=5 5*multiply(4) 向上返回 5*(4*(3*(2*1)))=120
注意：因為multiply(1)或multiply(0)返回的值為1
所以就有 2*multiply(1)=2*1=2
又因為multiply(2)符合遞歸條件，遞歸後可化為2*multiply(1)
所以就有3*multiply(2)=3*(2*multiply(1))=3*(2*1)=6
因為multiply(3)遞歸後可化為3*multiply(2)
所以multiply(4)=4*multiply(3)=4*(3*multiply(2))=4*(3*(2*1))=24
以此類推，multiply(5)=5*multiply(4)
可化為5*(4*multiply(3))=5*(4*3*(multiply(2)))=5*(4*(3*(2*1)))=120
再來看看字節碼信息:
代碼如下：
public class Test extends java.lang.Object{
public Test();
Code:
0: aload_0
1: invokespecial #1; //Method java/lang/Object."<init>":()V
4: return
static int multiply(int);
Code:
0: iload_0
1: iconst_1 //將int類型常量1壓入棧
2: if_icmpeq 9 //將兩個int類型值進行比較，相等，則跳轉到位置9，這就是||的短路功能
5: iload_0 //此處是在第一個條件不成立的情況下執行，從局部變量0中裝載int類型值（將n的值壓入棧）
6: ifne 14 //比較，如果不等於0則跳轉到位置14，注意：由於此處默認和0比較，所以沒有必要再將常量0壓入棧
9: iload_0 //如果在ifne處沒有跳轉，則從局部變量0中裝載int類型值（將n的值壓入棧）
10: istore_1 //將int類型值存入局部變量1中（彈出棧頂的值即局部變量0壓入棧的值，再存入局部變量1中）
11: goto 23 //無條件跳轉至位置23
14: iload_0 //位置6處的比較，如果不等於0執行此指令，從局部變量0中裝載int類型值（將n的值壓入棧）
15: iload_0 //從局部變量0中裝載int類型值（將n的值壓入棧）
16: iconst_1 //將int類型常量1壓入棧，常量1是代碼中n-1的1
17: isub //執行減法操作，n-1
18: invokestatic #2; //Method multiply:(I)I，調用方法multiply
21: imul //執行乘法操作，n * multiply(n - 1)
22: istore_1 //將int類型值存入局部變量1中，factorial=...
23: iload_1 //從局部變量1中裝載int類型值（將factorial的結果壓入棧）
24: ireturn //方法返回
public static void main(java.lang.String[]);
Code:
0: getstatic #3; //Field java/lang/System.out:Ljava/io/PrintStream;
3: iconst_5
4: invokestatic #2; //Method multiply:(I)I
7: invokevirtual #4; //Method java/io/PrintStream.println:(I)V
10: return
}
