數據結構與演算法系列八（遞歸見面禮）
- 2020 年 3 月 4 日
- 筆記
有人說，數據結構與演算法，電腦網路，與作業系統都一樣，脫離日常開發，除了面試這輩子可能都用不到呀！
有人說，我是做業務開發的，只要熟練API，熟練框架，熟練各種中間件，寫的程式碼不也能“飛”起來嗎？
於是問題來了：為什麼還要學習數據結構與演算法呢？
#理由一： 面試的時候，千萬不要被數據結構與演算法拖了後腿 #理由二： 你真的願意做一輩子CRUD Boy嗎 #理由三： 不想寫出開源框架，中間件的工程師，不是好廚子
我想好了，還是需要學習數據結構與演算法。但是我有兩個困惑：
1.如何著手學習呢？
2.有哪些內容要學習呢？
學習方法推薦：
#學習方法 1.從基礎開始，系統化學習 2.多動手，每一種數據結構與演算法，都自己用程式碼實現出來 3.思路更重要：理解實現思想，不要背程式碼 4.與日常開發結合，對應應用場景
學習內容推薦：
數據結構與演算法內容比較多，我們本著實用原則，學習經典的、常用的數據結構、與常用演算法
#學習內容： 1.數據結構的定義 2.演算法的定義 3.複雜度分析 4.常用數據結構 數組、鏈表、棧、隊列 散列表、二叉樹、堆 跳錶、圖 5.常用演算法 遞歸、排序、二分查找 搜索、哈希、貪心、分治 動態規劃、字元串匹配
到目前為止，基於線性表的數據結構我們都看完了，簡單回顧一下，它們是：數組、鏈表、棧、隊列。這些數據結構是其它數據結構與演算法的基礎，需要重點關注。
這一篇開始，我們開啟演算法的列車了，請系好安全帶！第一個要看的演算法是：遞歸。遞歸這兩個字你一定很熟悉，有沒有？
如果沒有的話，我們先舉一個例子。從2016年開始到如今，知識付費發展的如火如荼。如果你也是其中的一員，比如說在xx平台購買了xx課程。大多數平台都會告訴你，將你購買的課程分享出去，假如有人通過你分享的鏈接購買了該課程，那麼平台會給你傭金返現。
既然與錢有關係，那就比較麻煩了！對於平台來說，有這麼幾個問題需要搞清楚。比如說：1.誰是一級推薦人？
2.誰是二級推薦人……？
3.誰是最終推薦人？
因為不同級的推薦人，返現傭金的比例可不一樣，千萬別返錯了，對吧。關於這種類似求推薦人的問題，有請我們今天的主角登場，它就是：遞歸。
#遞歸稍微有些複雜，我們通過兩篇來學習： 1.第一篇是見面禮： 1.1.體會兩個生活中的小案例 2.第二篇是重頭戲： 2.1.詳細分析遞歸的實現 2.2.遞歸實現的注意事項
簡述：
1.A在某某知識付費平台購買了課程：xx。並將鏈接分享到了微信朋友圈
2.B通過A分享的鏈接，購買了課程：xx。並且將鏈接分享到了微信朋友圈
3.C通過B分享的鏈接，購買了課程：xx。並且將連接分享到了微信朋友圈
4.以此類推下去……
5.假如以C為起點，如何求出課程：xx的最終推薦人？
6.假設資料庫中存儲的數據是這樣的：
求解：
1.你肯定想到了，這個問題好簡單，經常寫如下類似這樣的程式碼：
/** * 求最終推薦人 */ public String findRootRecommend(String userId,String xx){ // 根據購買課程用戶id、課程 查詢資料庫，獲取推薦用戶id String 【分享用戶id】 = select 【分享用戶id】 from 【購買課程表】 where 【用戶id】 = 【userId】 and 【課程id】 = 【xx】; // 判斷是否是根據好友分享購買的課程 if(分享用戶id == null){ return userId; } // 遞歸查找 return findRootRecommend(分享用戶id,xx); }
1.你與女朋友正在電影院看電影，電影已經放映
2.突然，女朋友問你：我們坐在電影院的第幾排？
3.你一看，壞了：電影院一片漆黑，伸手不見五指
4.這個問題必須要回答，因為是女朋友問的，你該怎麼辦？
求解：
1.別忘了，你是程式設計師，對於程式設計師來說，這個問題太簡單了
2.用遞歸：先問前一排的人，他們在第幾排？
3.前一排的人，再問他的前一排，在第幾排？
4.以此類推……
5.一直問到第一排的人，第一排不需要再問了，直接回答在第一排
6.第二排的人：在第一排的人基礎上 + 1
7.以此類推……
8.每一排都在前一排的基礎上 + 1，最後到了你們這一排，女朋友得到了滿意的答案
9.你很驕傲有沒有？用程式碼回答，類似這樣：
public int movies(int n){ // 如果是第一排，返回1 if(n == 1){ return 1;} // 遞歸向前一排詢問 return movies(n - 1) + 1; }
