解釋：程序調用自身的編程技巧叫做遞歸。
程序調用自身的編程技巧稱為遞歸（ recursion）。遞歸做為一種算法在程序設計語言中廣泛應用。 一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量。遞歸的能力在于用有限的語句來定義對象的無限集合。
遞歸的三個條件：
1.邊界條件
2.遞歸前進段
3.遞歸返回段
當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回。
下面通過兩個示例程序來說明：
1.使用Java代碼求5的階乘。（5的階乘=5*4*3*2*1）
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
package org.wxp.recursion; /** * 計算5的階乘(result = 5*4*3*2*1) * @author Champion.Wong */public class Test01 { public static void main(String[] args) { System.out.println(f(5)); } public static int f(int n) { if (1 == n) return 1; else return n*(n-1); } } |
此題中，按照遞歸的三個條件來分析：
(1)邊界條件：階乘，乘到最后一個數，即1的時候，返回1，程序執行到底；
(2)遞歸前進段：當前的參數不等于1的時候，繼續調用自身；
(3)遞歸返回段：從最大的數開始乘，如果當前參數是5，那么就是5*4，即5*(5-1)，即n*(n-1)
2.使用Java代碼求數列：1，1，2，3，5，8......第40位的數
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
package org.wxp.recursion; /** * 求數列：1，1，2，3，5，8......第40位的數 */public class Test_02_Fibonacci { public static void main(String[] args) { System.out.println(f(6)); } public static int f(int n ) { if (1== n || 2 == n) return 1; else return f(n-1) + f(n-2); } } |
3.問題描述：求解Fibonacci數列的第10個位置的值？ （斐波納契數列（Fibonacci Sequence），又稱黃金分割數列，指的是這樣一個數列：1、1、2、3、5、8、13、21、……在數學上，斐波納契數列以如下被以遞歸的方法定義：F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N*））
程序清單：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
/** *<p>Title:Java遞歸算法實例</p> *<p>Description:利用遞歸算法求解Fibonacci數列第5個數的值</p> *<p>Filename:Fibonacci.java</p> */public class Fibonacci { /** *方法描述：求解Fibonacci數列的遞歸算法 *輸入參數：int n *返回類型：int */ public static int fun(int n) { if(1==n || 2==n) { return 1; } else { return (fun(n-1) + fun(n-2)); } } /** *方法描述：主方法 *輸入參數：String[] args *返回類型：void */ public static void main(String[] args) { System.out.println(fun(10)); } } |
運行結果如下所示：
復制代碼 代碼如下:
55
