告別遞歸，談?wù)勎业囊恍┙?jīng)驗(yàn)

兩年前公眾號(hào)發(fā)過(guò)遞歸的文章，好評(píng)如潮，不過(guò)當(dāng)時(shí)存在一些錯(cuò)誤，如今修復(fù)了，并且訓(xùn)練題也提供了

可能很多人在大一的時(shí)候，就已經(jīng)接觸了遞歸了，不過(guò)，我敢保證很多人初學(xué)者剛開(kāi)始接觸遞歸的時(shí)候，是一臉懵逼的，我當(dāng)初也是，給我的感覺(jué)就是，遞歸太神奇了！

可能也有一大部分人知道遞歸，也能看的懂遞歸，但在實(shí)際做題過(guò)程中，卻不知道怎么使用，有時(shí)候還容易被遞歸給搞暈。也有好幾個(gè)人來(lái)問(wèn)我有沒(méi)有快速掌握遞歸的捷徑啊。說(shuō)實(shí)話，哪來(lái)那么多捷徑啊，不過(guò)，我還是想寫(xiě)一篇文章，談?wù)勎业囊恍┙?jīng)驗(yàn)，或許，能夠給你帶來(lái)一些幫助。

為了兼顧初學(xué)者，我會(huì)從最簡(jiǎn)單的題講起！

遞歸的三大要素

第一要素：明確你這個(gè)函數(shù)想要干什么

對(duì)于遞歸，我覺(jué)得很重要的一個(gè)事就是，這個(gè)函數(shù)的功能是什么，他要完成什么樣的一件事，而這個(gè)，是完全由你自己來(lái)定義的。也就是說(shuō)，我們先不管函數(shù)里面的代碼什么，而是要先明白，你這個(gè)函數(shù)是要用來(lái)干什么。

例如，我定義了一個(gè)函數(shù)

// 算 n 的階乘(假設(shè)n不為0)
int f(int n){
    
}

這個(gè)函數(shù)的功能是算 n 的階乘。好了，我們已經(jīng)定義了一個(gè)函數(shù)，并且定義了它的功能是什么，接下來(lái)我們看第二要素。

第二要素：尋找遞歸結(jié)束條件

所謂遞歸，就是會(huì)在函數(shù)內(nèi)部代碼中，調(diào)用這個(gè)函數(shù)本身，所以，我們必須要找出遞歸的結(jié)束條件，不然的話，會(huì)一直調(diào)用自己，進(jìn)入無(wú)底洞。也就是說(shuō)，我們需要找出當(dāng)參數(shù)為啥時(shí)，遞歸結(jié)束，之后直接把結(jié)果返回，請(qǐng)注意，這個(gè)時(shí)候我們必須能根據(jù)這個(gè)參數(shù)的值，能夠直接知道函數(shù)的結(jié)果是什么。

例如，上面那個(gè)例子，當(dāng) n = 1 時(shí)，那你應(yīng)該能夠直接知道 f(n) 是啥吧？此時(shí)，f(1) = 1。完善我們函數(shù)內(nèi)部的代碼，把第二要素加進(jìn)代碼里面，如下

// 算 n 的階乘(假設(shè)n不為0)
int f(int n){
    if(n == 1){
        return 1;
    }
}

有人可能會(huì)說(shuō)，當(dāng) n = 2 時(shí)，那我們可以直接知道 f(n) 等于多少啊，那我可以把 n = 2 作為遞歸的結(jié)束條件嗎？

當(dāng)然可以，只要你覺(jué)得參數(shù)是什么時(shí)，你能夠直接知道函數(shù)的結(jié)果，那么你就可以把這個(gè)參數(shù)作為結(jié)束的條件，所以下面這段代碼也是可以的。

// 算 n 的階乘(假設(shè)n>=2)
int f(int n){
    if(n == 2){
        return 2;
    }
}

