## 遞歸 相信在數學中很常見這個概念，實際在編程中也很常見這樣的思維。遞歸通俗的來說，就是通過不斷的將當前問題進行分解，向前追溯直到終點然后再反推求解的過程。 ## 通俗解讀 ### 案例一 ：看電影不知道在第幾排 看電影時不清楚自己在第幾排，可以通過問前一排的人來得知，進行加1即可。那么用遞歸的思路求解代碼就是這樣的。 ``` function fn = (n) { if(n< = 0) return '座位不存在' if(n>1) { return fn(n-1)+1 } else { return 1 } } ``` ### 案例二 ：走格子有多少走法 一共有n格，每步可以走1格或者2格，問一共有多少走法。 首先分解問題是第n格可以是前面n-1格走的，也可能是n-2格走的。所以fn(n) = f(n-1) + f(n-2)。也要知道終止條件是只有1步，那么只有一步的可能情況是還有1格，也可能是還有2格。 ``` function fn = (n){ if(n>2){ return fn(n-1) + fn(n-2) } else if(n==2) { return 2 } else { return 1 } } ``` ## 核心要點解析 ### 可以分解為子問題 也就是返回的遞歸子問題與當前問題的邏輯拆解關系 ### 這個問題與分解之后的子問題，除了數據規模不同，其他都是相同的 也就是子問題的解法與當前問題是完全一致的，不需要區別寫法 ### 有終止條件 不再進行遞歸的判斷條件，并且知道臨界條件的特殊值是可求的 ## 實際問題 ### 堆棧溢出 當遞歸層級過深的時候，因為在遞歸的過程中會一直把臨時變量封裝為棧壓入內存棧，如果一直壓入，就會導致溢出導致服務崩潰。通常的解決方案是設置一個遞歸深度來進行限制。 比如下面的代碼：則假定內存深度為1000，超過1000則拋出異常。 ``` let depth = 0 let f = (n) => { ++depth if(depth>1000) throw error() if(n===1) return 1 return fn(n-1) + 1 } ``` 說明：這種不是很實用，因為內存一般是動態變化的，用定值沒意義，而如果動態獲取內存，又小題大做了。 ### 重復計算 還是上面的遞歸計算走法的案例，不難發現會重復計算一些中間步驟的走法，導致浪費。當然這種問題不一定會有，和問題的分解有關。  優化方式是針對已經得到結果的走法計到Map緩存中直接使用。 ``` let f = ( n) => { if (n == 1) return 1; if (n == 2) return 2; // hasSolvedList 可以理解成一個 Map，key 是 n，value 是 f(n) if (hasSolvedList.containsKey(n)) { return hasSovledList.get(n); } ley ret = f(n-1) + f(n-2); hasSovledList.put(n, ret); return ret; } ``` ### 無限遞歸 也就是沒有辦法找到終止條件的情況要考慮進，主要是避免死循環或者臟數據的影響 ## 總結 本文主要介紹了常見的遞歸案例，可以用遞歸的核心點以及遞歸可能存在的問題。 ## 彩蛋~~ 魔法幣挑戰 > 小易準備去魔法王國采購魔法神器,購買魔法神器需要使用魔法幣,但是小易現在一枚魔法幣都沒有,但是小易有兩臺魔法機器可以通過投入x(x可以為0)個魔法幣產生更多的魔法幣。 > 魔法機器1:如果投入x個魔法幣,魔法機器會將其變為2x+1個魔法幣 > 魔法機器2:如果投入x個魔法幣,魔法機器會將其變為2x+2個魔法幣 > 小易采購魔法神器總共需要n個魔法幣,所以小易只能通過兩臺魔法機器產生恰好n個魔法幣,小易需要你幫他設計一個投入方案使他最后恰好擁有n個魔法幣 如果你對這項游戲的解法有興趣，就請跳轉下面的鏈接介紹吧，有代碼有真相。 - [魔法幣遞歸通關](http://doc.damobing.com/fe-tech/565316)