推薦注冊(cè)返傭金這個(gè)功能我想你應(yīng)該不陌生吧？現(xiàn)在很多APP都有這個(gè)功能，這個(gè)功能中，用戶A推薦用戶B來注冊(cè)，用戶B又推薦用戶C來注冊(cè)。我們可以說，用戶C的最終推薦人為用戶A，用戶B的最終推薦人為用戶A，而用戶A沒有最終推薦人

一般來說，我們會(huì)通過數(shù)據(jù)庫來記錄這種推薦關(guān)系，在數(shù)據(jù)庫表中，我們可以記錄兩行數(shù)據(jù)，其中 actor_id 表示用戶 id, referrer-id 表示推薦人 id

picture1.jpg

基于這個(gè)背景，我的問題是？帶著這個(gè)問題，我們來學(xué)習(xí)今天的內(nèi)容，遞歸(Recursion)!

如何理解“遞歸”？

從我自己學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法的經(jīng)歷來看，我個(gè)人覺得，有兩個(gè)最難理解的知識(shí)點(diǎn)，一個(gè)是 ，另一個(gè)就是。

遞歸是一種應(yīng)用非常廣泛的算法（編程技巧）。很多數(shù)據(jù)結(jié)構(gòu)和算法的編碼實(shí)現(xiàn)都要用到遞歸，比如DFS深度優(yōu)先搜索、前中后序二叉樹遍歷等等。所以，搞懂遞歸非常重要，否則，后面復(fù)雜一些的數(shù)據(jù)結(jié)構(gòu)和算法學(xué)起來就會(huì)比較吃力。

不過，別看我說了這么多，遞歸本身可是一點(diǎn)都不“高冷”，咱們生活中就有很多用到遞歸的例子。

周末你帶著女朋友去電影院看電影，女朋友問你，咱們現(xiàn)在坐在第幾排??？電影院里面太黑了，看不清，沒法數(shù)，現(xiàn)在你怎么辦？

遞歸就開始派上用場(chǎng)了。于是你問前面一排的人他是第幾排，你想只要在他的數(shù)字上加一，就知道自己在哪一排了。但是前面的人也看不清啊，所以他也問他前面的人。就這樣一排一排的往前問，直到問到第一排的人，說我在第一排，然后再這樣一排一排再把數(shù)字傳回來。直到你前面的人告訴你他在那一排，于是你就知道答案了。

這是一個(gè)非常標(biāo)準(zhǔn)的遞歸求解的分解過程，去的過程“遞”，回來的過程叫“歸”?；旧?，所有的遞歸問題都可以用遞推公式來表示。剛剛這個(gè)生活中的例子，我們用遞推公式將它表示出來是這樣的：

f(n) = f(n-1) + 1 其中，f(1)= 1

f(n) 表示你想知道自己在哪一排，f(n-1) 表示前面一排所在的排數(shù)，f(1)=1 表示第一排的人知道自己在第一排。有了這個(gè)遞推公式，我們可以很輕松的改為遞歸代碼，如下：

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

遞歸需要滿足的三個(gè)條件

剛剛這個(gè)例子是非常典型的遞歸，那究竟什么樣的問題可以用遞歸來解決呢？只要同時(shí)滿足以下三個(gè)條件，就可以用遞歸來解決。

1.一個(gè)問題的解可以分解為幾個(gè)子問題的解

何為子問題？子問題就是數(shù)據(jù)規(guī)模更小的問題。比如，前面講的電影院的例子，你要知道，“自己在哪一排”的問題，可以分解為“前一排的人在哪一排”這樣一個(gè)子問題。

2.這個(gè)問題與分解之后的子問題，除了數(shù)據(jù)規(guī)模不同，求解思路完全一樣

比如電影院那個(gè)例子，你求解“自己在哪一排”的思路，和前面一排人求解“自己在哪一排”的思路是一模一樣的。

3.存在遞歸終止條件

把問題分解為子問題，把子問題再分解為子子問題，一層一層分解下去，不能存在無限循環(huán)，這就需要有終止條件。

還是電影院的例子，第一排的人不需要再繼續(xù)詢問任何人，就知道自己在哪一排，也就是f(1)=1,這就是遞歸的終止條件。

如何編寫遞歸代碼

剛剛鋪墊了很多，現(xiàn)在我們來看，如何來寫遞歸代碼？我個(gè)人覺得，寫遞歸代碼最關(guān)鍵的是寫出遞推公式，找到終止條件，剩下就是將遞推公式轉(zhuǎn)化為代碼就很簡(jiǎn)單了。

你先記住這個(gè)理論。我舉一個(gè)例子，帶你一步一步實(shí)現(xiàn)一個(gè)遞歸代碼，幫你理解。

