遞歸 —— 你值得擁有
相信很多人對遞歸的認(rèn)知是這樣的：
function?foo()?{
????foo();
}
就是一個函數(shù)在它內(nèi)部又調(diào)用了自己，簡稱自我調(diào)用。
刷新對遞歸的認(rèn)知
如果遇到一個問題，你說你可以用遞歸解決，基本上大家都會覺得這不是一個最好的方案。
如果另一個人說，他不用遞歸就可以搞定了，基本上大家都會認(rèn)為他的方法比你的牛逼些。
怎么說呢，就是大部分人可能對遞歸都是有點“偏見”的，或多或少罷了。
我想這可能和遞歸的執(zhí)行過程有關(guān)，一個函數(shù)在還沒有執(zhí)行完時又調(diào)用了自己，這就需要保存函數(shù)調(diào)用的當(dāng)前上下文，然后發(fā)起一個新的函數(shù)調(diào)用。
結(jié)果又是這樣子，又是在函數(shù)還沒有執(zhí)行完時再次調(diào)用了自己，那就需要繼續(xù)保存本次函數(shù)調(diào)用的上下文，然后再發(fā)起一次新的函數(shù)調(diào)用。
如此這般下去，會造成調(diào)用層次嵌套太深，保存的函數(shù)調(diào)用上下文過多，然后把線程棧空間用完了，最后就是StackOverflow了。
這是事實，任何人都無法辯解，自然我也不例外。但我還是建議那些對遞歸不太喜歡的開發(fā)人員要適當(dāng)?shù)母淖冏约旱倪@個看法。
備注：尾遞歸可以避免這個問題。
把遞歸看作是函數(shù)的自我調(diào)用，是一種十分狹隘的思想。我們應(yīng)該提高自己的認(rèn)知，推而廣之的來看遞歸，就會發(fā)現(xiàn)：
遞歸就是某種形式的不斷重復(fù)，結(jié)果構(gòu)成了閉環(huán)。（當(dāng)然，最后是可以跳出來的。）
按照這個觀點去思考，你會發(fā)現(xiàn)我們生活在遞歸中。不相信嗎？一起快速看看吧。
2019的春夏秋冬即將過完，馬上就又迎來了2020的春夏秋冬，一年四季的變換無窮無盡何時休。這是不是遞歸？當(dāng)然是啦。
還有每天24小時的晝夜交替永不停歇。還有每天上班打卡下班回家，天天如此仿佛看不到盡頭。還有老子生兒子，兒子生孫子，世世代代的生老病死。
還有電磁波的傳播，就是變化的電場產(chǎn)生了磁場，變化的磁場又產(chǎn)生了電場，電場和磁場相互交替著向前傳播。
以上這些都可以認(rèn)為是遞歸。所以不要只看表明現(xiàn)象，要看事物的本質(zhì)是不是某種形式的重復(fù)，且形成了閉環(huán)，最后在適當(dāng)?shù)臈l件下又跳出了這個環(huán)。
總之，接受遞歸，將會擁有一片更為廣闊的天地。
識別出構(gòu)成遞歸的要素
有些遞歸很明顯，一眼就看出來了。有些則很含蓄，需要仔細(xì)甄別才行。這就造成有些簡單、有些很難。
但是當(dāng)你寫出來后，又發(fā)現(xiàn)其實也沒有那么難，我相信這種感覺應(yīng)該都有過。今天就以科學(xué)的分析方法來搞一把，看看結(jié)論是什么？
根據(jù)上一小節(jié)的描述，我們知道遞歸必然是一種重復(fù)，而且還有跳出這種重復(fù)的條件。
因此，我們認(rèn)為遞歸至少包含兩個要素：重復(fù)體和跳出條件。
結(jié)合一個最簡單的示例來檢驗一下。比如，求N個自然數(shù)的和。就是
n + (n - 1) + (n - 2) + ... + 2 + 1
這樣一個表達(dá)式的值。
我們很容易寫出一個遞歸來：
function?sum(n)?{
????if?(n?==?1)?{
????????return?1;
????}
????return?n?+?sum(n?-?1);
}
不難看出這里的重復(fù)體就是sum()函數(shù)自身，因為它一直在自我調(diào)用。而跳出條件也十分明顯，就是n == 1。
這種最簡單形式的遞歸是符合我們剛剛提出的觀點的，再來看另一個稍微復(fù)雜點的情況。
假如在草原上遇到一群動物在奔跑，普遍人就認(rèn)為這可能就是一次普通的集體活動而已，但是專家可能識別出它們是在集體遷徙。
這區(qū)別是很大的，遷徙的話就是從A地到B地，等來年某個時候再從B地回到A地，這不就是遞歸嘛，而普通活動則肯定不是遞歸。
這里的問題是為什么“專家”能夠看出是遞歸，而我們普通人看不出呢？這是因為參與遞歸的A地和B地相距太遠(yuǎn)，我們?nèi)狈I(yè)知識，識別不出來。
根據(jù)這個，我們就又可以得出兩個要素：遞歸中的重復(fù)體可以是兩個和這兩個重復(fù)體互相調(diào)用的條件。
我們還使用求自然數(shù)和的例子，但是加一個限制條件，奇數(shù)和偶數(shù)分別用兩個函數(shù)來處理。
下面代碼僅僅用作示例，可能沒有什么實際意義：
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()這兩個函數(shù)都是重復(fù)體，它們互調(diào)對方，合起來構(gòu)成遞歸。互調(diào)對方的條件就是n是奇數(shù)還是偶數(shù)，跳出條件就是n是1或是2。
既然重復(fù)體可以有兩個，那么就可以有三個甚至更多，不過原理都是一樣的。因此我們可以得出遞歸三要素：
1）識別出重復(fù)體，可能是多個。
2）如果是多個，識別出重復(fù)體間的互調(diào)和自調(diào)條件。
3）識別出跳出條件，以便結(jié)束。
通俗的講就是，重復(fù)體越多越復(fù)雜，它們既可以互相調(diào)用也可以自我調(diào)用，一個重復(fù)體可以調(diào)多個重復(fù)體，多個重復(fù)體也可以調(diào)用一個重復(fù)體。
而且會有很多調(diào)用條件，只有在條件滿足某個重復(fù)體的時候才會發(fā)起對它的調(diào)用。而且在自我調(diào)用時也要滿足某個條件。
如果把重復(fù)體看作節(jié)點，把調(diào)用關(guān)系看作邊，十分復(fù)雜的遞歸就會變得像蜘蛛網(wǎng)一樣密密麻麻的。
小試牛刀not分配律
利用上面的結(jié)論，再結(jié)合一個相對有意義的案例，來試試看。之前遇到一個邏輯表達(dá)式求值的問題，表達(dá)式由操作數(shù)、and、or、not和括號組成。
一開始為了簡單，就做了個規(guī)定，not只能作用于操作數(shù)，不能作用于括號。就是這樣子的：
not A and not B 是可以的，not (A and B) 是不可以的。
后來需求有變，確實也需要支持not作用于括號的這種情況。但是我又不想修改解析表達(dá)式的代碼，好像也不太好改。
因為表達(dá)式字符串轉(zhuǎn)換成表達(dá)式樹之后，括號就沒有了。它本來就是起一個優(yōu)先級的作用，因為樹的節(jié)點本身就帶有優(yōu)先級了。
關(guān)鍵一開始就沒有這方面的設(shè)計，所以要改的話，改動量較大，后來轉(zhuǎn)念一想，我何不把not分配到括號里面呢，就像這樣：
not (A and B) -> (not A or not B)
這樣是完全等價的，而且表達(dá)式解析代碼一點也不用改。
所以接下來要做的就是，通過純字符串操作把not分配到括號里面，然后再解析，我把它稱為not分配律。
其實這個不用遞歸使用while循環(huán)也可以，只需要自己維護(hù)好進(jìn)入/退出括號這個上下文和對應(yīng)的not情況即可。
不過這里還是采用遞歸實現(xiàn)。仔細(xì)分析后發(fā)現(xiàn)，我們只需處理not后面是左括號的這種情況，如果不是只需原樣不動就行。
這樣的問題一時不太好想，那就把所有的情況都列出來，找找規(guī)律。
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)
看完之后發(fā)現(xiàn)，其實這里也存在不需要遞歸的情況，比如前四種一個循環(huán)就可以了。第五種有了括號前面的not后就需要遞歸了。
可能乍一看認(rèn)為也不需要啊，但是要寫成這樣呢：
not (not (not (A or B)))
可以很多層嵌套，這回肯定需要了。所以：
當(dāng)not遇上左括號這種情況就是一個重復(fù)體。調(diào)用這個重復(fù)體的條件自然就是not遇上左括號。
只有這一個重復(fù)體嗎？我們嘗試把表達(dá)式再嵌套一層看看：
not (A or not (B or C) and D)
當(dāng)not分配到括號里后，會與里面括號前面的not抵消掉，這樣里面的括號只需原樣不動就可以，括號結(jié)束后，not繼續(xù)與括號后面的部分進(jìn)行轉(zhuǎn)換。
所有內(nèi)部括號這部分相當(dāng)于一個獨立的上下文，外層括號是一個上下文，這涉及到從外層上下文進(jìn)入內(nèi)部上下文，然后再退出內(nèi)部上下文回到外層上下文。
所以內(nèi)部的括號雖然最終沒有not，但也是一個重復(fù)體，于是就有：
在上面那個重復(fù)體里的括號也是一個重復(fù)體，調(diào)用條件就是在上面那個重復(fù)體里遇到左括號。
通俗一點說就是帶not的括號里面出現(xiàn)了不帶not的括號。
還可以再復(fù)雜點，再增加一層嵌套看看：
not (A or not (B or C and not (D or E)) and F)
通俗的說就是帶not的括號里是不帶not的括號，該括號里又有了帶not的括號。
即三層括號嵌套，這樣我們就需要在第二個重復(fù)體里調(diào)用第一個重復(fù)體，調(diào)用條件依然是在第二個重復(fù)體里遇上not加左括號。
這樣這兩個重復(fù)體之間就形成了互相調(diào)用，調(diào)用條件是在自己的重復(fù)體內(nèi)遇到了括號或not加括號。造成互相調(diào)用的原因就是括號的嵌套和not的存在。
所以遞歸調(diào)用確實有很多的上下文，這些上下文會自動保存和還原，因此如果采用非遞歸形式的話，這個上下文就需要自己保存和還原了。
而且有些遞歸非常復(fù)雜時，基本上轉(zhuǎn)變?yōu)榉沁f歸的形式非常困難，有的可能轉(zhuǎn)不成。
最后總結(jié)一下：
整個過程既有非遞歸部分也有遞歸部分。遞歸部分有兩個重復(fù)體。從非遞歸部分只能進(jìn)入遞歸部分的第一個重復(fù)體，進(jìn)入條件是遇上not加左括號。
這兩個重復(fù)體可以互相調(diào)用，也可以自己調(diào)自己。調(diào)用條件上面已經(jīng)說的很明白了。這兩個重復(fù)體的退出條件都是遇到右括號。
當(dāng)所有嵌套調(diào)用的重復(fù)體全部都退出時，遞歸部分就執(zhí)行完畢，接著進(jìn)入非遞歸部分繼續(xù)執(zhí)行，然后還可以再次進(jìn)入遞歸部分，然后再退出。
直到最后表達(dá)式字符串處理完畢，就全部結(jié)束了。最后再重復(fù)下這句話：
遞歸確實有一定的難度，但是當(dāng)你寫出來后，發(fā)現(xiàn)也不過如此。
發(fā)現(xiàn)遞歸四要素理論
我們發(fā)現(xiàn)在遞歸的三要素上還要再加一個要素，就是重復(fù)體也會有退出條件，控制著某個重復(fù)體的執(zhí)行結(jié)束。
這樣就構(gòu)成了遞歸四要素：
1）識別出重復(fù)體，可能是多個。
2）如果是多個，識別出重復(fù)體間的互調(diào)和自調(diào)條件。
3）如果是多個，識別出重復(fù)體的退出條件。
4）識別出跳出條件，以便結(jié)束。
個人感覺：
使用遞歸解決問題，思考起來較難，但代碼寫起來簡單。
使用while循環(huán)解決問題，思考起來簡單，但代碼寫起來較難。
自我發(fā)問：
那么我們什么時候才能跳出自己的遞歸呢？答案是，鬼知道。
請問鬼是誰？我怎么知道，你去問鬼啊。WTF！
推薦阿里云推廣服務(wù)器89/年，229/3年，買來送自己，送女朋友馬上過年再合適不過了，買了搭建個項目給面試官看也香，還可以熟悉技術(shù)棧，(老用戶用家人賬號買就好了，我用我女朋友的?）。掃碼購買
我這里還有購買后的教程：搭建教程，從0開始一步一步帶你搭建?
兩年嘔心瀝血的文章：「面試題」「基礎(chǔ)」「進(jìn)階」這里全都有！