注意我代碼里面寫(xiě)的注釋?zhuān)僭O(shè) n >= 2，因?yàn)槿绻?n = 1時(shí)，會(huì)被漏掉，當(dāng) n <= 2時(shí)，f(n) = n，所以為了更加嚴(yán)謹(jǐn)，我們可以寫(xiě)成這樣：

// 算 n 的階乘(假設(shè)n不為0)
int f(int n){
    if(n <= 2){
        return n;
    }
}

第三要素：找出函數(shù)的等價(jià)關(guān)系式

第三要素就是，我們要不斷縮小參數(shù)的范圍，縮小之后，我們可以通過(guò)一些輔助的變量或者操作，使原函數(shù)的結(jié)果不變。

例如，f(n) 這個(gè)范圍比較大，我們可以讓 f(n) = n * f(n-1)。這樣，范圍就由 n 變成了 n-1 了，范圍變小了，并且為了原函數(shù)f(n) 不變，我們需要讓 f(n-1) 乘以 n。

說(shuō)白了，就是要找到原函數(shù)的一個(gè)等價(jià)關(guān)系式，f(n) 的等價(jià)關(guān)系式為 n * f(n-1)，即

f(n) = n *  f(n-1)。

這個(gè)等價(jià)關(guān)系式的尋找，可以說(shuō)是最難的一步了，如果你不大懂也沒(méi)關(guān)系，因?yàn)槟悴皇翘觳?，你還需要多接觸幾道題，我會(huì)在接下來(lái)的文章中，找一些遞歸題，讓你慢慢熟悉起來(lái)。

找出了這個(gè)等價(jià)，繼續(xù)完善我們的代碼，我們把這個(gè)等價(jià)式寫(xiě)進(jìn)函數(shù)里。如下：

// 算 n 的階乘(假設(shè)n不為0)
int f(int n){
    if(n <= 2){
        return n;
    }
    // 把 f(n) 的等價(jià)操作寫(xiě)進(jìn)去
    return f(n-1) * n;
}

至此，遞歸三要素已經(jīng)都寫(xiě)進(jìn)代碼里了，所以這個(gè) f(n) 功能的內(nèi)部代碼我們已經(jīng)寫(xiě)好了。

這就是遞歸最重要的三要素，每次做遞歸的時(shí)候，你就強(qiáng)迫自己試著去尋找這三個(gè)要素。

還是不懂？沒(méi)關(guān)系，我再按照這個(gè)模式講一些題。

有些有點(diǎn)小基礎(chǔ)的可能覺(jué)得我寫(xiě)的太簡(jiǎn)單了，沒(méi)耐心看？少俠，請(qǐng)繼續(xù)看，我下面還會(huì)講如何優(yōu)化遞歸。當(dāng)然，大佬請(qǐng)隨意，可以直接拉動(dòng)最下面留言給我一些建議，萬(wàn)分感謝！

案例1：斐波那契數(shù)列

斐波那契數(shù)列的是這樣一個(gè)數(shù)列：1、1、2、3、5、8、13、21、34....，即第一項(xiàng) f(1) = 1,第二項(xiàng) f(2) = 1.....,第 n 項(xiàng)目為 f(n) = f(n-1) + f(n-2)。求第 n 項(xiàng)的值是多少。

1、第一遞歸函數(shù)功能

假設(shè) f(n) 的功能是求第 n 項(xiàng)的值，代碼如下：

int f(int n){
    
}

2、找出遞歸結(jié)束的條件

顯然，當(dāng) n = 1 或者 n = 2 ,我們可以輕易著知道結(jié)果 f(1) = f(2) = 1。所以遞歸結(jié)束條件可以為  n <= 2。代碼如下：

int f(int n){
    if(n <= 2){
        return 1;
    }
}

第三要素：找出函數(shù)的等價(jià)關(guān)系式

