乾貨|遞歸 —— 你值得擁有

• 2020 年 3 月 10 日
• 筆記

function foo() { foo();} 就是一個函數在它內部又調用了自己，簡稱自我調用 刷新對遞歸的認知 如果遇到一個問題，你說你可以用遞歸解決，基本上大家都會覺得這不是一個最好的方案。 如果另一個人說，他不用遞歸就可以搞定了，基本上大家都會認為他的方法比你的牛逼些。 怎麼說呢，就是大部分人可能對遞歸都是有點「偏見」的，或多或少罷了。 我想這可能和遞歸的執行過程有關，一個函數在還沒有執行完時又調用了自己，這就需要保存函數調用的當前上下文，然後發起一個新的函數調用。 結果又是這樣子，又是在函數還沒有執行完時再次調用了自己，那就需要繼續保存本次函數調用的上下文，然後再發起一次新的函數調用。 如此這般下去，會造成調用層次嵌套太深，保存的函數調用上下文過多，然後把執行緒棧空間用完了，最後就是StackOverflow了。 這是事實，任何人都無法辯解，自然我也不例外。但我還是建議那些對遞歸不太喜歡的開發人員要適當的改變自己的這個看法。 備註：尾遞歸可以避免這個問題。 把遞歸看作是函數的自我調用，是一種十分狹隘的思想。我們應該提高自己的認知，推而廣之的來看遞歸，就會發現： 遞歸就是某種形式的不斷重複，結果構成了閉環。（當然，最後是可以跳出來的。） 按照這個觀點去思考，你會發現我們生活在遞歸中。不相信嗎？一起快速看看吧。 2019的春夏秋冬即將過完，馬上就又迎來了2020的春夏秋冬，一年四季的變換無窮無盡何時休。這是不是遞歸？當然是啦。 還有每天24小時的晝夜交替永不停歇。還有每天上班打卡下班回家，天天如此彷彿看不到盡頭。還有老子生兒子，兒子生孫子，世世代代的生老病死。 還有電磁波的傳播，就是變化的電場產生了磁場，變化的磁場又產生了電場，電場和磁場相互交替著向前傳播。 以上這些都可以認為是遞歸。所以不要只看錶明現象，要看事物的本質是不是某種形式的重複，且形成了閉環，最後在適當的條件下又跳出了這個環。 總之，接受遞歸，將會擁有一片更為廣闊的天地。 識別出構成遞歸的要素 有些遞歸很明顯，一眼就看出來了。有些則很含蓄，需要仔細甄別才行。這就造成有些簡單、有些很難。 但是當你寫出來後，又發現其實也沒有那麼難，我相信這種感覺應該都有過。今天就以科學的分析方法來搞一把，看看結論是什麼？ 根據上一小節的描述，我們知道遞歸必然是一種重複，而且還有跳出這種重複的條件。 因此，我們認為遞歸至少包含兩個要素：重複體和跳出條件。 結合一個最簡單的示例來檢驗一下。比如，求N個自然數的和。就是 n + (n – 1) + (n – 2) + … + 2 + 1 這樣一個表達式的值。 我們很容易寫出一個遞歸來：

function sum(n) { if (n == 1) { return 1; } return n + sum(n - 1);} 不難看出這裡的重複體就是sum()函數自身，因為它一直在自我調用。而跳出條件也十分明顯，就是n == 1。 這種最簡單形式的遞歸是符合我們剛剛提出的觀點的，再來看另一個稍微複雜點的情況。 假如在草原上遇到一群動物在奔跑，普遍人就認為這可能就是一次普通的集體活動而已，但是專家可能識別出它們是在集體遷徙。 這區別是很大的，遷徙的話就是從A地到B地，等來年某個時候再從B地回到A地，這不就是遞歸嘛，而普通活動則肯定不是遞歸。 這裡的問題是為什麼「專家」能夠看出是遞歸，而我們普通人看不出呢？這是因為參與遞歸的A地和B地相距太遠，我們缺乏專業知識，識別不出來。 根據這個，我們就又可以得出兩個要素：遞歸中的重複體可以是兩個和這兩個重複體互相調用的條件。 我們還使用求自然數和的例子，但是加一個限制條件，奇數和偶數分別用兩個函數來處理。 下面程式碼僅僅用作示例，可能沒有什麼實際意義：

function oddSum(n) { if (n == 1) { return 1; } if (n % 2 == 1) { return n + evenSum(n - 1); } return evenSum(n);}

