遞歸是一種應(yīng)用非常廣泛的算法（或者編程技巧）。也是很多數(shù)據(jù)結(jié)構(gòu)和算法編碼實(shí)現(xiàn)的基礎(chǔ)。比如DFS深度優(yōu)先搜索、前中后序二叉樹遍歷等等，所以搞懂遞歸是學(xué)習(xí)后面復(fù)雜的數(shù)據(jù)結(jié)構(gòu)和算法的前提條件。

為滴道等地區(qū)用戶提供了全套網(wǎng)頁設(shè)計(jì)制作服務(wù)，及滴道網(wǎng)站建設(shè)行業(yè)解決方案。主營業(yè)務(wù)為成都網(wǎng)站建設(shè)、網(wǎng)站建設(shè)、滴道網(wǎng)站設(shè)計(jì)，以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠的服務(wù)。我們深信只要達(dá)到每一位用戶的要求，就會得到認(rèn)可，從而選擇與我們長期合作。這樣，我們也可以走得更遠(yuǎn)！

1. 理解遞歸

遞歸在我們的生活中也是很常見的：

在電影院里，在漆黑的時(shí)候，我們沒法直接知道自己是第幾排，于是我們就可以問前一排的人他是第幾排，我們只要在前一個(gè)人的基礎(chǔ)加一，但前面一排的人也看不清楚，所以他也要問他前面的人。就這樣一排一排往前問，直到問到第一排的人，因?yàn)榈谝慌诺娜吮旧砭椭雷约菏堑谝慌?，然后再這樣一排一排的把數(shù)字傳回來。直到你前面的人告訴你他在哪一排，于是就知道你自己是第幾排了。

上面的例子是一個(gè)非常標(biāo)準(zhǔn)的遞歸求解問題的分解過程，去的過程叫“遞”，回來的過程叫“歸”。

遞歸問題幾乎都可以用遞推公式來表示。上面電影院的例子的是：

f(n)=f(n-1)+1 其中，f(1)=1

f(n)表示你想知道自己在哪一排，f(n-1)表示前面一排所在的排數(shù)，f(1)=1表示第一排的人知道自己在第一排。

根據(jù)上面的遞推公式，我們就可以寫出遞推代碼：

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

2. 遞歸需滿足的三個(gè)條件

只有同時(shí)滿足下面三個(gè)條件的問題，才能用遞歸來解決。

1. 一個(gè)問題的解可以分解為幾個(gè)子問題的解

何為子問題？子問題就是數(shù)據(jù)規(guī)模更小的問題。比如前面電影院的例子，你要知道"自己在哪一排"的問題，可以分解為"前一排的人在哪一排"這樣的子問題。

2. 這個(gè)問題與分解之后的子問題，除了數(shù)據(jù)規(guī)模不同，求解思路完全一樣

比如電影院的例子，你求解"自己在哪一排"的思路，和前面一排人求解"自己在哪一排"的思路，是一模一樣的。

3. 存在遞歸終止條件

把問題分解為子問題，再把子問題分解為子子問題，一層一層分解下去，不能存在無限循環(huán)，這就需要有終止條件。

比如電影院的例子，第一排的人不需要在繼續(xù)詢問任何人，就知道自己在哪一排，也就是f(1)=1，這就是遞歸的終止條件。

3. 如何編寫遞歸代碼

寫遞歸代碼最關(guān)鍵的是"寫出遞推公式，找到終止條件"，然后就是將遞推公式轉(zhuǎn)化為代碼。

為了理解上面的結(jié)論，我們舉例說明：

假如有n個(gè)臺階，每次你可以跨1個(gè)臺階或2個(gè)臺階，請問走這n個(gè)臺階有多少種走法？

如果共有7個(gè)臺階，可以是 2 2 2 1，也可以是 1 2 1 1 2 等等。走法有多種，但如何用編程求解總共有多少種走法呢？

可以根據(jù)第一步的走法把所有走法分為兩類：

第一類：第一步走了1個(gè)臺階

第二類：第一步走了2個(gè)臺階

所以n個(gè)臺階的走法就等于先走1個(gè)臺階后，n-1個(gè)臺階的走法加上先走2個(gè)臺階后，n-2個(gè)臺階的走法，所以遞推公式就是：

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

有了遞推公式，然后就需要找到終止條件。

當(dāng)只剩一個(gè)臺階時(shí)，不需要遞推，因?yàn)樽叻ň椭挥幸环N，即f(1)=1。

當(dāng)還剩兩個(gè)臺階時(shí)，這時(shí)候可以一步走完（直接跨兩個(gè)臺階），或者一步一步的走（每次跨一個(gè)臺階），即f(2)=2。

當(dāng)還剩三個(gè)臺階時(shí)，可以分解為上面兩個(gè)子問題，即f(3)=f(2)+f(1)。

。。。以此類推。。。

所以終止條件就是f(1)=1,f(2)=2。

結(jié)合上面的分析，就可以得出終止條件和遞推公式：

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

根據(jù)上面的公式，就可以寫出如下遞歸代碼：

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

總結(jié)：寫遞歸代碼的關(guān)鍵就是找到如何將大問題分解為小問題的規(guī)律，并且基于此寫出遞推公式，然后再推敲終止條件，最后將遞推公式和終止條件翻譯成代碼。

前面電影院的例子，遞歸調(diào)用只有一個(gè)分支，即：一個(gè)問題只需要分解為一個(gè)子問題。這種情況，我們很容易理解，也能夠想清楚"遞"和"歸"的每一個(gè)步驟，所以想起來、理解起來都不難。

