遞歸的理解

在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法的過(guò)程中，遞歸可能是比較難理解的一個(gè)知識(shí)點(diǎn)，每次都試著用自己的大腦去把一步一步去想清楚切省，結(jié)果最后把自己都繞暈了。

我們很多人都遇到過(guò)這種情況帕胆，讀源碼的時(shí)候朝捆，我們想弄清楚一個(gè)方法的具體實(shí)現(xiàn)，然后跟進(jìn)去發(fā)現(xiàn)里邊還有一個(gè)方法懒豹，然后我們又跟到新的方法里邊右蹦，結(jié)果發(fā)現(xiàn)里邊還有另一個(gè)新的方法……這樣跟了一層又一層，終于到了最后一層沒(méi)有再調(diào)用其他的方法歼捐，然后我們?cè)僖粚右粚臃祷厝ィ罱K弄明白了最初想了解的方法的作用（實(shí)際中這種方式是不推薦的晨汹，因?yàn)榍短缀芏鄬颖ⅲ詈蟾愕妙^都大了，卻忘記了最初是要干什么）淘这。其實(shí)這就是一個(gè)遞歸的過(guò)程剥扣，通過(guò)一層一層的去了解方法的作用巩剖，然后到最后再一層一層返回去，明白最初方法的作用钠怯。

到這里佳魔，我想大家其實(shí)對(duì)遞歸也有一定了解了。其實(shí)遞歸就是可以把原來(lái)一個(gè)大型復(fù)雜的任務(wù)晦炊，分解成一個(gè)或幾個(gè)與原任務(wù)有相類似求解方法的小任務(wù)鞠鲜，然后最后有一個(gè)終止條件。

遞歸的條件

由此我們可以總結(jié)出幾個(gè)使用遞歸需要滿足的條件：

• 一個(gè)問(wèn)題可以分解為一個(gè)或幾個(gè)子問(wèn)題
• 子問(wèn)題和原來(lái)問(wèn)題的求解方式相同断国，只是規(guī)模比原問(wèn)題小
• 存在終止條件贤姆，否則會(huì)變成無(wú)限循環(huán)

舉一個(gè)例子

前幾天刷劍指offer題庫(kù)，碰到了好多題都可以用遞歸的方法計(jì)算稳衬。比如其中一個(gè)經(jīng)典的跳臺(tái)階問(wèn)題霞捡。

題目描述

一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)薄疚。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法（先后次序不同算不同的結(jié)果）碧信。

解題思路

每次跳臺(tái)階都有兩個(gè)選擇，要么跳1級(jí)街夭，要么跳2級(jí)砰碴。只有1級(jí)臺(tái)階的時(shí)候只有跳1級(jí)1種跳法，有2級(jí)時(shí)有每次1級(jí)1級(jí)跳兩次和直接跳2級(jí)兩種跳法莱坎，當(dāng)有3級(jí)臺(tái)階的時(shí)候衣式，我們可以從第2級(jí)跳1級(jí)到第3級(jí)，也可以從第1級(jí)跳2級(jí)到第3級(jí)檐什，所以3級(jí)臺(tái)階的總跳法碴卧，就是1級(jí)臺(tái)階的總跳法和2級(jí)臺(tái)階的總跳法的總和，由此我們就發(fā)現(xiàn)了一個(gè)規(guī)律從3級(jí)之后的算法為 f(n)=f(n-1)+f(n-2)乃正，發(fā)現(xiàn)我們要求得結(jié)果符合斐波那契數(shù)列住册。所以我們想知道 n 級(jí)臺(tái)階總共有多少跳法，只要將 n-1 的跳法加上 n-2 的跳法就可以了瓮具。

代碼實(shí)現(xiàn)

public class Solution {
    public int JumpFloor(int target) {
        if(target<3){
            return target;
        }
        return JumpFloor(target - 1) + JumpFloor(target - 2);
    }
}

怎么使用遞歸

我們現(xiàn)在也對(duì)遞歸有一定的了解了荧飞，那遞歸該怎么用呢？其實(shí)在上邊例子中其實(shí)已經(jīng)給出了答案名党。首先叹阔，我們要通過(guò)規(guī)律推導(dǎo)出遞歸的公式，然后找到遞歸的終止條件传睹，然后把公式轉(zhuǎn)化為代碼就很容易了耳幢。就比如上邊例子中的解題思路中就是這一過(guò)程的實(shí)現(xiàn)。

