1.遞歸是什麼?
定義:程序調用自身的編程技巧稱為遞歸。它分為調用階段和回退階段，遞歸的回退順序是它調用順序的逆序。
遞歸使用的是選擇結構：if/switch。而for，while，do while使用的是循環結構。
定義不明白不要緊，先思考以下表達式，要怎麼寫程序來計算呢？
1+2+3....+100=?
很多人第一反應使用for循環來解決：
或者神級程序猿使用最簡潔而且高效的公式(推薦使用，開銷最小，且一步到位)：
遞歸代碼如下：
通過初體驗對比，不難發現以下遞歸有以下幾個要點：
1.優點：使程序結構更清晰，更簡潔，更容易讓人理解。
2.缺點：使用遞歸調用時，是方法調用方法，如果過多的調用容易造成棧溢出和程序執行過慢。這是一個潛在Bug和影響程序執行效率問題，需要謹慎使用。對於互聯網這種以速度和效率來維護用戶量，不得以用遞歸時，可以把處理的數據放入緩存，或者直接使用迭代等方式來解決。
3.規律：遞歸要有出口，不然成了死循環。解出遞歸的要點在於求出n-1，求出了n-1才能求解出n，這點後文有講解。
2.遞歸的執行過程:
前文對於遞歸的定義中說，遞歸分為調用階段和回退階段，遞歸的回退順序是它調用順序的逆序。為了理解執行過程，這裡配合實例講解。請思考如何寫出它的遞歸代碼：
n!=n*(n-1)*(n-2)...*3*2*1
這裡給出數學表達式：
從表達式中可以明顯的可以看出：1.遞歸有出口。2.遞歸是選擇結構。遞歸代碼也不難：
它的調用順序是怎麼樣的呢？
當你傳入5時，方法內會去調用方法factorial（4），然後又調用方法factorial（3）直到factorial（0）=1時開始返回，下面為更詳細的圖解:
調用階段
回退階段
圖中紅色箭頭為調用階段，綠色箭頭為回退階段。這就是遞歸的要點在於求出n-1，求出了n-1才能求解出n，它思想其實和數學中的歸納本質上是相同的。
3.漢諾塔遊戲講解
遊戲規則：有三根柱子，最左邊的一根柱子從下往上按照大小順序摞著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。
現在，我們可以給出代碼：
4.總結和展望
遞歸對於解決某些問題非常方便（比如遞歸讀取文件路徑），也易於理解。雖然用迭代不是不可以實現，只是同樣為了解決某些特性問題，寫出迭代的代碼花費的時間和難度卻比遞歸高。
前文提到，遞歸和數學中的歸納思想本質上是相同的，都是"將複雜的問題簡化"。掌握遞歸思想的核心就在於"把握結構",因為把握結構是分解整個問題的突破口。
閱讀更多 Java是最好的語言NO1 的文章
