你對遞歸很糾結嗎?
雖然代碼量少，理解起來太費勁？如果你這么想那就對了。
因為我們人類的思維方式和遞歸的實現邏輯是有沖突的！我們想問題根本不那么想。
可是程序員面試不得不準備算法題，尤其是競爭激烈的公司，不管你進去擰不擰螺絲釘。
算法題中超過50%的問題直接或間接的與遞歸相關。
重要事情說三遍，因為這很重要！
今天我們就掰開它看看，到底有多難。
玩過俄羅斯套娃么？一層一層的套，里面有更小的娃娃。
如果中間某個娃娃里面放了一枚鉆戒，讓你去找出來—這就是嵌套問題的一種。
俄羅斯套娃
聽過馬三立的《祖傳秘方》單口相聲么？治療渾身發癢的神器-紙條包紙條（答案是：撓撓）
實際上，答案不一定在最后一張紙條里面，哪張都可能，哈哈。沒看過的自己補一下。
單口相聲-祖傳秘方
開心完了看看理解遞歸的的關鍵是啥：
- 輸出并不總是按照它在代碼中出現的順序出現。最重要的是按照編譯器的方式遍歷代碼。
- 按照代碼順序前后關系理解輸出，你就完蛋了。
例子說話：
就走一遍啥也沒干是啥樣？
嵌套Stack
執行結果看下面：全都入棧，再從孩子的孩子最底層執行出來。
in stack for recurser_print(5) output not trigger yet
in stack for recurser_print(4) output not trigger yet
in stack for recurser_print(3) output not trigger yet
in stack for recurser_print(2) output not trigger yet
in stack for recurser_print(1) output not trigger yet
exit and print n for recurser_print(1)
exit and print n for recurser_print(2)
exit and print n for recurser_print(3)
exit and print n for recurser_print(4)
exit and print n for recurser_print(5)
還是沒太明白？加個圖：只有一個門，后進先出來。計算機得記得它先后要干活的具體順序。
嵌套算法
基本執行看明白了，一個基本例子理解一下：
- 例子：求n的階乘
- 如果n=5 那么 數學計算方法： result = 5 * (5-1) * (5-2) * (5-3) * (5-4)也就是 5*(4*(3*(2*(1))))
特點：
- 總結的函數式就是遞歸自己調用自己的寫法:F = n*f(n-1)
- 父親使用兒子的返回結果
求n的階乘
運行結果：
In stack:3
In stack:2
out stack:2 -人工添加
out stack:3 - 人工添加
6
總結：
嵌套算法的特點：
• 每次有不同的輸入
• 但是每次運算相同
• 必須有停止嵌套的條件（防止死循環）
• 與循環的不同：每次輸入數據范圍縮小
為什么要用嵌套算法：
• 能用嵌套不用循環：好寫 好讀，-- 這條可以有異議
• 問題可以分解為相同的小問題（處理的數據范圍變小）
• 廣泛應用于 樹， 圖 數據結構中
• 比如： 樹的深度優先搜索，如果你發現一個問題可以通過搜索來解決，那么你就有一個很好的遞歸算法候選。
