算法-遞歸 - 簡書

什么是遞歸硫痰？

簡單的說就是自己調(diào)用自己，用一個生活中的例子來解釋就是窜护，假設(shè)你有天和女朋友去電影院看電影效斑，你女朋友問你們現(xiàn)在坐的是第幾排，但是現(xiàn)在很黑看不清柄慰，然后你問你前面的人現(xiàn)在是第幾排鳍悠，前面的人也看不清他就問他前面的人税娜，直到問到第一排的那個人坐搔，然后第一排的人再往回傳直到告訴你。這就是一個非常標準的遞歸求解問題的分解過程敬矩，去的過程叫“遞”概行，回來的過程叫“歸”。所有的遞歸問題都可以用遞推公式來表示弧岳。f(n)=f(n-1)+1 其中凳忙，f(1)=1 f(n)表示你想知道自己在哪一排业踏，f(n-1)表示前面一排所在的排數(shù)，f(1)=1表示第一排的人知道自己在第一排涧卵。有了這個遞推公式勤家，我們就可以很輕松地將它改為遞

歸代碼，如下:

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

遞歸需要滿足的三個條件

一個問題的解可以分解為幾個子問題的解,子問題就是數(shù)據(jù)規(guī)模更小的問題柳恐。
這個問題與分解之后的子問題伐脖，除了數(shù)據(jù)規(guī)模不同，求解思路完全一樣
存在遞歸終止條件

如何編寫遞歸代碼?

遞歸代碼最關(guān)鍵的是寫出遞推公式乐设，找到終止條件讼庇，剩下將遞推公式轉(zhuǎn)化為代碼就很簡單了。舉一個例子??

假如這里有n個臺階近尚，每次你可以跨1個臺階或者2個臺階蠕啄，請問走這n個臺階有多少種走法?如果有7個臺階，你可以2戈锻，2歼跟，2，1這樣子上去格遭，也可以1嘹承，2，1如庭，1叹卷，2這樣子上去，總之走法有很多坪它，那如何用編程求得總共有多少種走法呢?

我們仔細想下骤竹，實際上，可以根據(jù)第一步的走法把所有走法分為兩類往毡，第一類是第一步走了1個臺階蒙揣，另一類是第一步走了2個臺階。所以n個臺階的走法就等于先走1階后开瞭，n-1個臺階的走法加上先走2階后懒震，n-2個臺階的走法。用公式表示就是:

file:///F/temp/geektime/數(shù)據(jù)結(jié)構(gòu)與算法之美/10遞歸:如何用三行代碼找到“最終推薦人”?.html[2019/1/15 15:35:23]

10|遞歸:如何用三行代碼找到“最終推薦人”?

f(n) = f(n-1)+f(n-2) 有了遞推公式嗤详，遞歸代碼基本上就完成了一半个扰。我們再來看下終止條件。當有一個臺階時葱色，我們不需要再繼續(xù)遞歸递宅，就只有一種走法。所以f(1)=1。這個遞歸終止

條件足夠嗎?我們可以用n=2办龄，n=3這樣比較小的數(shù)試驗一下烘绽。 n=2時，f(2)=f(1)+f(0)俐填。如果遞歸終止條件只有一個f(1)=1安接，那f(2)就無法求解了。所以除了f(1)=1這一個遞歸終止條件外英融，還要有f(0)=1赫段，表示走0個臺階有一種走法，不過這樣子看起來就不符合正常的邏輯思維了矢赁。所以糯笙，我們可以把f(2)=2作為一種終止條件，表示走2個臺階撩银，有兩種走法给涕，一步走完或者分兩步來走。所以额获，遞歸終止條件就是f(1)=1够庙，f(2)=2。這個時候抄邀，你可以再拿n=3耘眨，n=4來驗證一下，這個終止條件是否足夠并且正確境肾。

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

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

有了這個公式剔难，我們轉(zhuǎn)化成遞歸代碼就簡單多了。最終的遞歸代碼是這樣的:

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

遞歸代碼要警惕堆棧溢出

函數(shù)調(diào)用會使用棧來保存臨時變量奥喻。每調(diào)用一個函數(shù)偶宫，都會將臨時變量封裝為棧幀壓入內(nèi)存棧，等函數(shù)執(zhí)行完成返回時环鲤，才出棧纯趋。系統(tǒng)棧或者虛擬機棧空間一般都不大冷离。如果遞歸求解的數(shù)據(jù)規(guī)模很大吵冒，調(diào)用層次很深，一直壓入棧西剥，就會有堆棧溢出的風(fēng)險痹栖。

比如前面的講到的電影院的例子，如果我們將系統(tǒng)椖璧ⅲ或者JVM堆棧大小設(shè)置為1KB结耀，在求解f(19999)時便會出現(xiàn)如下堆棧報錯: Exception in thread "main" java.lang.StackOverflowError

我們可以通過在代碼中限制遞歸調(diào)用的最大深度的方式來解決這個問題留夜。遞歸調(diào)用超過一定深度(比如1000)之后匙铡，我們就不繼續(xù)往下再遞歸了图甜，直接返回報錯。還是電影院那個例子鳖眼，我們可以改造成下面這樣子黑毅，就可以避免堆棧溢出了。不過钦讳，我寫的代碼是偽代碼矿瘦，為了代碼簡潔，有些邊界條件沒有考慮愿卒，比

int depth = 0;

int f(int n) {
 ++depth;
 if (depth > 1000) throw exception;
if (n == 1) return 1; 
return f(n-1) + 1;
}

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

為了避免重復(fù)計算缚去，我們可以通過一個數(shù)據(jù)結(jié)構(gòu)(比如散列表)來保存已經(jīng)求解過的f(k)。當遞歸調(diào)用到f(k)時琼开，先看下是否已經(jīng)求解過了易结。如果是，則直接從散列表中取值返回柜候，不需要重復(fù)計算搞动。

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

遞歸有利有弊，利是遞歸代碼的表達力很強渣刷，寫起來非常簡潔;而弊就是空間復(fù)雜度高鹦肿、有堆棧溢出的風(fēng)險、存在重復(fù)計算辅柴、過多的函數(shù)調(diào)用會耗時較多等問題箩溃。所以，在開發(fā)過程中碌嘀，我們要根據(jù)實際情況來選擇是否需要用遞歸的方式來實現(xiàn)碾篡。那我們是否可以把遞歸代碼改寫為非遞歸代碼呢?比如剛才那個電影院的例子，我們拋開場景筏餐，只看f(x) =f(x-1)+1這個遞推公式开泽。我們這樣改寫看看:

int f(int n) {
 int ret = 1;
 for (int i = 2; i <= n; ++i) { }ret = ret + 1;
return ret;
}

同樣，第二個例子也可以改為非遞歸的實現(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;
}