遞回是一種非常重要的演算法思想，無論你是前端開發，還是后端開發，都需要掌握它，在日常作業中，統計檔案夾大小，決議xml檔案等等，都需要用到遞回演算法，它太基礎太重要了，這也是為什么面試的時候，面試官經常讓我們手寫遞回演算法，本文呢，將跟大家一起深入挖掘一下遞回演算法~
什么是遞回？
遞回，在計算機科學中是指一種通過重復將問題分解為同類的子問題而解決問題的方法，簡單來說，遞回表現為函式呼叫函式本身，在知乎看到一個比喻遞回的例子，個人覺得非常形象，大家看一下：
?
遞回最恰當的比喻，就是查詞典，我們使用的詞典，本身就是遞回，為了解釋一個詞，需要使用更多的詞，當你查一個詞，發現這個詞的解釋中某個詞仍然不懂，于是你開始查這第二個詞，可惜，第二個詞里仍然有不懂的詞，于是查第三個詞，這樣查下去，直到有一個詞的解釋是你完全能看懂的，那么遞回走到了盡頭，然后你開始后退，逐個明白之前查過的每一個詞，最終，你明白了最開始那個詞的意思，
?
來試試水，看一個遞回的代碼例子吧，如下：
遞回的特點
實際上，遞回有兩個顯著的特征,終止條件和自身呼叫:
? 自身呼叫：原問題可以分解為子問題，子問題和原問題的求解方法是一致的，即都是呼叫自身的同一個函式，
? 終止條件：遞回必須有一個終止的條件，即不能無限回圈地呼叫本身，
結合以上demo代碼例子，看下遞回的特點：
遞回與堆疊的關系
其實，遞回的程序，可以理解為出入堆疊的程序的，這個比喻呢，只是為了方便讀者朋友更好理解遞回哈，以上代碼例子計算sum（n=3）的出入堆疊圖如下：
為了更容易理解一些，我們來看一下 函式sum（n=5）的遞回執行程序，如下：
? 計算sum（5）時，先sum（5）入堆疊，然后原問題sum（5）拆分為子問題sum（4），再入堆疊，直到終止條件sum（n=1）=1，就開始出堆疊，
? sum（1）出堆疊后，sum（2）開始出堆疊，接著sum（3），
? 最后呢，sum（1）就是后進先出，sum（5）是先進后出，因此遞回程序可以理解為堆疊出入程序啦~
遞回的經典應用場景
哪些問題我們可以考慮使用遞回來解決呢？即遞回的應用場景一般有哪些呢？
? 階乘問題
? 二叉樹深度
? 漢諾塔問題
? 斐波那契數列
? 快速排序、歸并排序（分治演算法體現遞回）
? 遍歷檔案，決議xml檔案
遞回解題思路
解決遞回問題一般就三步曲，分別是：
? 第一步，定義函式功能
? 第二步，尋找遞回終止條件
? 第二步，遞推函式的等價關系式
這個遞回解題三板斧理解起來有點抽象，我們拿階乘遞回例子來喵喵吧~
1、定義函式功能
定義函式功能，就是說，你這個函式是干嘛的，做什么事情，換句話說，你要知道遞回原問題是什么呀？比如你需要解決階乘問題，定義的函式功能就是n的階乘，如下：
2、尋找遞回終止條件
遞回的一個典型特征就是必須有一個終止的條件，即不能無限回圈地呼叫本身，所以，用遞回思路去解決問題的時候，就需要尋找遞回終止條件是什么，比如階乘問題，當n=1的時候，不用再往下遞回了，可以跳出回圈啦，n=1就可以作為遞回的終止條件，如下：
3、遞推函式的等價關系式
遞回的「本義」，就是原問題可以拆為同類且更容易解決的子問題，即「原問題和子問題都可以用同一個函式關系表示，遞推函式的等價關系式，這個步驟就等價于尋找原問題與子問題的關系，如何用一個公式把這個函式表達清楚」，
階乘的公式就可以表示為 f(n) = n * f(n-1), 因此，階乘的遞回程式代碼就可以寫成這樣，如下：
「注意啦」，不是所有遞推函式的等價關系都像階乘這么簡單，一下子就能推匯出來，需要我們多接觸，多積累，多思考，多練習遞回題目滴~
如果你想成為學習更多的高級編程知識——編程學習交流俱樂部【點擊進入】！
涉及到：C語言、C++、windows編程、網路編程、QT界面開發、Linux編程、游戲編程、黑客等等......
程式員編程入門資料：
程式員?推薦學習書籍：
一個活躍、高逼格、高層次的程式員編程學習殿堂；編程入門只是順帶，思維的提高才有價值！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/196897.html
標籤：其他
下一篇：前端面試題