作者：劉半仙 來源：http://1t.click/eWx
# 遞歸是什麼?定義：程序調用自身的編程技巧稱為遞歸。
它分為調用階段和回退階段，遞歸的回退順序是它調用順序的逆序。
遞歸使用的是選擇結構：if/switch。而for，while，do while使用的是循環結構。
定義不明白不要緊，先思考以下表達式，要怎麼寫程序來計算呢？
1+2+3....+100=?
很多人第一反應使用for循環來解決：
int sum =0;for (int i = 1; i <= 100; i++) { sum+=i;}System.out.println(sum);或者二逼青年使用最簡潔而且高效的公式(推薦使用,開銷最小,且一步到位):
int start =1; int end = 100; int sum =(start+end)*end/2;//首項加末項乘以項數除以二 System.out.println(sum);//5050而遞歸代碼如下:
static int recursion(int n){ if(n==1){ return 1; }else{ return n+recursion(n-1); }}通過初體驗對比,不難發現以下遞歸有以下幾個要點。
優點：使程序結構更清晰,更簡潔,更容易讓人理解。
缺點：使用遞歸調用時，如果過多的調用容易造成java.lang.StackOverflowError即棧溢。
出和程序執行過慢。這是一個潛在Bug和影響程序執行效率問題，需要謹慎使用。對於網際網路這種以速度和效率來維護用戶量，不得以用遞歸時，可以把處理的數據放入緩存，或者直接使用迭代等方式來解決。
規律：遞歸要有出口，不然成了死循環。解出遞歸的要點在於求出n-1，求出了n-1才能求解出n,這是為什麼呢?
# 遞歸的執行過程前文對於遞歸的定義中說，遞歸分為調用階段和回退階段，遞歸的回退順序是它調用順序的逆序。為了理解執行過程，這裡配合實例講解。請思考如何寫出它的遞歸代碼：
n!=n*(n-1)*(n-2)...*3*2*1
這裡給出數學表達式：
從表達式中可以明顯的可以看出：
遞歸有出口；
遞歸是選擇結構。
遞歸代碼也不難。
它的調用順序是怎麼樣的呢？
當你傳入5時，方法內會去調用方法factorial（4），然後又調用方法factorial（3）直到factorial（0）=1時開始返回，下面為更詳細的圖解。
1、調用階段
2、回退階段
圖中紅色箭頭為調用階段，綠色箭頭為回退階段。這就是遞歸的要點在於求出n-1，求出了n-1才能求解出n，它思想其實和數學中的歸納本質上是相同的。
# 漢諾塔遊戲講解遊戲規則：有三根柱子，最左邊的一根柱子從下往上按照大小順序摞著64片圓盤。需要你藉助中間的柱子把左邊的所有圓盤移動到最右邊的柱子上。並且規定，下面圓盤始終要比上面的大，在三根柱子之間一次只能移動一個圓盤。求出最少移動的次數。
如果要把X柱上得3個圓盤移動到Z柱，步驟如下：
①把X柱最上面的小圓盤移動到Z柱。②再把X柱中間大的圓盤移動到Y柱。③把Z柱上最小的圓盤移動到Y柱上。
這三次操作如圖所示：
再加上步驟④⑤⑥⑦，所以3個圓盤至少需要移動7次。如果移動6個圓盤時：
所以，可以推出,當n個從x柱，經由y柱中轉，移動到z柱(解出n層漢諾塔時)，有:
當n=0時，不用做任何操作；
當n>0時，
首先,將n-1個盤子從x藉助z移動到y
然後,將1個盤子從x移動到z
最後,將在中間y上的n-1個盤子藉助x移動到z
為了解出n層漢諾塔，需要先使用n-1層漢諾塔的解法。
從推到過程中我們可以發現：解出遞歸的要點在於求出n-1，求出了n-1才能求解出n。此外，從數學角度也可以歸納出 0,1,3,7,15,63...表達式為:f(n)=2^n - 1。
現在，我們可以給出代碼：
static int t=0;public static void main(String[] args) { hanio(3,"x","y","z"); System.out.println(t);} static void hanio(int n ,String src,String mid,String dest){ if(n==1){ System.out.println(src+"-->"+dest); t++; }else{ hanio(n-1,src,dest,mid); hanio(1,src,"",dest); hanio(n-1,mid,src,dest); }}# 總結和展望
遞歸對於解決某些問題非常方便（比如遞歸讀取文件路徑），也易於理解。雖然用迭代不是不可以實現，只是同樣為了解決某些特性問題，寫出迭代的代碼花費的時間和難度卻比遞歸高。
前文提到，遞歸和數學中的歸納思想本質上是相同的，都是"將複雜的問題簡化"。掌握遞歸思想的核心就在於"把握結構",因為把握結構是分解整個問題的突破口。
熱文推薦
MyBatis憑神馬能獲取到接口參數名？
原創：如何來判斷一個List是否有序？