題目已經(jīng)把等價(jià)關(guān)系式給我們了，所以我們很容易就能夠知道 f(n) = f(n-1) + f(n-2)。我說(shuō)過(guò)，等價(jià)關(guān)系式是最難找的一個(gè)，而這個(gè)題目卻把關(guān)系式給我們了，這也太容易，好吧，我這是為了兼顧幾乎零基礎(chǔ)的讀者。

所以最終代碼如下：

int f(int n){
    // 1.先寫(xiě)遞歸結(jié)束條件
    if(n <= 2){
        return 1;
    }
    // 2.接著寫(xiě)等價(jià)關(guān)系式
    return f(n-1) + f(n - 2);
}

搞定，是不是很簡(jiǎn)單？

零基礎(chǔ)的可能還是不大懂，沒(méi)關(guān)系，之后慢慢按照這個(gè)模式練習(xí)！好吧，有大佬可能在吐槽太簡(jiǎn)單了。

案例2：小青蛙跳臺(tái)階

一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。

1、第一遞歸函數(shù)功能

假設(shè) f(n) 的功能是求青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法，代碼如下：

int f(int n){
    
}

2、找出遞歸結(jié)束的條件

我說(shuō)了，求遞歸結(jié)束的條件，你直接把 n 壓縮到很小很小就行了，因?yàn)?n 越小，我們就越容易直觀著算出 f(n) 的多少，所以當(dāng) n = 1時(shí)，你知道 f(1) 為多少吧？夠直觀吧？即 f(1) = 1。代碼如下：

int f(int n){
    if(n == 1){
        return 1;
    }
}

第三要素：找出函數(shù)的等價(jià)關(guān)系式

每次跳的時(shí)候，小青蛙可以跳一個(gè)臺(tái)階，也可以跳兩個(gè)臺(tái)階，也就是說(shuō)，每次跳的時(shí)候，小青蛙有兩種跳法。

第一種跳法：第一次我跳了一個(gè)臺(tái)階，那么還剩下n-1個(gè)臺(tái)階還沒(méi)跳，剩下的n-1個(gè)臺(tái)階的跳法有f(n-1)種。

第二種跳法：第一次跳了兩個(gè)臺(tái)階，那么還剩下n-2個(gè)臺(tái)階還沒(méi)，剩下的n-2個(gè)臺(tái)階的跳法有f(n-2)種。

所以，小青蛙的全部跳法就是這兩種跳法之和了，即 f(n) = f(n-1) + f(n-2)。至此，等價(jià)關(guān)系式就求出來(lái)了。于是寫(xiě)出代碼：

int f(int n){
    if(n == 1){
        return 1;
    }
    ruturn f(n-1) + f(n-2);
}

大家覺(jué)得上面的代碼對(duì)不對(duì)？

答是不大對(duì)，當(dāng) n = 2 時(shí)，顯然會(huì)有 f(2) = f(1) + f(0)。我們知道，f(0) = 0，按道理是遞歸結(jié)束，不用繼續(xù)往下調(diào)用的，但我們上面的代碼邏輯中，會(huì)繼續(xù)調(diào)用 f(0) = f(-1) + f(-2)。這會(huì)導(dǎo)致無(wú)限調(diào)用，進(jìn)入死循環(huán)。

這里有人覺(jué)得 f(0) 應(yīng)該是等于 1，等于 0 還是等于 1 不是很重要，此次我們就當(dāng)作是 0 處理哈。