function evenSum(n) { if (n == 2) { return 2; } if (n % 2 == 0) { return n + oddSum(n - 1); } return oddSum(n);} 不難看出oddSum()和evenSum()這兩個函數都是重複體，它們互調對方，合起來構成遞歸。互調對方的條件就是n是奇數還是偶數，跳出條件就是n是1或是2。 既然重複體可以有兩個，那麼就可以有三個甚至更多，不過原理都是一樣的。因此我們可以得出遞歸三要素： 1）識別出重複體，可能是多個。 2）如果是多個，識別出重複體間的互調和自調條件。 3）識別出跳出條件，以便結束。 通俗的講就是，重複體越多越複雜，它們既可以互相調用也可以自我調用，一個重複體可以調多個重複體，多個重複體也可以調用一個重複體。 而且會有很多調用條件，只有在條件滿足某個重複體的時候才會發起對它的調用。而且在自我調用時也要滿足某個條件。 如果把重複體看作節點，把調用關係看作邊，十分複雜的遞歸就會變得像蜘蛛網一樣密密麻麻的。 小試牛刀not分配律 利用上面的結論，再結合一個相對有意義的案例，來試試看。之前遇到一個邏輯表達式求值的問題，表達式由操作數、and、or、not和括弧組成。 一開始為了簡單，就做了個規定，not只能作用於操作數，不能作用於括弧。就是這樣子的： not A and not B 是可以的，not (A and B) 是不可以的。 後來需求有變，確實也需要支援not作用於括弧的這種情況。但是我又不想修改解析表達式的程式碼，好像也不太好改。 因為表達式字元串轉換成表達式樹之後，括弧就沒有了。它本來就是起一個優先順序的作用，因為樹的節點本身就帶有優先順序了。 關鍵一開始就沒有這方面的設計，所以要改的話，改動量較大，後來轉念一想，我何不把not分配到括弧裡面呢，就像這樣： not (A and B) -> (not A or not B) 這樣是完全等價的，而且表達式解析程式碼一點也不用改。 所以接下來要做的就是，通過純字元串操作把not分配到括弧裡面，然後再解析，我把它稱為not分配律。 其實這個不用遞歸使用while循環也可以，只需要自己維護好進入/退出括弧這個上下文和對應的not情況即可。 不過這裡還是採用遞歸實現。仔細分析後發現，我們只需處理not後面是左括弧的這種情況，如果不是只需原樣不動就行。 這樣的問題一時不太好想，那就把所有的情況都列出來，找找規律。 1）沒有括弧沒有not的，A or B 2）沒有括弧有not的，not A or not B 3）有括弧沒有not的，(A or B) and C 4）有不在括弧前的not的，(not A or not B) and not C 5）有在括弧前的not的，not (A or B) 看完之後發現，其實這裡也存在不需要遞歸的情況，比如前四種一個循環就可以了。第五種有了括弧前面的not後就需要遞歸了。 可能乍一看認為也不需要啊，但是要寫成這樣呢： not (not (not (A or B))) 可以很多層嵌套，這回肯定需要了。所以： 當not遇上左括弧這種情況就是一個重複體。調用這個重複體的條件自然就是not遇上左括弧。 只有這一個重複體嗎？我們嘗試把表達式再嵌套一層看看： not (A or not (B or C) and D) 當not分配到括弧里後，會與裡面括弧前面的not抵消掉，這樣裡面的括弧只需原樣不動就可以，括弧結束後，not繼續與括弧後面的部分進行轉換。 所有內部括弧這部分相當於一個獨立的上下文，外層括弧是一個上下文，這涉及到從外層上下文進入內部上下文，然後再退出內部上下文回到外層上下文。 所以內部的括弧雖然最終沒有not，但也是一個重複體，於是就有： 在上面那個重複體里的括弧也是一個重複體，調用條件就是在上面那個重複體里遇到左括弧。 通俗一點說就是帶not的括弧裡面出現了不帶not的括弧。 還可以再複雜點，再增加一層嵌套看看： not (A or not (B or C and not (D or E)) and F) 通俗的說就是帶not的括弧里是不帶not的括弧，該括弧里又有了帶not的括弧。 即三層括弧嵌套，這樣我們就需要在第二個重複體里調用第一個重複體，調用條件依然是在第二個重複體里遇上not加左括弧。 這樣這兩個重複體之間就形成了互相調用，調用條件是在自己的重複體內遇到了括弧或not加括弧。造成互相調用的原因就是括弧的嵌套和not的存在。 所以遞歸調用確實有很多的上下文，這些上下文會自動保存和還原，因此如果採用非遞歸形式的話，這個上下文就需要自己保存和還原了。 而且有些遞歸非常複雜時，基本上轉變為非遞歸的形式非常困難，有的可能轉不成。 最後總結一下： 整個過程既有非遞歸部分也有遞歸部分。遞歸部分有兩個重複體。從非遞歸部分只能進入遞歸部分的第一個重複體，進入條件是遇上not加左括弧。 這兩個重複體可以互相調用，也可以自己調自己。調用條件上面已經說的很明白了。這兩個重複體的退出條件都是遇到右括弧。 當所有嵌套調用的重複體全部都退出時，遞歸部分就執行完畢，接著進入非遞歸部分繼續執行，然後還可以再次進入遞歸部分，然後再退出。 直到最後表達式字元串處理完畢，就全部結束了。最後再重複下這句話： 遞歸確實有一定的難度，但是當你寫出來後，發現也不過如此。 發現遞歸四要素理論 我們發現在遞歸的三要素上還要再加一個要素，就是重複體也會有退出條件，控制著某個重複體的執行結束。 這樣就構成了遞歸四要素： 1）識別出重複體，可能是多個。 2）如果是多個，識別出重複體間的互調和自調條件。 3）如果是多個，識別出重複體的退出條件。 4）識別出跳出條件，以便結束。 個人感覺： 使用遞歸解決問題，思考起來較難，但程式碼寫起來簡單。 使用while循環解決問題，思考起來簡單，但程式碼寫起來較難。 自我發問： 那麼我們什麼時候才能跳出自己的遞歸呢？答案是，鬼知道。 請問鬼是誰？我怎麼知道，你去問鬼啊。WTF！ 原文作者：編程新說李新傑 原文鏈接：https://mp.weixin.qq.com/s/bstfd2gZmLM3aVPGeT-N-Q 好課推薦 「人人都會微信小程式」 超低門檻 快速上手 帶你打造屬於自己的小程式 課程原價49 限時優惠只需4.9 點擊閱讀原文 立刻開始學習 若需了解更多 請掃碼添加小助手諮詢 也可直接查找微訊號：TencentNext ▲ NEXT學院 官方課程助教 ▲