有人覺(jué)得遞歸難以理解，可能是走入誤區(qū)睛藻，就像我一開(kāi)始舉得讀源碼的例子启上。一定要在腦子里把遞歸展開(kāi)，一層一層去調(diào)用店印，然后一層層的返回冈在，試圖去弄明白每一個(gè)過(guò)程，這其實(shí)就有點(diǎn)鉆牛角尖了按摘，尤其是當(dāng)一個(gè)問(wèn)題分解成好幾個(gè)子問(wèn)題包券，然后嵌套層數(shù)比較多的時(shí)候，我們的大腦是沒(méi)辦法把每一個(gè)過(guò)程都能想出來(lái)的院峡。相反計(jì)算機(jī)卻很擅長(zhǎng)這種重復(fù)的事情兴使，所以我們沒(méi)必要在大腦中去分解每一個(gè)步驟，我們只需要找到規(guī)律公式和終止條件照激，剩下的交給計(jì)算就行了发魄。

使用遞歸需要注意

在實(shí)際程序設(shè)計(jì)的時(shí)候，我們使用遞歸的時(shí)候要注意幾個(gè)問(wèn)題俩垃。

棧溢出問(wèn)題

我們都知道函數(shù)調(diào)用時(shí)會(huì)用棧來(lái)保存臨時(shí)變量励幼，每調(diào)用一個(gè)函數(shù)，都會(huì)將臨時(shí)變量封裝為棧幀壓入內(nèi)存棧口柳，等函數(shù)執(zhí)行結(jié)束才出棧苹粟。一般系統(tǒng)棧和虛擬機(jī)棧都不是很大，當(dāng)遞歸嵌套的次數(shù)較多的時(shí)候跃闹，就會(huì)有棧溢出的風(fēng)險(xiǎn)嵌削。

所以如果遞歸的次數(shù)比較小的時(shí)候我們可以考慮使用遞歸，否則我們就要考慮其他的方法望艺。

重復(fù)計(jì)算問(wèn)題

還是以跳臺(tái)階的例子來(lái)說(shuō)明苛秕，假如我們要計(jì)算 5 級(jí)臺(tái)階有多少種跳法，我們用我們推導(dǎo)出來(lái)公式來(lái)計(jì)算找默，f(5)=f(4)+f(3)艇劫，然后我們分別要求 f(4)=f(3)+f(2)，f(3)=f(2)+f(1)惩激，我們可以看到在求解 f(5) 的時(shí)候我們計(jì)算過(guò) f(3)店煞，而在計(jì)算 f(4) 的時(shí)候我們又計(jì)算了一遍 f(3)，同樣 f(2) 也被計(jì)算了多次风钻，這就是重復(fù)計(jì)算的問(wèn)題顷蟀。

我們可以用散列表來(lái)儲(chǔ)存已經(jīng)計(jì)算過(guò)的 f(n)，然后在每次計(jì)算的時(shí)候先去散列表里查有沒(méi)有被計(jì)算過(guò)骡技，如果有那么直接使用衩椒；如果沒(méi)有那把計(jì)算后的值存到散列表中，這樣就能避免重復(fù)計(jì)算的問(wèn)題。

我們按這個(gè)辦法修改一下上邊例子的代碼毛萌。

public class Solution {
    Map<Integer, Integer> resultMap = new HashMap<Integer, Integer>();
    public int JumpFloor(int target) {
        if(target < 3){
            return target;
        }
        if(resultMap.containsKey(target)){
            return resultMap.get(target);
        }
        int result = JumpFloor(target - 1) + JumpFloor(target - 2);
        resultMap.put(target, result);
        return result;
    }
}

效率問(wèn)題

由于多層遞歸的嵌套，所以會(huì)多次調(diào)用函數(shù)喝滞，當(dāng)次數(shù)達(dá)到一定數(shù)量的時(shí)候阁将，就會(huì)有很高的時(shí)間成本。在空間復(fù)雜度上右遭，因?yàn)檫f歸每調(diào)用一次就會(huì)在棧中保存一次現(xiàn)場(chǎng)數(shù)據(jù)做盅，所以每次都要產(chǎn)生這種額外的開(kāi)銷。

所以窘哈，雖然遞歸的代碼看上去非常簡(jiǎn)潔吹榴，但是也會(huì)有很多問(wèn)題，我們?cè)趯?shí)際使用的時(shí)候一定要注意遞歸可能會(huì)帶來(lái)的問(wèn)題滚婉。