但當(dāng)一個(gè)問題要分解為多個(gè)子問題的時(shí)候，遞歸代碼就沒那么好理解。例如上面走臺階的例子，我們幾乎不能將整個(gè)"遞"和"歸"的過程一步一步都想清楚。

其實(shí)，對于遞歸代碼，我們試圖想弄清楚整個(gè)"遞"和"歸"過程的做法，實(shí)際上是一個(gè)進(jìn)入了思維誤區(qū)。很多時(shí)候，我們理解起來很費(fèi)力，主要原因是我們自己給自己制造了這種理解障礙。

我們正確的理解方式應(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è)步驟。

4. 警惕堆棧溢出

在寫遞歸代碼時(shí)，容易堆棧溢出，堆棧溢出會導(dǎo)致系統(tǒng)崩潰，后果很嚴(yán)重。

遞歸代碼容易造成堆棧溢出的原因

函數(shù)調(diào)用會使用棧來保存臨時(shí)變量，每調(diào)用一個(gè)函數(shù)，都會將臨時(shí)變量封裝為棧幀壓入內(nèi)存棧，等函數(shù)執(zhí)行完成返回時(shí)，才出棧。系統(tǒng)?；蛘咛摂M機(jī)?？臻g一般都不大，如果遞歸求解的數(shù)據(jù)規(guī)模很大，調(diào)用層次很深，一直壓入棧，就會有堆棧溢出的風(fēng)險(xiǎn)。

比如前面電影院的例子，如果我們將系統(tǒng)?；蛘逬VM堆棧大小設(shè)置為1KB，在求解f(19999)時(shí)便會出現(xiàn)如下堆棧報(bào)錯(cuò)：

Exception in thread "main" java.lang.StackOverflowError

遞歸代碼中如何預(yù)防堆棧溢出

可以通過在代碼中限制遞歸調(diào)用的大深度來解決堆棧溢出的問題。一般遞歸深度超過1000后，就不繼續(xù)往下遞歸，直接返回報(bào)錯(cuò)。

例如電影院的例子，我們可以通過如下改造，就可以避免堆棧溢出。

// 全局變量，表示遞歸的深度。
int depth = 0;

int f(int n) {
  ++depth；
  if (depth > 1000) throw exception;

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

上面寫的是偽代碼，為了代碼簡潔，有些邊界條件沒有考慮，比如x<=0。

但這種做法并不能完全解決問題，因?yàn)榇笤试S的遞歸深度跟當(dāng)前線程剩余的?？臻g大小有關(guān)，事先無法計(jì)算。如果實(shí)時(shí)計(jì)算，代碼就會過于復(fù)雜，會影響代碼的可讀性。所以，如果大深度比較小，比如50、100，就可以用這種方法，否則這種方法并不是很實(shí)用。

5. 警惕重復(fù)計(jì)算

在使用遞歸時(shí)，還會出現(xiàn)重復(fù)計(jì)算的問題。上面講的臺階的例子，如果我們將整個(gè)遞歸過程分解一下的話，就如下圖所示：

從圖中可以看出，當(dāng)我們計(jì)算f(5)時(shí)，需要先計(jì)算f(4)和f(3)，而計(jì)算f(4)時(shí)，還需要計(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ì)算。

按照上面的思想，可以改進(jìn)下上面臺階的代碼：

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;
}

在時(shí)間效率上，遞歸代碼里多了很多函數(shù)調(diào)用，當(dāng)這些函數(shù)調(diào)用的數(shù)量較大時(shí)，就會積聚成一個(gè)較大的時(shí)間成本。在空間復(fù)雜度上，因?yàn)檫f歸調(diào)用一次就會在內(nèi)存棧中保存一次現(xiàn)場數(shù)據(jù)，所以在分析遞歸代碼空間復(fù)雜度時(shí)，需要額外的考慮這部分開銷，例如上面電影院的例子，空間復(fù)雜度并不是O(1)，而是O(n)。

6. 將遞歸代碼改為非遞歸代碼

遞歸代碼有利有弊：

利：

代碼簡潔、表達(dá)能力強(qiáng)

弊：

空間復(fù)雜度高、有堆棧溢出的風(fēng)險(xiǎn)、存在重復(fù)計(jì)算、過多的函數(shù)調(diào)用會耗時(shí)較多。

所以在實(shí)際開發(fā)過程中，我們需要根據(jù)實(shí)際情況來選擇是否用遞歸的方式去實(shí)現(xiàn)。

我們也可以將遞歸代碼改為非遞歸代碼，例如電影院的例子就可修改為如下：

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

臺階的例子可修改為如下：

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)的非遞歸寫法。

7. 內(nèi)容小結(jié)

• 遞歸是一種非常高效、簡潔的編碼技巧。只要是滿足”三個(gè)條件“的問題就可以通過遞歸代碼來解決

• 遞歸代碼比較難寫、難理解。編寫遞歸代碼的關(guān)鍵就是不要把自己繞進(jìn)去，正確的姿勢是寫出遞推公式，找出終止條件，然后翻譯成遞歸代碼。

• 遞歸代碼雖然簡潔高效，但是也有很多弊端，例如：堆棧溢出、重復(fù)計(jì)算、函數(shù)調(diào)用耗時(shí)多、空間復(fù)雜度高等。

創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務(wù)器，動態(tài)BGP最優(yōu)骨干路由自動選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機(jī)房獨(dú)有T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動現(xiàn)已開啟，新人活動云服務(wù)器買多久送多久。

分享文章：遞歸算法-創(chuàng)新互聯(lián)
本文來源：http://www.rwnh.cn/article10/cojego.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供做網(wǎng)站、網(wǎng)站導(dǎo)航、用戶體驗(yàn)、品牌網(wǎng)站制作、定制開發(fā)、面包屑導(dǎo)航

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)