這也是我要和你們說(shuō)的，關(guān)于遞歸結(jié)束條件是否夠嚴(yán)謹(jǐn)問(wèn)題，有很多人在使用遞歸的時(shí)候，由于結(jié)束條件不夠嚴(yán)謹(jǐn)，導(dǎo)致出現(xiàn)死循環(huán)。也就是說(shuō)，當(dāng)我們?cè)诘诙秸页隽艘粋€(gè)遞歸結(jié)束條件的時(shí)候，可以把結(jié)束條件寫(xiě)進(jìn)代碼，然后進(jìn)行第三步，但是請(qǐng)注意，當(dāng)我們第三步找出等價(jià)函數(shù)之后，還得再返回去第二步，根據(jù)第三步函數(shù)的調(diào)用關(guān)系，會(huì)不會(huì)出現(xiàn)一些漏掉的結(jié)束條件。就像上面，f(n-2)這個(gè)函數(shù)的調(diào)用，有可能出現(xiàn) f(0) 的情況，導(dǎo)致死循環(huán)，所以我們把它補(bǔ)上。代碼如下：

int f(int n){
    //f(0) = 0,f(1) = 1，等價(jià)于 n<=2時(shí)，f(n) = n。
    if(n <= 2){
        return n;
    }
    ruturn f(n-1) + f(n-2);
}

有人可能會(huì)說(shuō)，我不知道我的結(jié)束條件有沒(méi)有漏掉怎么辦？別怕，多練幾道就知道怎么辦了。

看到這里有人可能要吐槽了，這兩道題也太容易了吧？？能不能被這么敷衍。少俠，別走啊，下面出道難一點(diǎn)的。

下面其實(shí)也不難了，就比上面的題目難一點(diǎn)點(diǎn)而已，特別是第三步等價(jià)的尋找。

案例3：反轉(zhuǎn)單鏈表。

反轉(zhuǎn)單鏈表。例如鏈表為：1->2->3->4。反轉(zhuǎn)后為 4->3->2->1

鏈表的節(jié)點(diǎn)定義如下：

class Node{
    int date;
    Node next;
}

雖然是 Java語(yǔ)言，但就算你沒(méi)學(xué)過(guò) Java，我覺(jué)得也是影響不大，能看懂。

還是老套路，三要素一步一步來(lái)。

1、定義遞歸函數(shù)功能

假設(shè)函數(shù) reverseList(head) 的功能是反轉(zhuǎn)但鏈表，其中 head 表示鏈表的頭節(jié)點(diǎn)。代碼如下：

Node reverseList(Node head){
    
}

2. 尋找結(jié)束條件

當(dāng)鏈表只有一個(gè)節(jié)點(diǎn)，或者如果是空表的話，你應(yīng)該知道結(jié)果吧？直接啥也不用干，直接把 head 返回唄。代碼如下：

Node reverseList(Node head){
    if(head == null || head.next == null){
        return head;
    }
}

3. 尋找等價(jià)關(guān)系

這個(gè)的等價(jià)關(guān)系不像 n 是個(gè)數(shù)值那樣，比較容易尋找。但是我告訴你，它的等價(jià)條件中，一定是范圍不斷在縮小，對(duì)于鏈表來(lái)說(shuō)，就是鏈表的節(jié)點(diǎn)個(gè)數(shù)不斷在變小，所以，如果你實(shí)在找不出，你就先對(duì) reverseList(head.next) 遞歸走一遍，看看結(jié)果是咋樣的。例如鏈表節(jié)點(diǎn)如下

我們就縮小范圍，先對(duì) 2->3->4遞歸下試試，即代碼如下

Node reverseList(Node head){
    if(head == null || head.next == null){
        return head;
    }
    // 我們先把遞歸的結(jié)果保存起來(lái)，先不返回，因?yàn)槲覀冞€不清楚這樣遞歸是對(duì)還是錯(cuò)。，
    Node newList = reverseList(head.next);
}

我們?cè)诘谝徊降臅r(shí)候，就已經(jīng)定義了 reverseLis t函數(shù)的功能可以把一個(gè)單鏈表反轉(zhuǎn)，所以，我們對(duì) 2->3->4反轉(zhuǎn)之后的結(jié)果應(yīng)該是這樣：

我們把 2->3->4 遞歸成 4->3->2。不過(guò)，1 這個(gè)節(jié)點(diǎn)我們并沒(méi)有去碰它，所以 1 的 next 節(jié)點(diǎn)仍然是連接這 2。

