概述
程序調用自身的編程技巧稱為遞歸（ recursion）。遞歸做為一種算法在程序設計語言中廣泛應用。遞歸有直接遞歸和間接遞歸
?直接遞歸：函數在執行過程中調用本身。
?間接遞歸：函數在執行過程中調用其它函數再經過這些函數調用本身。
?表達方式：

?遞歸算法有四個特性：
（1）必須有可最終達到的終止條件，否則程序將陷入無窮循環；
（2）子問題在規模上比原問題小，或更接近終止條件；
（3）子問題可通過再次遞歸調用求解或因滿足終止條件而直接求解；
（4）子問題的解應能組合為整個問題的解。

下面將從以下幾個典型的例子來講解遞歸算法：
漢諾塔問題
如圖，漢諾塔問題是指有三根桿子A,B,C。C桿上有若干碟子，把所有碟子從A桿上移到C桿上，每次只能移動一個碟子，大的碟子不能疊在小的碟子上面。求最少要移動多少次？

?

當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 盤子的個數
???????? * @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數列
斐波納契數列，又稱黃金分割數列，指的是這樣一個數列：1、1、2、3、5、8、13、21、……在數學上，斐波納契數列以如下被以遞歸的方法定義：F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N*）
源代碼
??? /**
???????? * fibonacci數列
???????? * @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累加
用遞歸實現從1加到n，即1+2+3+4+...+n。
源代碼
??? /**
???????? * 累加,從1加到n，即1+2+3+4+...+n
???????? * @param n 要累加到的數值
???????? * @return 累加的結果
???????? */ ?
??????? public static long total(int n) { ?
??????????? if(1 == n) { ?
??????????????? return n; ?
??????????? }else { ?
??????????????? return total(n-1) + n; ?
??????????? } ?
??????? } ?



從1到n累積
用遞歸實現，從1到n累積，即1*2*3*...*n
源代碼

?? ??? ?/**
???????? * 從1到n的累積，即1*2*3*...*n
???????? * @param n 要累乖到的數值
???????? * @return
???????? */ ?
??????? public static long accumulate(int n) {? ?
??????????? if(1 == n) { ?
??????????????? return n; ?
??????????? }else { ?
??????????????? return accumulate(n-1) * n; ?
??????????? } ?
??????? } ?



求數組中的最大值
用遞歸算法求數組中的最大值。
源代碼
?? ??? ?/**
???????? * 用遞歸算法求數組中的最大值
???????? * @param a 數組
???????? * @param low 數組下標
???????? * @param heigh 數組上標
???????? * @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; ?
??????? } ?

數字塔問題
用遞歸算法求解數字塔問題。
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?? ?
源代碼
?? ??? ?/**
???????? * 用遞歸算法求解數字塔問題
???????? * @param n 數字塔的行數
???????? * @return 數字塔的字符串
???????? */ ?
??????? 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; ?
??????? }?

?

轉載至：http://blog.csdn.net/luoweifu/article/details/8509688

轉載于:https://www.cnblogs.com/web424/p/6911782.html

總結

以上是生活随笔為你收集整理的java数据结构之递归算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。