遞歸：如何用三行代碼找到“最終推薦人”
推薦注冊返傭金的這個(gè)功能我想你應(yīng)該不陌生吧？現(xiàn)在很多 App 都有這個(gè)功能陪汽。這個(gè)功能中，用戶 A 推薦用戶 B 來注冊，用戶 B 又推薦了用戶 C 來注冊便斥。我們可以說，用戶 C 的“最終推薦人”為用戶 A威始，用戶 B 的“最終推薦人”也為用戶 A枢纠，而用戶 A 沒有“最終推薦人”。
一般來說黎棠，我們會(huì)通過數(shù)據(jù)庫來記錄這種推薦關(guān)系晋渺。在數(shù)據(jù)庫表中镰绎，我們可以記錄兩行數(shù)據(jù)，其中 actor_id 表示用戶 id木西，referrer_id 表示推薦人 id畴栖。
基于這個(gè)背景，我的問題是八千，給定一個(gè)用戶 ID驶臊，如何查找這個(gè)用戶的“最終推薦人”？ 帶著這個(gè)問題叼丑，我們來學(xué)習(xí)今天的內(nèi)容关翎，遞歸（Recursion）！
如何理解“遞歸”鸠信？
從我自己學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法的經(jīng)歷來看纵寝，我個(gè)人覺得，有兩個(gè)最難理解的知識(shí)點(diǎn)星立，一個(gè)是動(dòng)態(tài)規(guī)劃爽茴，另一個(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)在你怎么辦秃嗜？
別忘了你是程序員，這個(gè)可難不倒你顿膨，遞歸就開始排上用場了锅锨。于是你就問前面一排的人他是第幾排，你想只要在他的數(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è)例子是非常典型的遞歸敬察，那究竟什么樣的問題可以用遞歸來解決呢秀睛？我總結(jié)了三個(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)化為代碼就很簡單了壕鹉。
你先記住這個(gè)理論。我舉一個(gè)例子聋涨，帶你一步一步實(shí)現(xiàn)一個(gè)遞歸代碼晾浴，幫你理解。
假如這里有 n 個(gè)臺(tái)階牍白，每次你可以跨 1 個(gè)臺(tái)階或者 2 個(gè)臺(tái)階脊凰，請問走這 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)
有了遞推公式，遞歸代碼基本上就完成了一半曙聂。我們再來看下終止條件晦炊。當(dāng)有一個(gè)臺(tái)階時(shí)，我們不需要再繼續(xù)遞歸宁脊，就只有一種走法断国。所以 f(1)=1。這個(gè)遞歸終止條件足夠嗎榆苞？我們可以用 n=2稳衬，n=3 這樣比較小的數(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)
有了這個(gè)公式叹阔，我們轉(zhuǎn)化成遞歸代碼就簡單多了。最終的遞歸代碼是這樣的：
if (n == 1) return 1;
if (n == 2) return 2;
return f(n-1) + f(n-2);
}
我總結(jié)一下传睹，寫遞歸代碼的關(guān)鍵就是找到如何將大問題分解為小問題的規(guī)律耳幢，并且基于此寫出遞推公式，然后再推敲終止條件欧啤，最后將遞推公式和終止條件翻譯成代碼睛藻。
雖然我講了這么多方法，但是作為初學(xué)者的你邢隧，現(xiàn)在是不是還是有種想不太清楚的感覺呢店印？實(shí)際上，我剛學(xué)遞歸的時(shí)候倒慧，也有這種感覺按摘，這也是文章開頭我說遞歸代碼比較難理解的地方。
剛講的電影院的例子纫谅，我們的遞歸調(diào)用只有一個(gè)分支炫贤，也就是說“一個(gè)問題只需要分解為一個(gè)子問題”，我們很容易能夠想清楚“遞“和”歸”的每一個(gè)步驟付秕，所以寫起來兰珍、理解起來都不難。
但是盹牧，當(dāng)我們面對的是一個(gè)問題要分解為多個(gè)子問題的情況俩垃，遞歸代碼就沒那么好理解了。
像我剛剛講的第二個(gè)例子汰寓，人腦幾乎沒辦法把整個(gè)“遞”和“歸”的過程一步一步都想清楚口柳。
計(jì)算機(jī)擅長做重復(fù)的事情，所以遞歸正和它的胃口有滑。而我們?nèi)四X更喜歡平鋪直敘的思維方式跃闹。當(dāng)我們看到遞歸時(shí)，我們總想把遞歸平鋪展開毛好，腦子里就會(huì)循環(huán)望艺，一層一層往下調(diào)，然后再一層一層返回肌访，試圖想搞清楚計(jì)算機(jī)每一步都是怎么執(zhí)行的找默，這樣就很容易被繞進(jìn)去。
對于遞歸代碼吼驶，這種試圖想清楚整個(gè)遞和歸過程的做法惩激，實(shí)際上是進(jìn)入了一個(gè)思維誤區(qū)店煞。很多時(shí)候，我們理解起來比較吃力风钻，主要原因就是自己給自己制造了這種理解障礙顷蟀。那正確的思維方式應(yīng)該是怎樣的呢？
如果一個(gè)問題 A 可以分解為若干子問題 B骡技、C鸣个、D，你可以假設(shè)子問題 B布朦、C囤萤、D 已經(jīng)解決，在此基礎(chǔ)上思考如何解決問題 A喝滞。而且阁将，你只需要思考問題 A 與子問題 B膏秫、C右遭、D 兩層之間的關(guān)系即可，不需要一層一層往下思考子問題與子子問題缤削，子子問題與子子子問題之間的關(guān)系窘哈。屏蔽掉遞歸細(xì)節(jié)，這樣子理解起來就簡單多了亭敢。
因此滚婉，編寫遞歸代碼的關(guān)鍵是，只要遇到遞歸帅刀，我們就把它抽象成一個(gè)遞推公式让腹，不用想一層層的調(diào)用關(guān)系，不要試圖用人腦去分解遞歸的每個(gè)步驟扣溺。
遞歸代碼要警惕堆棧溢出
在實(shí)際的軟件開發(fā)中骇窍，編寫遞歸代碼時(shí)，我們會(huì)遇到很多問題锥余，比如堆棧溢出腹纳。而堆棧溢出會(huì)造成系統(tǒng)性崩潰，后果會(huì)非常嚴(yán)重驱犹。為什么遞歸代碼容易造成堆棧溢出呢嘲恍？我們又該如何預(yù)防堆棧溢出呢？
我在“椥劬裕”那一節(jié)講過佃牛，函數(shù)調(diào)用會(huì)使用棧來保存臨時(shí)變量。每調(diào)用一個(gè)函數(shù)医舆，都會(huì)將臨時(shí)變量封裝為棧幀壓入內(nèi)存棧俘侠，等函數(shù)執(zhí)行完成返回時(shí)桑涎，才出棧。系統(tǒng)椉婀保或者虛擬機(jī)椆ダ洌空間一般都不大。如果遞歸求解的數(shù)據(jù)規(guī)模很大，調(diào)用層次很深博投，一直壓入棧廓旬，就會(huì)有堆棧溢出的風(fēng)險(xiǎn)。
比如前面的講到的電影院的例子禁谦，如果我們將系統(tǒng)棧或者 JVM 堆棧大小設(shè)置為 1KB废封，在求解 f(19999) 時(shí)便會(huì)出現(xiàn)如下堆棧報(bào)錯(cuò)：
Exception in thread "main" java.lang.StackOverflowError
那么州泊，如何避免出現(xiàn)堆棧溢出呢？
我們可以通過在代碼中限制遞歸調(diào)用的最大深度的方式來解決這個(gè)問題漂洋。遞歸調(diào)用超過一定深度（比如 1000）之后遥皂，我們就不繼續(xù)往下再遞歸了，直接返回報(bào)錯(cuò)刽漂。還是電影院那個(gè)例子演训，我們可以改造成下面這樣子，就可以避免堆棧溢出了贝咙。不過样悟，我寫的代碼是偽代碼，為了代碼簡潔庭猩，有些邊界條件沒有考慮窟她，比如 x<=0。
// 全局變量蔼水，表示遞歸的深度震糖。
int depth = 0;
int f(int n) {
++depth；
if (depth > 1000) throw exception;
if (n == 1) return 1;
return f(n-1) + 1;
}
但這種做法并不能完全解決問題徙缴，因?yàn)樽畲笤试S的遞歸深度跟當(dāng)前線程剩余的検曰铮空間大小有關(guān)，事先無法計(jì)算于样。如果實(shí)時(shí)計(jì)算疏叨，代碼過于復(fù)雜，就會(huì)影響代碼的可讀性穿剖。所以蚤蔓，如果最大深度比較小，比如 10糊余、50秀又，就可以用這種方法单寂，否則這種方法并不是很實(shí)用。
遞歸代碼要警惕重復(fù)計(jì)算
除此之外吐辙，使用遞歸時(shí)還會(huì)出現(xiàn)重復(fù)計(jì)算的問題宣决。剛才我講的第二個(gè)遞歸代碼的例子，如果我們把整個(gè)遞歸過程分解一下的話昏苏，那就是這樣的：
從圖中尊沸，我們可以直觀地看到，想要計(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) 時(shí)，先看下是否已經(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.containsKey(n)) {
return hasSovledList.get(n);
}
int ret = f(n-1) + f(n-2);
hasSovledList.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)場數(shù)據(jù)，所以在分析遞歸代碼空間復(fù)雜度時(shí)垢乙，需要額外考慮這部分的開銷锨咙，比如我們前面講到的電影院遞歸代碼，空間復(fù)雜度并不是 O(1)追逮，而是 O(n)酪刀。
怎么將遞歸代碼改寫為非遞歸代碼粹舵？
我們剛說了，遞歸有利有弊骂倘，利是遞歸代碼的表達(dá)力很強(qiáng)眼滤，寫起來非常簡潔；而弊就是空間復(fù)雜度高历涝、有堆棧溢出的風(fēng)險(xiǎn)柠偶、存在重復(fù)計(jì)算、過多的函數(shù)調(diào)用會(huì)耗時(shí)較多等問題睬关。所以诱担，在開發(fā)過程中，我們要根據(jù)實(shí)際情況來選擇是否需要用遞歸的方式來實(shí)現(xiàn)电爹。
那我們是否可以把遞歸代碼改寫為非遞歸代碼呢蔫仙？比如剛才那個(gè)電影院的例子，我們拋開場景丐箩，只看 f(x) =f(x-1)+1 這個(gè)遞推公式摇邦。我們這樣改寫看看：
int f(int n) {
int ret = 1;
for (int i = 2; i <= n; ++i) {
ret = ret + 1;
}
return ret;
}
同樣，第二個(gè)例子也可以改為非遞歸的實(shí)現(xiàn)方式屎勘。
int f(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
int ret = 0;
int pre = 2;
int prepre = 1;
for (int i = 3; i <= n; ++i) {
ret = pre + prepre;
prepre = pre;
pre = ret;
}
return ret;
}
那是不是所有的遞歸代碼都可以改為這種迭代循環(huán)的非遞歸寫法呢施籍？
籠統(tǒng)地講，是的概漱。因?yàn)檫f歸本身就是借助棧來實(shí)現(xiàn)的丑慎，只不過我們使用的棧是系統(tǒng)或者虛擬機(jī)本身提供的，我們沒有感知罷了瓤摧。如果我們自己在內(nèi)存堆上實(shí)現(xiàn)棧竿裂，手動(dòng)模擬入棧、出棧過程照弥，這樣任何遞歸代碼都可以改寫成看上去不是遞歸代碼的樣子腻异。
但是這種思路實(shí)際上是將遞歸改為了“手動(dòng)”遞歸，本質(zhì)并沒有變这揣，而且也并沒有解決前面講到的某些問題悔常，徒增了實(shí)現(xiàn)的復(fù)雜度。
解答開篇
到此為止给赞，遞歸相關(guān)的基礎(chǔ)知識(shí)已經(jīng)講完了机打，咱們來看一下開篇的問題：如何找到“最終推薦人”？我的解決方案是這樣的：
long findRootReferrerId(long actorId) {
Long referrerId = select referrer_id from [table] where actor_id = actorId;
if (referrerId == null) return actorId;
return findRootReferrerId(referrerId);
}
是不是非常簡潔塞俱？用三行代碼就能搞定了姐帚，不過在實(shí)際項(xiàng)目中，上面的代碼并不能工作障涯，為什么呢罐旗？這里面有兩個(gè)問題膳汪。
第一，如果遞歸很深九秀，可能會(huì)有堆棧溢出的問題遗嗽。
第二，如果數(shù)據(jù)庫里存在臟數(shù)據(jù)鼓蜒，我們還需要處理由此產(chǎn)生的無限遞歸問題痹换。比如 demo 環(huán)境下數(shù)據(jù)庫中，測試工程師為了方便測試都弹，會(huì)人為地插入一些數(shù)據(jù)娇豫，就會(huì)出現(xiàn)臟數(shù)據(jù)。如果 A 的推薦人是 B畅厢，B 的推薦人是 C冯痢，C 的推薦人是 A，這樣就會(huì)發(fā)生死循環(huán)框杜。
第一個(gè)問題浦楣，我前面已經(jīng)解答過了，可以用限制遞歸深度來解決咪辱。第二個(gè)問題振劳，也可以用限制遞歸深度來解決。不過油狂，還有一個(gè)更高級的處理方法历恐，就是自動(dòng)檢測 A-B-C-A 這種“環(huán)”的存在。如何來檢測環(huán)的存在呢选调？這個(gè)我暫時(shí)不細(xì)說夹供，你可以自己思考下，后面的章節(jié)我們還會(huì)講仁堪。
內(nèi)容小結(jié)
關(guān)于遞歸的知識(shí)，到這里就算全部講完了填渠。我來總結(jié)一下弦聂。
遞歸是一種非常高效、簡潔的編碼技巧氛什。只要是滿足“三個(gè)條件”的問題就可以通過遞歸代碼來解決莺葫。
不過遞歸代碼也比較難寫、難理解枪眉。編寫遞歸代碼的關(guān)鍵就是不要把自己繞進(jìn)去捺檬，正確姿勢是寫出遞推公式，找出終止條件贸铜，然后再翻譯成遞歸代碼堡纬。
遞歸代碼雖然簡潔高效聂受，但是，遞歸代碼也有很多弊端烤镐。比如蛋济，堆棧溢出、重復(fù)計(jì)算炮叶、函數(shù)調(diào)用耗時(shí)多碗旅、空間復(fù)雜度高等，所以镜悉，在編寫遞歸代碼的時(shí)候祟辟，一定要控制好這些副作用。
課后思考
我們平時(shí)調(diào)試代碼喜歡使用 IDE 的單步跟蹤功能侣肄，像規(guī)模比較大旧困、遞歸層次很深的遞歸代碼，幾乎無法使用這種調(diào)試方式茫孔。對于遞歸代碼叮喳，你有什么好的調(diào)試方法呢？
評論精選
調(diào)試遞歸:
1.打印日志發(fā)現(xiàn)缰贝，遞歸值馍悟。
2.結(jié)合條件斷點(diǎn)進(jìn)行調(diào)試。檢測環(huán)可以構(gòu)造一個(gè)set集合或者散列表(下面都叫散列表吧剩晴，為了方便)锣咒。每次獲取到上層推薦人就去散列表里先查，沒有查到的話就加入赞弥，如果存在則表示存在環(huán)了毅整。當(dāng)然，每一次查詢都是一個(gè)自己的散列表绽左，不能共用悼嫉。實(shí)際情況內(nèi)存不會(huì)耗費(fèi)太多。
界定問題能否用遞歸解決
1.一個(gè)問題的解可以分解為幾個(gè)子問題的解拼窥；
2.這個(gè)問題與分解子問題的求解思路完全相同戏蔑；
3.存在終止條件
編寫遞歸代碼的技巧
1.終止條件
2.遞推公式
3.清理現(xiàn)場
編寫遞歸的關(guān)鍵是思考終止條件，把問題抽象成一個(gè)遞推公式鲁纠，并信任它一定能幫我們完成任務(wù)总棵，不用想一層層的調(diào)用關(guān)系，試圖用人腦分解遞歸是反人類的改含，最多只能想兩三層情龄。
遞歸的缺點(diǎn)
遞歸會(huì)利用棧保存臨時(shí)變量，如果遞歸過深，會(huì)造成棧溢出骤视。解決方案是控制遞歸的深度鞍爱。
遞歸要警惕重復(fù)計(jì)算，遞歸分解的子問題尚胞、子子問題可能存在相同的情況硬霍，如果都一一計(jì)算的話，就會(huì)發(fā)生重復(fù)計(jì)算笼裳。解決方案是使用散列表來保存結(jié)算結(jié)果唯卖，每次開始計(jì)算前檢查散列表是否已經(jīng)有結(jié)算結(jié)果。
籠統(tǒng)地講躬柬，遞歸代碼都能用迭代循環(huán)來替換拜轨。
總結(jié)
一、什么是遞歸允青？
1.遞歸是一種非常高效橄碾、簡潔的編碼技巧，一種應(yīng)用非常廣泛的算法颠锉，比如DFS深度優(yōu)先搜索法牲、前中后序二叉樹遍歷等都是使用遞歸。
2.方法或函數(shù)調(diào)用自身的方式稱為遞歸調(diào)用琼掠，調(diào)用稱為遞拒垃，返回稱為歸。
3.基本上瓷蛙，所有的遞歸問題都可以用遞推公式來表示悼瓮，比如
f(n) = f(n-1) + 1;
f(n) = f(n-1) + f(n-2);
f(n)=n*f(n-1);
二、為什么使用遞歸艰猬？遞歸的優(yōu)缺點(diǎn)横堡？
1.優(yōu)點(diǎn)：代碼的表達(dá)力很強(qiáng)，寫起來簡潔冠桃。
2.缺點(diǎn)：空間復(fù)雜度高命贴、有堆棧溢出風(fēng)險(xiǎn)、存在重復(fù)計(jì)算食听、過多的函數(shù)調(diào)用會(huì)耗時(shí)較多等問題套么。
三、什么樣的問題可以用遞歸解決呢碳蛋？
一個(gè)問題只要同時(shí)滿足以下3個(gè)條件，就可以用遞歸來解決：
1.問題的解可以分解為幾個(gè)子問題的解省咨。何為子問題肃弟？就是數(shù)據(jù)規(guī)模更小的問題。
2.問題與子問題，除了數(shù)據(jù)規(guī)模不同笤受，求解思路完全一樣
3.存在遞歸終止條件
四穷缤、如何實(shí)現(xiàn)遞歸？
1.遞歸代碼編寫
寫遞歸代碼的關(guān)鍵就是找到如何將大問題分解為小問題的規(guī)律箩兽，并且基于此寫出遞推公式津肛，然后再推敲終止條件，最后將遞推公式和終止條件翻譯成代碼汗贫。
2.遞歸代碼理解
對于遞歸代碼身坐，若試圖想清楚整個(gè)遞和歸的過程，實(shí)際上是進(jìn)入了一個(gè)思維誤區(qū)落包。
那該如何理解遞歸代碼呢部蛇？如果一個(gè)問題A可以分解為若干個(gè)子問題B、C咐蝇、D涯鲁，你可以假設(shè)子問題B、C有序、D已經(jīng)解決抹腿。而且，你只需要思考問題A與子問題B旭寿、C警绩、D兩層之間的關(guān)系即可，不需要一層層往下思考子問題與子子問題许师，子子問題與子子子問題之間的關(guān)系房蝉。屏蔽掉遞歸細(xì)節(jié)，這樣子理解起來就簡單多了微渠。
因此搭幻，理解遞歸代碼，就把它抽象成一個(gè)遞推公式逞盆，不用想一層層的調(diào)用關(guān)系檀蹋，不要試圖用人腦去分解遞歸的每個(gè)步驟。
五云芦、遞歸常見問題及解決方案
1.警惕堆棧溢出：可以聲明一個(gè)全局變量來控制遞歸的深度俯逾，從而避免堆棧溢出。
2.警惕重復(fù)計(jì)算：通過某種數(shù)據(jù)結(jié)構(gòu)來保存已經(jīng)求解過的值舅逸，從而避免重復(fù)計(jì)算桌肴。
六、如何將遞歸改寫為非遞歸代碼琉历？
籠統(tǒng)的講坠七，所有的遞歸代碼都可以改寫為迭代循環(huán)的非遞歸寫法水醋。如何做？抽象出遞推公式彪置、初始值和邊界條件拄踪，然后用迭代循環(huán)實(shí)現(xiàn)。