接下來(lái)呢？該怎么辦？

其實(shí)，接下來(lái)就簡(jiǎn)單了，我們接下來(lái)只需要把節(jié)點(diǎn) 2 的 next 指向 1，然后把 1 的 next 指向 null,不就行了？，即通過(guò)改變 newList 鏈表之后的結(jié)果如下：

也就是說(shuō)，reverseList(head) 等價(jià)于 reverseList(head.next) + 改變一下1，2兩個(gè)節(jié)點(diǎn)的指向。好了，等價(jià)關(guān)系找出來(lái)了，代碼如下(有詳細(xì)的解釋)：

//用遞歸的方法反轉(zhuǎn)鏈表
public static Node reverseList2(Node head){
    // 1.遞歸結(jié)束條件
    if (head == null || head.next == null) {
             return head;
         }
         // 遞歸反轉(zhuǎn) 子鏈表
         Node newList = reverseList2(head.next);
         // 改變 1，2節(jié)點(diǎn)的指向。
         // 通過(guò) head.next獲取節(jié)點(diǎn)2
         Node t1  = head.next;
         // 讓 2 的 next 指向 1
         t1.next = head;
         // 1 的 next 指向 null.
        head.next = null;
        // 把調(diào)整之后的鏈表返回。
        return newList;
    }

這道題的第三步看的很懵？正常，因?yàn)槟阕龅奶倭?，可能沒(méi)有想到還可以這樣，多練幾道就可以了。但是，我希望通過(guò)這三道題，給了你以后用遞歸做題時(shí)的一些思路，你以后做題可以按照我這個(gè)模式去想。通過(guò)一篇文章是不可能掌握遞歸的，還得多練，我相信，只要你認(rèn)真看我的這篇文章，多看幾次，一定能找到一些思路?。?/p>

我已經(jīng)強(qiáng)調(diào)了好多次，多練幾道了，所以呢，后面我也會(huì)找大概一些遞歸的練習(xí)題供大家學(xué)習(xí)，不過(guò)，我找的可能會(huì)有一定的難度。不會(huì)像今天這樣，比較簡(jiǎn)單，所以呢，初學(xué)者還得自己多去找題練練，相信我，掌握了遞歸，你的思維抽象能力會(huì)更強(qiáng)！

接下來(lái)我講講有關(guān)遞歸的一些優(yōu)化。

有關(guān)遞歸的一些優(yōu)化思路

1. 考慮是否重復(fù)計(jì)算

告訴你吧，如果你使用遞歸的時(shí)候不進(jìn)行優(yōu)化，是有非常非常非常多的子問(wèn)題被重復(fù)計(jì)算的。

啥是子問(wèn)題？f(n-1),f(n-2)....就是 f(n) 的子問(wèn)題了。

例如對(duì)于案例2那道題，f(n) = f(n-1) + f(n-2)。遞歸調(diào)用的狀態(tài)圖如下：

看到?jīng)]有，遞歸計(jì)算的時(shí)候，重復(fù)計(jì)算了兩次 f(5)，五次 f(4)。。。。這是非?？植赖?，n 越大，重復(fù)計(jì)算的就越多，所以我們必須進(jìn)行優(yōu)化。

如何優(yōu)化？一般我們可以把我們計(jì)算的結(jié)果保證起來(lái)，例如把 f(4) 的計(jì)算結(jié)果保證起來(lái)，當(dāng)再次要計(jì)算 f(4) 的時(shí)候，我們先判斷一下，之前是否計(jì)算過(guò)，如果計(jì)算過(guò)，直接把 f(4) 的結(jié)果取出來(lái)就可以了，沒(méi)有計(jì)算過(guò)的話，再遞歸計(jì)算。

