一、什么是遞歸？
自己調(diào)用自己，當(dāng)業(yè)務(wù)邏輯符合以下三個(gè)條件的時(shí)候，就可以考慮使用遞歸來實(shí)現(xiàn)。
- 一個(gè)問題可以分解為多個(gè)子問題；
- 當(dāng)前問題與其子問題除了數(shù)據(jù)規(guī)模不同外，求解思路完全一樣；
- 存在遞歸終止條件；
二、為什么要使用遞歸？
理論上，任何遞歸代碼都可以使用非遞歸的方式進(jìn)行實(shí)現(xiàn)，那么為什么還要使用遞歸呢？
遞歸求解本質(zhì)上是使用系統(tǒng)提供的棧來實(shí)現(xiàn)的，由系統(tǒng)為我們自動(dòng)遞歸求解；如果改成非遞歸的方式，那么我們其實(shí)就是在手動(dòng)遞歸，本質(zhì)上這兩種方式?jīng)]有任何區(qū)別。但是相同的邏輯，兩份代碼，遞歸實(shí)現(xiàn)明顯更加地簡潔，更加有利系統(tǒng)的維護(hù)。
三、如何使用遞歸？
我們以一個(gè)實(shí)際的例子來演示如何使用遞歸。
假設(shè)，有n個(gè)臺(tái)階，我們一步可以跨一個(gè)臺(tái)階，也可以一步跨兩個(gè)臺(tái)階，那么這n個(gè)臺(tái)階總共有多少種跨法？
我們按照遞歸使用的三個(gè)條件來分析下：
- 是否可以分解為子問題？
- 是的，我們跨上第n階臺(tái)階時(shí)，要么是一步一個(gè)跨上去的，要么就是一步兩個(gè)跨上去的，所以問題就分解為“跨上n-1個(gè)臺(tái)階有多少種跨法”+“跨上n-2個(gè)臺(tái)階有多少種跨法”，遞推公式可以表示為f(n)=f(n-1)+f(n-2);
- 當(dāng)前問題和子問題的求解思路是否一樣？
- 是的
- 是否存在終止條件？
- 是的，當(dāng)n為1的時(shí)候，就一種跨法，當(dāng)n為2的時(shí)候有兩種跨法，當(dāng)n為3或者4的時(shí)候，可以拆解為子問題，所以終止條件就是f(1)=1,f(2)=2;
分析完之后，我們就得到了帶終止條件的遞推公式，再轉(zhuǎn)換為代碼即可：
int countSteps(int n){
if(n == 1) {
return 1;
}
if(n == 2) {
return 2;
}
return f(n-1) + f(n-2);
}
遞歸的求解過程確實(shí)很難一下子就理解清楚，這是由于我們?nèi)四X的機(jī)制造成的，誰都會(huì)感覺這樣。
我們應(yīng)該假設(shè)子問題f(n-1)和f(n-2)已經(jīng)得到求解，然后在此基礎(chǔ)上去求解當(dāng)前的問題f(n)，得到一個(gè)遞推公式，如此只思考兩層之間的關(guān)聯(lián)關(guān)系會(huì)簡單很多，千萬不要試圖去分解和理解每個(gè)遞歸層次的過程。
四、使用遞歸需要注意什么？
4.1 堆棧溢出
當(dāng)遞歸調(diào)用深度過深的時(shí)候，就很容易出現(xiàn)棧溢出的問題，此時(shí)最好的方法就是根據(jù)業(yè)務(wù)場景邏輯和JVM的棧大小確定一個(gè)合理的最大遞歸深度，當(dāng)超過該深度值的時(shí)候，程序拋出異常；
4.2 重復(fù)計(jì)算
子問題的子問題可能會(huì)出現(xiàn)重復(fù)的問題，比如f(6)=f(5)+f(4)，其中，f(5)和f(4)都會(huì)有子問題f(3)，那么f(3)應(yīng)該是不需要重復(fù)計(jì)算的。
我們可以將求解過的問題結(jié)果保存到散列表中，當(dāng)遞歸調(diào)用執(zhí)行時(shí)，先檢查該問題是否已經(jīng)求解過了，如果是那么直接從散列表中獲取結(jié)果返回即可，只有沒有求解過的問題，才繼續(xù)遞歸調(diào)用；
int countSteps(int n){
if(n == 1) {
return 1;
}
if(n == 2) {
return 2;
}
// 先從散列表中檢查是否已經(jīng)對(duì)f(n)求解過了
if(resultMap.get(n) != null){
return resultMap.get(n);
}
int result = f(n-1) + f(n-2);
// 將當(dāng)前問題f(n)結(jié)果保存到散列表
resultMap.put(n,result);
return result;
}
4.3 時(shí)空復(fù)雜度
空間復(fù)雜度方面，因?yàn)檫f歸深度決定著棧的使用程度，所以空間復(fù)雜度為O(n)；
時(shí)間復(fù)雜度上面，雖然入棧和出棧都是O(1)，但是如果遞歸深度較大的話，函數(shù)上下文切換等造成的時(shí)間開銷也會(huì)比較可觀；
4.4 遞歸環(huán)
有時(shí)候，可能由于臟數(shù)據(jù)的問題，會(huì)導(dǎo)致遞歸環(huán)的存在，比如在找原始推薦人的時(shí)候，A推薦了B，B推薦了C，C推薦了D，然后有一條臟數(shù)據(jù)，導(dǎo)致A的推薦人是D，那么在遞歸尋找原始推薦人的時(shí)候，就會(huì)陷入環(huán)中，可以設(shè)置一個(gè)最大遞歸深度來解決這個(gè)問題。
