[TOC] >[success] # 遞歸 ~~~ 1.遞歸應該一種比較常見的實現一些特殊代碼邏輯時需要做的，但常常也是最繞的一種方式，在解釋遞歸 之前，我們用循環和遞歸來做個比較 1.1.如果你打開一扇門后，同樣發現前方也有一扇們，緊接著你又打開下一扇門...直到打開最后一扇門出去， 或者一直沒有碰到盡頭 （死循環）——'這就是循環' 1.2.如果你打開一扇門，緊接著你又用鑰匙打開了這扇門，然后你又看到一扇們...但是當你開到某扇門時， 發現前方是一堵墻無路可走了，你選擇原路返回——'這就是遞歸' 2.通過上面的故事可以發現遞歸其實是兩個過程 2.1.'遞'問題分解去的過程叫'遞' -- 就像故事打開的門 2.2.'歸'遇到終止'遞'的條件叫'歸' -- 就像故事里的墻 ~~~ >[info] ## 滿足遞歸的條件 ~~~ 1.遞歸是一種解決問題的方法，它從解決問題的各個小部分開始，直到解決最初的大問題。遞 歸通常涉及函數調用自身 2.還是上面開門的故事，你想知道你開啟的第一個門，實際是距離墻的第幾扇門，這個問題想要解決 根據第一條的概念進行拆分 2.1.'分解成各個小部分'，也就是我要知道我下一扇門距離墻是第幾扇門 2.2.'這個問題與分解之后的子問題，除了數據規模不同，求解思路完全一樣',我想知道開啟第一扇門距離墻 是第幾扇門，和我想知道下一扇門距離墻的位置是第幾扇門是一樣的 2.3.'存在遞歸終止條件',也就這些問題一層一層解析后，直到我知道扇的位置后終止，在一個個回來數 ~~~ >[danger] ##### 如何編寫遞歸 * 引用極客時間王爭老師的總結來說 ~~~ 1.寫出遞推公式，找到終止條件 2.寫遞歸代碼的關鍵就是找到如何將大問題分解為小問題的規律，并且基于此寫出遞推公式，然后再推敲終止條件， 最后將遞推公式和終止條件翻譯成代碼 3.編寫遞歸代碼的關鍵是，只要遇到遞歸，我們就把它抽象成一個遞推公式，不用想一層層的調用關系，不要試圖用人 腦去分解遞歸的每個步驟 ~~~ >[danger] ##### 遞歸到底是個什么 ~~~ 1.遞歸就是棧一種應用場景，也遵循著'先進后出的原則（后進先出）' ~~~