用什么保存呢？可以用數(shù)組或者 HashMap 保存，我們用數(shù)組來(lái)保存把，把 n 作為我們的數(shù)組下標(biāo)，f(n) 作為值，例如 arr[n] = f(n)。f(n) 還沒(méi)有計(jì)算過(guò)的時(shí)候，我們讓 arr[n] 等于一個(gè)特殊值，例如 arr[n] = -1。

當(dāng)我們要判斷的時(shí)候，如果 arr[n] = -1，則證明 f(n) 沒(méi)有計(jì)算過(guò)，否則， f(n) 就已經(jīng)計(jì)算過(guò)了，且 f(n) = arr[n]。直接把值取出來(lái)就行了。代碼如下：

// 我們實(shí)現(xiàn)假定 arr 數(shù)組已經(jīng)初始化好的了。
int f(int n){
    if(n <= 2){
        return n;
    }
    //先判斷有沒(méi)計(jì)算過(guò)
    if(arr[n] != -1){
        //計(jì)算過(guò)，直接返回
        return arr[n];
    }else{
        // 沒(méi)有計(jì)算過(guò)，遞歸計(jì)算,并且把結(jié)果保存到 arr數(shù)組里
        arr[n] = f(n-1) + f(n-2);
        return arr[n];
    }
}

也就是說(shuō)，使用遞歸的時(shí)候，必要 須要考慮有沒(méi)有重復(fù)計(jì)算，如果重復(fù)計(jì)算了，一定要把計(jì)算過(guò)的狀態(tài)保存起來(lái)。

2. 考慮是否可以自底向上

對(duì)于遞歸的問(wèn)題，我們一般都是從上往下遞歸的，直到遞歸到最底，再一層一層著把值返回。

不過(guò)，有時(shí)候當(dāng) n 比較大的時(shí)候，例如當(dāng) n = 10000 時(shí)，那么必須要往下遞歸10000層直到 n <=1 才將結(jié)果慢慢返回，如果n太大的話，可能棧空間會(huì)不夠用。

對(duì)于這種情況，其實(shí)我們是可以考慮自底向上的做法的。例如我知道

f(1) = 1;

f(2) = 2;

那么我們就可以推出 f(3) = f(2) + f(1) = 3。從而可以推出f(4),f(5)等直到f(n)。因此，我們可以考慮使用自底向上的方法來(lái)取代遞歸，代碼如下：

public int f(int n) {
       if(n <= 2)
           return n;
       int f1 = 1;
       int f2 = 2;
       int sum = 0;

       for (int i = 3; i <= n; i++) {
           sum = f1 + f2;
           f1 = f2;
           f2 = sum;
       }
       return sum;
   }

這種方法，其實(shí)也被稱之為遞推。

最后總結(jié)

其實(shí)，遞歸不一定總是從上往下，也是有很多是從下往上的，例如 n = 1 開(kāi)始，一直遞歸到 n = 1000，例如一些排序組合。對(duì)于這種從下往上的，也是有對(duì)應(yīng)的優(yōu)化技巧，不過(guò)，我就先不寫(xiě)了，后面再慢慢寫(xiě)。這篇文章寫(xiě)了很久了，脖子有點(diǎn)受不了了，，，，頸椎??？害怕。。。。

說(shuō)實(shí)話，對(duì)于遞歸這種比較抽象的思想，要把他講明白，特別是講給初學(xué)者聽(tīng)，還是挺難的，這也是我這篇文章用了很長(zhǎng)時(shí)間的原因，不過(guò)，只要能讓你們看完，有所收獲，我覺(jué)得值得！

相關(guān)訓(xùn)練題

另外，對(duì)應(yīng)的訓(xùn)練題已經(jīng)寫(xiě)好了，已經(jīng)同步到我的個(gè)人網(wǎng)站，可以在這里學(xué)：https://www.iamshuaidi.com/267.html（也可以閱讀原文直達(dá)，推薦PC端打開(kāi)）