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

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

1. 理解遞歸

遞歸在我們的生活中也是很常見(jiàn)的：

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

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

遞歸問(wèn)題幾乎都可以用遞推公式來(lái)表示。上面電影院的例子的是：

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

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

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

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

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

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

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

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

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

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

3. 存在遞歸終止條件

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

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

3. 如何編寫(xiě)遞歸代碼

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

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

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

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

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

第一類(lèi)：第一步走了1個(gè)臺(tái)階

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

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

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

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

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

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

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

。。。以此類(lèi)推。。。

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

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

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

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

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

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

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

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

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

我們正確的理解方式應(yīng)該是：

如果一個(gè)問(wèn)題A可以分解為若干子問(wèn)題B、C、D，你可以先假設(shè)子問(wèn)題B、C、D已經(jīng)解決，在此基礎(chǔ)上思考如何解決問(wèn)題A。你只需要思考A與子問(wèn)題B、C、D兩層之間的關(guān)系即可，不需要一層一層往下思考子問(wèn)題與子子問(wèn)題，子子問(wèn)題與子子子問(wèn)題之間的關(guān)系。屏蔽掉遞歸細(xì)節(jié)，這樣就容易理解很多。

因此，編寫(xiě)遞歸代碼的關(guān)鍵是，只要遇到遞歸，就把它想象成一個(gè)遞推公式，不用想一層層的調(diào)用關(guān)系，不要試圖用人腦去解遞歸的每個(gè)步驟。

4. 警惕堆棧溢出

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

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

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

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

Exception in thread "main" java.lang.StackOverflowError

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

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

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

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

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

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

上面寫(xiě)的是偽代碼，為了代碼簡(jiǎn)潔，有些邊界條件沒(méi)有考慮，比如x<=0。

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

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

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

從圖中可以看出，當(dāng)我們計(jì)算f(5)時(shí)，需要先計(jì)算f(4)和f(3)，而計(jì)算f(4)時(shí)，還需要計(jì)算f(3)，因此，f(3)就會(huì)計(jì)算多次，這就是重復(fù)計(jì)算問(wèn)題。

為了避免重復(fù)計(jì)算，可以通過(guò)一個(gè)數(shù)據(jù)結(jié)構(gòu)（比如散列表）來(lái)保存已經(jīng)求解過(guò)的f(k)，當(dāng)遞歸調(diào)用f(k)時(shí)，先看下是否已經(jīng)求解過(guò)了。如果是，則直接從散列表中取值返回，不需要重復(fù)計(jì)算。

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

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í)，就會(huì)積聚成一個(gè)較大的時(shí)間成本。在空間復(fù)雜度上，因?yàn)檫f歸調(diào)用一次就會(huì)在內(nèi)存棧中保存一次現(xiàn)場(chǎng)數(shù)據(jù)，所以在分析遞歸代碼空間復(fù)雜度時(shí)，需要額外的考慮這部分開(kāi)銷(xiāo)，例如上面電影院的例子，空間復(fù)雜度并不是O(1)，而是O(n)。

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

遞歸代碼有利有弊：

利：

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

弊：

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

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

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

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

臺(tái)階的例子可修改為如下：

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

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

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

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

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

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

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

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

廣告

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