假如這里有n個(gè)臺(tái)階，每次你可以跨1個(gè)臺(tái)階或者2個(gè)臺(tái)階，請(qǐng)問走這n個(gè)臺(tái)階有多少種走法？如果有7個(gè)臺(tái)階，你可以2，2，2，1這樣子上去，也可以1，2，1，1，2這樣子上去，總之走法很多，那如何用編程求得總共有多少種走法呢？

我們仔細(xì)想下，實(shí)際上，可以根據(jù)第一步的走法把所有走法分為兩類，第一類是第一步走了1個(gè)臺(tái)階，另一類是第一步走了2個(gè)臺(tái)階。所以n個(gè)臺(tái)階的走法就等于先走1階后，n-1個(gè)臺(tái)階的走法，加上先走2階后，n-2個(gè)臺(tái)階的走法。用公式法表示就是：

f(n) = f(n-1) + f(n-2)

有了遞推公式，遞歸代碼基本就完成了一半。我們?cè)賮砜聪陆K止條件。當(dāng)有一個(gè)臺(tái)階時(shí)，我們不需要再繼續(xù)遞歸，就只有一種走法。所以f(1)=1。這個(gè)遞歸終止條件足夠嗎？我們可以用n=2,n=3這樣比較小的數(shù)實(shí)驗(yàn)一下。

n=2時(shí)，f(2)=f(1)+f(0)。如果遞歸終止條件只有一個(gè)f(1)=1,那f(2)就無法求解了。所以除了f(1)=1這一個(gè)遞歸終止條件外，還有f(0)=1,表示走0個(gè)臺(tái)階有一種走法，不過這樣子看起來看起來就不符合正常的邏輯思維了。所以。我們可以把f(2)=2作為一種終止條件，表示走2個(gè)臺(tái)階，有兩種走法，一步走完或者分兩步來走。

所以，遞歸終止條件就是f(1)=1,f(2)=2,這個(gè)時(shí)候，你可以拿n=3,n=4來驗(yàn)證一下，這個(gè)終止條件是否足夠并且正確。

我們把遞歸終止條件和剛剛得到的遞推公式放到一起是這樣的：

f(1)=1;
f(2)=2;
f(n)=f(n-1)+f(n-2);

代碼：

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

總結(jié)：<font color=red>寫遞歸代碼的關(guān)鍵就是找到如何將大問題分解為小問題的規(guī)律，并且基于此寫出遞推公式，然后再推敲終止條件，最后將遞推公式和終止條件翻譯成代碼</font>

剛講的電影院的例子，我們的遞歸調(diào)用只有一個(gè)分支，也就是說“一個(gè)問題只需要分解為一個(gè)子問題”，我們就很容易能夠想清楚“遞”和“歸”的每一個(gè)步驟，所以寫起來、理解起來都不難。但是，當(dāng)我們面對(duì)的是一個(gè)問題需要分解多個(gè)子問題的情況，遞歸代碼就沒那么好理解了。剛剛第二個(gè)例子，人腦幾乎沒辦法把整個(gè)“遞”和“歸”的過程一步一步想清楚。

計(jì)算機(jī)擅長做重復(fù)的事情，所以遞歸正和它的胃口。而我們?nèi)四X更喜歡平鋪直敘的思維方式。當(dāng)我們看到遞歸時(shí)，我們總想把遞歸平鋪展開，腦子里就會(huì)循環(huán)，一層一層往下調(diào)，然后一層一層返回。這樣很容易繞進(jìn)去

對(duì)于遞歸代碼，這種試圖想清楚整個(gè)遞和歸過程的做法，實(shí)際上進(jìn)入了一個(gè)思維誤區(qū)。很多時(shí)候，我們理解起來比較吃力，主要原因就是自己給自己制造了這種理解障礙。那正確的思維方式是怎樣的呢？

如果一個(gè)問題A可以分解為若干子問題B、C、D，你可以假設(shè)子問題B、C、D已經(jīng)解決，在此基礎(chǔ)上思考如何解決問題A。而且，你只需要思考問題A與子問題B、C、D兩層之間的關(guān)系即可，不需要一層一層往下思考子問題與子子問題，子子問題與子子子問題之間的關(guān)系。屏蔽掉遞歸細(xì)節(jié)，這樣理解起來就簡(jiǎn)單多了。

因此，<font color=red>編寫遞歸代碼的關(guān)鍵是，只要遇到遞歸，我們就把它抽象成一個(gè)遞推公式，不用想一層層的調(diào)用關(guān)系，不要試圖用人腦分解遞歸的每個(gè)步驟</font>。

遞歸代碼要警惕堆棧溢出

在實(shí)際軟件開發(fā)中，編寫遞歸代碼時(shí)，我們會(huì)遇到很多問題，比如堆棧溢出。而堆棧溢出會(huì)造成系統(tǒng)性崩潰，后果非常嚴(yán)重。為什么遞歸代碼容易造成堆棧溢出呢？又改如何預(yù)防堆棧溢出呢？

