概述程序調(diào)用自身的編程技巧稱為遞歸（ recursion）。遞歸做為一種算法在程序設計語言中廣泛應用。遞歸有直接遞歸和間接遞歸 ·直接遞歸：函數(shù)在執(zhí)行過程中調(diào)用本身。 ·間接遞歸：函數(shù)在執(zhí)行過程中調(diào)用其它函數(shù)再經(jīng)過這些函數(shù)調(diào)用本身。 ·表達方式： ·遞歸算法有四個特性： （1）必須有可最終達到的終止條件，否則程序將陷入無窮循環(huán)； （2）子問題在規(guī)模上比原問題小，或更接近終止條件； （3）子問題可通過再次遞歸調(diào)用求解或因滿足終止條件而直接求解； （4）子問題的解應能組合為整個問題的解。
下面將從以下幾個典型的例子來講解遞歸算法： 漢諾塔問題如圖，漢諾塔問題是指有三根桿子A,B,C。C桿上有若干碟子，把所有碟子從C桿上移到B桿上，每次只能移動一個碟子，大的碟子不能疊在小的碟子上面。求最少要移動多少次？
當n=1時： Move 1 from A to C
當n=2時：
Move 1 from A to B
Move 2 from A to C
Move 1 from B to C
當n=3時：
Move 1 from A to C
Move 2 from A to B
Move 1 from C to B
Move 3 from A to C
Move 1 from B to A
Move 2 from B to C
Move 1 from A to C
源代碼- static StringBuffer str = new StringBuffer();
- /**
- * //漢諾塔問題
- * @param n 盤子的個數(shù)
- * @param x 將要移動盤子柱子
- * @param y 要借用的柱子
- * @param z 要移動到的柱子
- * @return
- */
- public static String hanio(int n, Object x, Object y, Object z) {
- //String str ="";
- if(1 == n)
- str.append(move(x, n, z) + "\n");
- else {
- hanio(n-1, x, z, y);
- str.append(move(x, n, z) + "\n") ;
- hanio(n-1, y, x, z);
- }
- return str.toString();
- }
- private static String move(Object x, int n, Object y) {
- //System.out.println("Move " + n + " from " + x + " to " + y);
- return "Move " + n + " from " + x + " to " + y;
- }
fibonacci數(shù)列斐波納契數(shù)列，又稱黃金分割數(shù)列，指的是這樣一個數(shù)列：1、1、2、3、5、8、13、21、……在數(shù)學上，斐波納契數(shù)列以如下被以遞歸的方法定義：F0=0，F(xiàn)1=1，F(xiàn)n=F(n-1)+F(n-2)（n>=2，n∈N*）
源代碼- /**
- * fibonacci數(shù)列
- * @param n
- * @return
- */
- public static long fibonacci(int n) {
- if((0 == n) || (1 == n)) {
- return n;
- }else {
- return fibonacci(n-1) + fibonacci(n-2);
- }
- }
1加到n累加用遞歸實現(xiàn)從1加到n，即1+2+3+4+...+n。
源代碼- /**
- * 累加,從1加到n，即1+2+3+4+...+n
- * @param n 要累加到的數(shù)值
- * @return 累加的結果
- */
- public static long total(int n) {
- if(1 == n) {
- return n;
- }else {
- return total(n-1) + n;
- }
- }
從1到n累積用遞歸實現(xiàn)，從1到n累積，即1*2*3*...*n
源代碼- /**
- * 從1到n的累積，即1*2*3*...*n
- * @param n 要累乖到的數(shù)值
- * @return
- */
- public static long accumulate(int n) {
- if(1 == n) {
- return n;
- }else {
- return accumulate(n-1) * n;
- }
- }
求數(shù)組中的最大值用遞歸算法求數(shù)組中的最大值。
源代碼- /**
- * 用遞歸算法求數(shù)組中的最大值
- * @param a 數(shù)組
- * @param low 數(shù)組下標
- * @param heigh 數(shù)組上標
- * @return
- */
- public static int Max(int[] a, int low, int heigh) {
- int max;
- if(low > heigh-2) {
- if(a[low] > a[heigh]) max = a[low];
- else max = a[heigh];
- }else {
- int mid = (low + heigh)/2;
- int max1 = Max(a, low, mid);
- int max2 = Max(a, mid+1, heigh);
- max = max1>max2 ? max1 : max2;
- }
- return max;
- }
數(shù)字塔問題用遞歸算法求解數(shù)字塔問題。
n=1時 1 n=2時
1
2 2
n=3時
1
2 2
3 3 3
n=4時
1
2 2
3 3 3
4 4 4 4 源代碼- /**
- * 用遞歸算法求解數(shù)字塔問題
- * @param n 數(shù)字塔的行數(shù)
- * @return 數(shù)字塔的字符串
- */
- public static String tourData(int n) {
- String str = new String();
- if(1 == n) {
- str = rowData(n) + "\n";
- return str;
- }
- else {
- str = tourData(n-1) + rowData(n) + "\n";
- }
- return str;
- }
- private static String rowData(int n) {
- String str = new String();
- for(int i=0; i<n; i++) {
- str = str+ n + " ";
- }
- return str;
- }
|
