遞迴是一種非常重要的演算法思想，無論你是前端開發，還是後端開發，都需要掌握它。在日常工作中，統計資料夾大小，解析xml檔案等等，都需要用到遞迴演算法。它太基礎太重要了，這也是為什麼面試的時候，面試官經常讓我們手寫遞迴演算法。本文呢，將跟大家一起深入挖掘一下遞迴演算法~
什麼是遞迴？
遞迴，在計算機科學中是指一種透過重複將問題分解為同類的子問題而解決問題的方法。簡單來說，遞迴表現為函式呼叫函式本身。在知乎看到一個比喻遞迴的例子，個人覺得非常形象，大家看一下：
遞迴最恰當的比喻，就是查詞典。我們使用的詞典，本身就是遞迴，為了解釋一個詞，需要使用更多的詞。當你查一個詞，發現這個詞的解釋中某個詞仍然不懂，於是你開始查這第二個詞，可惜，第二個詞裡仍然有不懂的詞，於是查第三個詞，這樣查下去，直到有一個詞的解釋是你完全能看懂的，那麼遞迴走到了盡頭，然後你開始後退，逐個明白之前查過的每一個詞，最終，你明白了最開始那個詞的意思。
來試試水，看一個遞迴的程式碼例子吧，如下：
實際上，遞迴有兩個顯著的特徵,終止條件和自身呼叫:
自身呼叫：原問題可以分解為子問題，子問題和原問題的求解方法是一致的，即都是呼叫自身的同一個函式。
終止條件：遞迴必須有一個終止的條件，即不能無限迴圈地呼叫本身。
結合以上demo程式碼例子，看下遞迴的特點：
其實，遞迴的過程，可以理解為出入棧的過程的，這個比喻呢，只是為了方便讀者朋友更好理解遞迴哈。以上程式碼例子計算sum（n=3）的出入棧圖如下：
sum（1）出棧後，sum（2）開始出棧，接著sum（3）。
最後呢，sum（1）就是後進先出，sum（5）是先進後出，因此遞迴過程可以理解為棧出入過程啦~
遞迴的經典應用場景
哪些問題我們可以考慮使用遞迴來解決呢？即遞迴的應用場景一般有哪些呢？
階乘問題
二叉樹深度
漢諾塔問題
斐波那契數列
快速排序、歸併排序（分治演算法體現遞迴）
遍歷檔案，解析xml檔案
遞迴解題思路
解決遞迴問題一般就三步曲，分別是：
第一步，定義函式功能
第二步，尋找遞迴終止條件
第二步，遞推函式的等價關係式
這個遞迴解題三板斧理解起來有點抽象，我們拿階乘遞迴例子來喵喵吧~
1、定義函式功能
定義函式功能，就是說，你這個函式是幹嘛的，做什麼事情，換句話說，你要知道遞迴原問題是什麼呀？比如你需要解決階乘問題，定義的函式功能就是n的階乘，如下：
遞迴的一個典型特徵就是必須有一個終止的條件，即不能無限迴圈地呼叫本身。所以，用遞迴思路去解決問題的時候，就需要尋找遞迴終止條件是什麼。比如階乘問題，當n=1的時候，不用再往下遞迴了，可以跳出迴圈啦，n=1就可以作為遞迴的終止條件，如下：
遞迴的「本義」，就是原問題可以拆為同類且更容易解決的子問題，即「原問題和子問題都可以用同一個函式關係表示。遞推函式的等價關係式，這個步驟就等價於尋找原問題與子問題的關係，如何用一個公式把這個函式表達清楚」。
階乘的公式就可以表示為 f(n) = n * f(n-1), 因此，階乘的遞迴程式程式碼就可以寫成這樣，如下：
涉及到：C語言、C++、windows程式設計、網路程式設計、QT介面開發、Linux程式設計、遊戲程式設計、駭客等等......
