遞歸是一種非常重要的算法思想，無論你是前端開發，還是後端開發，都需要掌握它。在日常工作中，統計文件夾大小，解析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編程、遊戲編程、黑客等等......
