一、什么是遞歸？

自己調(diào)用自己，當業(yè)務邏輯符合以下三個條件的時候，就可以考慮使用遞歸來實現(xiàn)。

一個問題可以分解為多個子問題；
當前問題與其子問題除了數(shù)據(jù)規(guī)模不同外，求解思路完全一樣；
存在遞歸終止條件；

二、為什么要使用遞歸？

理論上，任何遞歸代碼都可以使用非遞歸的方式進行實現(xiàn)，那么為什么還要使用遞歸呢？

遞歸求解本質(zhì)上是使用系統(tǒng)提供的棧來實現(xiàn)的，由系統(tǒng)為我們自動遞歸求解；如果改成非遞歸的方式，那么我們其實就是在手動遞歸，本質(zhì)上這兩種方式?jīng)]有任何區(qū)別。但是相同的邏輯，兩份代碼，遞歸實現(xiàn)明顯更加地簡潔，更加有利系統(tǒng)的維護。

三、如何使用遞歸？

我們以一個實際的例子來演示如何使用遞歸。

假設，有n個臺階，我們一步可以跨一個臺階，也可以一步跨兩個臺階，那么這n個臺階總共有多少種跨法？

我們按照遞歸使用的三個條件來分析下：

是否可以分解為子問題？
是的，我們跨上第n階臺階時，要么是一步一個跨上去的，要么就是一步兩個跨上去的，所以問題就分解為“跨上n-1個臺階有多少種跨法”+“跨上n-2個臺階有多少種跨法”，遞推公式可以表示為f(n)=f(n-1)+f(n-2);
當前問題和子問題的求解思路是否一樣？
是的
是否存在終止條件？
是的，當n為1的時候，就一種跨法，當n為2的時候有兩種跨法，當n為3或者4的時候，可以拆解為子問題，所以終止條件就是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);
}

遞歸的求解過程確實很難一下子就理解清楚，這是由于我們?nèi)四X的機制造成的，誰都會感覺這樣。

我們應該假設子問題f(n-1)和f(n-2)已經(jīng)得到求解，然后在此基礎上去求解當前的問題f(n)，得到一個遞推公式，如此只思考兩層之間的關聯(lián)關系會簡單很多，千萬不要試圖去分解和理解每個遞歸層次的過程。

四、使用遞歸需要注意什么？

4.1 堆棧溢出

當遞歸調(diào)用深度過深的時候，就很容易出現(xiàn)棧溢出的問題，此時最好的方法就是根據(jù)業(yè)務場景邏輯和JVM的棧大小確定一個合理的最大遞歸深度，當超過該深度值的時候，程序拋出異常；

4.2 重復計算

子問題的子問題可能會出現(xiàn)重復的問題，比如f(6)=f(5)+f(4)，其中，f(5)和f(4)都會有子問題f(3)，那么f(3)應該是不需要重復計算的。

我們可以將求解過的問題結(jié)果保存到散列表中，當遞歸調(diào)用執(zhí)行時，先檢查該問題是否已經(jīng)求解過了，如果是那么直接從散列表中獲取結(jié)果返回即可，只有沒有求解過的問題，才繼續(xù)遞歸調(diào)用；

int countSteps(int n){
    if(n == 1) {
        return 1;
    }
    if(n == 2) {
        return 2;
    }
    
    // 先從散列表中檢查是否已經(jīng)對f(n)求解過了
    if(resultMap.get(n) != null){
        return resultMap.get(n);
    }
    int result = f(n-1) + f(n-2);
    // 將當前問題f(n)結(jié)果保存到散列表
    resultMap.put(n,result);
    return result;
}