點選上方"藍字"，關注了解更多
啥是遞歸算法呢？用比較哲學的話語來形容就是：從前有座山，山裡有個廟，廟裡有個老和尚，他對小和尚講故事，講的是：從前有座山，山裡有個廟。。。。。。。。。。。。。這樣子的故事，如果是放在高中作文中，可以寫上個幾萬字了。
剛學程式設計的時候，是比較難了解遞歸算法的。遞歸思想之是以困難，原因在于它非常像是一種循環推理，它也不是一個直覺的過程，稍微有點繞的感覺。
在日常開發中，我們使用循環語句遠遠大于遞歸，但這不能說明遞歸就沒有用武之地。
遞歸算法是比較好用，但是了解起來可能不太好了解，是以在遞歸算法和循環算法對比中，流行一句話：人了解循環，神了解遞歸。當然這隻是一個段子，不過也從側面反映出遞歸算法不容易了解的事實。
ps：本文為避免繁雜，沒有涉及到遞歸算法的時間/ 空間複雜度
什麼是遞歸
遞歸算法簡單來說就是：自己調用自身函數的算法。隻不過其中要涉及要遞歸出口和邏輯處理的過程，這就增加了設計遞歸算法的難度。
遞歸算法的實質是把問題分解成規模縮小的同類問題的子問題，然後遞歸調用方法來表示問題的解。遞歸算法對解決一大類問題很有效，它可以使算法簡潔和易于了解。
這樣我們就可以利用大道至簡的思想，把一個大的複雜的問題層層轉換為一個小的和原問題相似的問題來求解的這樣一種政策。
遞歸往往能給我們帶來非常簡潔非常直覺的代碼形勢，進而使我們的編碼大大簡化，然而遞歸的思維确實很我們的正常思維相逆的，我們通常都是從上而下的思維問題， 而遞歸趨勢從下往上的進行思維。
這樣我們就能看到我們會用很少的語句解決了非常大的問題，是以遞歸政策的最主要展現就是小的代碼量解決了非常複雜的問題。
遞歸算法解決問題的特點
1)遞歸就是方法裡調用自身。
2) 在使用遞歸政策時，必須有一個明确的遞歸結束條件，稱為遞歸出口。
3)遞歸算法解題通常顯得很簡潔，但遞歸算法解題的運作效率較低。是以一般不提倡用遞歸算法設計程式。
4)在遞歸調用的過程當中系統為每一層的傳回點、局部量等開辟了棧來存儲。遞歸次數過多容易造成棧溢出等，是以一般不提倡用遞歸算法設計程式。
public void recursiveTest(){ recursiveTest(); //自己調用自己的方法 ----> 就叫遞歸}
上面就是最簡單的遞歸算法，但不是正确的遞歸算法，一旦運作起來就會抛出棧記憶體溢出的異常，因為沒有退出條件，
是以就會進入死循環中，一直都在重複調用自己，遞歸調用在底層其實是對線程棧的壓棧和出棧操作，每調用一次都會壓棧一次，并記錄相關的局部變量資訊，線程棧的記憶體是非常有限的，而遞歸調用如果是無限的，那麼很快就會消耗完所有的記憶體資源，最終導緻記憶體溢出。
這一點與空的while死循環是不一樣的，單純的死循環會大量的消耗cpu資源，但不會占用記憶體資源，是以不會導緻程式異常。從這一點能看到遞歸算法其實是更加消耗系統的性能和資源的。
是以：
使用遞歸算法必須滿足2個條件：
1)有反複執行的過程(調用自身)
2)有跳出反複執行過程的條件(遞歸出口)
遞歸算法簡單例子
說了那麼多，看個例子更加直覺：求階乘。顯然，階乘是可以用循環結構來實作的，是以遞歸與循環是可以互相轉換的。
直接出代碼：
public static int factrial(int n){ if(n<1){ return 1; } return n * factrial(n-1); }
以階層 f(6) 為例來看下它的「遞」和「歸」。
求解問題 f(6), 由于 f(6) = n * f(5), 是以 f(6) 需要拆解成 f(5) 子問題進行求解，同理 f(5) = n * f(4) ,也需要進一步拆分,... ,直到 f(1), 這是「遞」，f(1) = 1解決了，由于 f(2) = 2 f(1) = 2 也解決了,.... f(n)到最後也解決了，這是「歸」，是以遞歸的本質是能把問題拆分成具有相同解決思路的子問題，。。。直到最後被拆解的子問題再也不能拆分，解決了最小粒度可求解的子問題後，在「歸」的過程中自然順其自然地解決了最開始的問題。
另外一種形式：
對應進棧出棧：
遞歸算法基本架構
java實作遞歸的基本架構
public void recur(int level, int param) { // level:遞歸層數；param參數 // 遞歸終止條件 if (level > MAX_LEVEL) { // 對結果處理 return; } // 處理目前層的邏輯關系 process(level, param); // 遞歸下去一層 recur( level: level + 1, newParam); // 儲存目前狀态 }
遞歸必須要有三個要素：
①、邊界條件
②、遞歸前進段
③、遞歸傳回段
當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸傳回。
其他遞歸算法例子
一、漢諾塔問題：
所有盤子的直徑是不同的，并且盤子中央都有一個洞使得它們剛好可以放在塔座上。所有的盤子剛開始都放置在A 塔座上。這個難題的目标是将所有的盤子都從塔座A移動到塔座C上，每次隻可以移動一個盤子，并且任何一個盤子都不可以放置在比自己小的盤子之上。
無論有多少個盤子，我們都将其看做隻有兩個盤子。假設有 N 個盤子在塔座A上，我們将其看為兩個盤子，其中(N-1)~1個盤子看成是一個盤子，最下面第N個盤子看成是一個盤子，那麼解決辦法為：
①、先将A塔座的第(N-1)~1個盤子看成是一個盤子，放到中介塔座B上，然後将第N個盤子放到目标塔座C上。
②、然後A塔座為空，看成是中介塔座，B塔座這時候有N-1個盤子，将第(N-2)~1個盤子看成是一個盤子，放到中介塔座A上，然後将B塔座的
第(N-1)号盤子放到目标塔座C上。
③、這時候A塔座上有(N-2)個盤子，B塔座為空，又将B塔座視為中介塔座，重複①，②步驟，直到所有盤子都放到目标塔座C上結束。
public static void move(int dish,String from,String temp,String to){ if(dish == 1){ System.out.println("将盤子"+dish+"從塔座"+from+"移動到目标塔座"+to); }else{ move(dish-1,from,to,temp);//A為初始塔座，B為目标塔座，C為中介塔座 System.out.println("将盤子"+dish+"從塔座"+from+"移動到目标塔座"+to); move(dish-1,temp,from,to);//B為初始塔座，C為目标塔座，A為中介塔座 }}
二、斐波那契數組：
public static int fab(int index) { if (index == 1 || index == 2) { return 1; } else { return fab(index - 1) + fab(index - 2); }
三、排列組合：
要求：将輸入的一個字元串中的所有元素進行排序并輸出，例如：你給出的參數是"abc"，
則程式會輸出
abc
acb
bac
bca
cab
cba
public static void permute(char[] list, int low, int high) { int i; if (low == high) { String cout = ""; for (i = 0; i <= high; i++) { cout += list[i]; } System.out.println(cout); } else { for (i = low; i <= high; i++) { char temp = list[low]; list[low] = list[i]; list[i] = temp; permute(list, low + 1, high); temp = list[low]; list[low] = list[i]; list[i] = temp; } }
輸出：
public static void permute(String str) { char[] strArray = str.toCharArray(); permute(strArray, 0, strArray.length - 1); }
當然，還有經典的遞歸周遊算法：二叉樹的前序、中序、後序周遊
如果你覺得文章不錯的話，就請去點個“再看”吧！！！！！！
END
掃碼關注
微信号 : LifeAndCoding
資料結構 | 算法
程式設計語言 | 面經
電子資源 | 資訊
我就知道你“在看”