Recursion
遞迴 (Recursion)，通過調用自身函數，有時可以將某個複雜的問題，分解為規模較小的子問題。而 Recursion 也經常和以下演算法配合使用 :
- 分治法 divide and conquer
- 回溯法 backtrack
- 動態規劃 dynamic programming
在實際狀況中，遞迴函數的設計常常很難想像，因為遞迴設計屬於逆向思維，在設計遞迴函數的時候，非常容易被這種層層嵌套搞暈，在這裡簡單給個模板範例講解。
逆向思維是甚麼呢 ? 是一種從未知到已知的探索。例如我們想計算 100!，這時候假設已經計算好了 99! 的答案，那我們就可以使用 99! 乘 100 ，這樣就得到 100! ! 但是其實 99!真正的數值還不知道，因此又需要尋求 98! 的結果…，就這樣一直往前推導，便推到了 1!。
而1! = 1，這是最基本的 case，這樣 2! = 1!*2 = 2也就可以算出來，同理 3!、4!、…、10!、…、20!、…，30!、…後面的所有的階乘結果我們都可以依次返回並填上答案。這就是遞迴的逆向思維方式
從最終想要的答案出發，逐步回頭尋找答案，並且使用前次答案，構造出現在層的答案。
而逐步回頭尋找答案，最後一定需要找到最基本的簡單的 Case。而因為問題已經足夠簡單，故可以直接得知答案，之後遞迴執行便開始層層返回，並且在返回途上，每層的答案就可依次填上。
Recursion Template
我們常用來舉例遞迴的Fibonacci數列，其實用一般迭代方法感覺就可以了，可能看起來更直觀；但某些問題其實是很難用迭代的方式來實現的，反而遞迴卻可以非常簡潔，例如 Merge Sort，故還是蠻需要學習遞迴函數的寫法的。一般來說，Recursion Template可以分成 4 個步驟:
定義 Recursion 函數
要明確這個函數要做什麼事情，它的輸入參數是什麼，希望它要完成什麼樣的任務，並返回什麼值。且最重要的是，要設計成原問題和子問題都可以調用的形式。
Base case處理
考慮當規模足夠小的基礎情況，答案會顯而易見，這時直接將答案寫死並返回。基礎情況的處理，是為了避免遞迴無限下去無法停止。
遞迴調用
這個階段會縮小原始問題的規模，變成去解決子問題。因為解決子問題和解決大問題流程其實一樣，所以可調用原函數來解決問題，這就是遞迴。然後便可以就由這種分治的思想，獲取到較小規模的子問題答案。
雖然遞迴調用是為了解決子問題，但這並不是一蹴而就的事情，內部暗含了很多深層的操作，故我們在這邊可以先把遞迴調用，稱為一個超級操作。
構造當前層答案
再這裡，會通過將上一層的答案進行推導，並得到現在層的答案
構造當前層狀態答案時，並不涉及到復雜的深層遞迴操作，因此先稱它為一個微操作。
Recursion & Mathematical Induction
為什麼設計遞迴函數的時候，經常會覺得難以理解呢，它的原因就在於上說的超級操作 ! 由於超級操作裡面有很多深層的調用，所以我們可能會懷疑這個超級操作作能否正確完成，故抱著懷疑的態度，會想試圖深入探索一下超級操作的內部邏輯。也就是說，我們的思維也進入到下一層遞迴中，這樣便陷入到層層圈套中，便很容易搞暈…要怎麼避免被搞糊塗呢 ? 其實很簡單
那麼為什麼我們可以相信超級操作，一定能完成它的使命呢 ? 為了回答這個問題，來說一下了數學歸納法。
數學歸納法是一種證明命題對於所有正整數都成立的方法。包含了三個步驟:
- Base Step:
證明命題對於最小的整數是成立的，通常是
n=1時某個命題成立。 - Inductive Step:
假設命題對於某個整數
n是成立的，這就是所謂的歸納假設。 - 歸納遞推:
然後基於 Inductive Step 假設，再來證明命題對於整數
n+1也是成立的。
如果這以上步驟都成功完成，那麼我們就可以得出該命題對於所有相關的正整數都成立。了解數學歸納法，再回頭思考一下 Recursion ，曾有疑問過:
為什麼我們可以相信 Recursion 的超級操作，一定能完成它的使命呢?
其回答是:
所以在設計遞迴函數的時候，千萬不要陷入去思考超級操作內部邏輯，主要專注在歸納遞推，構造當前層答案就可以了。