函數(shù)調(diào)用會(huì)使用棧來保存臨時(shí)變量。每調(diào)用一個(gè)函數(shù)，都會(huì)將臨時(shí)變量封裝為棧幀壓入內(nèi)存棧，等函數(shù)執(zhí)行完成返回時(shí)，才出棧，系統(tǒng)?；蛘咛摂M機(jī)?？丶话愣疾淮蟆Ｈ绻f歸求解的數(shù)據(jù)規(guī)模很大，調(diào)用層次很深，一直壓入棧，就會(huì)有堆棧溢出的風(fēng)險(xiǎn)。

比如前面所講的電影院的例子，如果我們將系統(tǒng)棧或者JVM堆棧大小設(shè)置為1KB，在求解f(19999)時(shí)就會(huì)出現(xiàn)堆棧報(bào)錯(cuò)

那么，如何避免出現(xiàn)堆棧溢出呢？

我們可以通過在代碼中遞歸調(diào)用的最大深度的方式來解決這個(gè)問題。遞歸調(diào)用超過一定深度（比如1000）之后，我們就不繼續(xù)往下再遞歸了，直接返回報(bào)錯(cuò)。還是電影院那個(gè)例子，我們可以改造成下面這樣子，就可以避免堆棧溢出。

// 全局變量，表示遞歸的深度
int depth = 0;
inf f(int n) {
    ++depth;
    if (depth > 1000) throw exception;
    
    if (n==1) return 1;
    return f(n-1) + 1;
}

但這種做法并不能完全解決問題，因?yàn)樽畲笤试S的遞歸深度跟當(dāng)前線程剩余的?？臻g大小有關(guān)，事先無法計(jì)算，如果實(shí)時(shí)計(jì)算，代碼過于復(fù)雜，影響代碼可讀性。所以，如果最大深度比較小，比如 10，50 可以用這種方法。否則這種方法不實(shí)用

遞歸代碼要警惕重復(fù)計(jì)算

除此之外，使用遞歸時(shí)還會(huì)出現(xiàn)重復(fù)計(jì)算的問題。剛才我講的第二個(gè)遞歸代碼的例子，如果我們把整個(gè)遞歸過程分解一下的話，那就是這樣的：
[圖片上傳失敗...(image-806d36-1563369670168)]
從圖中，我們可以直觀看到，想要計(jì)算f(5)，需要先計(jì)算f(4)和f(3)，而計(jì)算f(4)還需要計(jì)算f(3)，因此f(3)就被計(jì)算很多次，這就是重復(fù)計(jì)算問題。

為了避免重復(fù)計(jì)算，我們可以通過一個(gè)數(shù)據(jù)結(jié)構(gòu)（散列表）來保存已經(jīng)求解過的f(k)。當(dāng)遞歸調(diào)用f(k)，先看下是否已經(jīng)求解過了。如果是，則直接從散列表返回，不需要重復(fù)計(jì)算。

按照上面的思路，改造一下代碼：

public int f(int n) {
    if (n==1) return 1;
    if (n==2) return 2;
    
    // hasSolvedList 可以理解成一個(gè)Map，key是n，value是f(n)
    if (hasSolvedList.containKey(n)) {
        return hasSolvedList.get(n);
    }
    
    int ret = f(n-1) + f(n-2);
    hasSolvedList.put(n, ret);
    return ret;
}

除了堆棧溢出、重復(fù)計(jì)算這兩個(gè)常見的問題，遞歸代碼還有很多別的問題。

在時(shí)間效率上，遞歸代碼多了很多函數(shù)調(diào)用，當(dāng)這些函數(shù)調(diào)用的數(shù)量較大時(shí)，就會(huì)積聚成一個(gè)可觀的時(shí)間成本。在空間復(fù)雜度上，因?yàn)檫f歸調(diào)用一次就會(huì)在內(nèi)存棧中保存一次現(xiàn)場(chǎng)數(shù)據(jù)，所以在分析遞歸代碼空間復(fù)雜度時(shí)，需要額外考慮這部分開銷。

怎么將遞歸代碼改寫為非遞歸代碼

遞歸有利有弊，利是遞歸代碼表達(dá)力很強(qiáng)，寫起來非常簡(jiǎn)潔；而弊就是空間復(fù)雜度高，有堆棧溢出的風(fēng)險(xiǎn)、存在重復(fù)計(jì)算、過多的函數(shù)調(diào)用會(huì)耗時(shí)較多等問題。所以，在開發(fā)時(shí)要根據(jù)實(shí)際情況來選擇是否用遞歸方式來實(shí)現(xiàn)。

學(xué)習(xí)來源：https://time.geekbang.org/column/article/41440