遞歸與分治的關(guān)系

品牌網(wǎng)站建設(shè),任何可以用計(jì)算機(jī)求解的問題所需要的計(jì)算時(shí)間都與其規(guī)模有關(guān)。問題規(guī)模越小，解題所需要的計(jì)算時(shí)間往往也越短，從而也比較容易處理。例如，對(duì)于n個(gè)元素的排序問題，當(dāng)n=1時(shí)，不需要任何計(jì)算。n=2時(shí)，只需要一次比較即可排好序。n=3時(shí)只要兩次比較即可…當(dāng)n較大時(shí)，問題就不那么容易處理了。要想解決一個(gè)較大的問題，有時(shí)是相當(dāng)困難的。分治法的設(shè)計(jì)思想就是：將一個(gè)難以直接解決的大問題分割成一些規(guī)模較小的相同問題，以便各個(gè)擊破，即分而治之。 如果原問題可分割成k個(gè)子問題，1<k<=n，且這些子問題都可解，并可利用這些子問題的解求出原問題的解，那么這種分治法就是可行的。由分治法產(chǎn)生的子問題往往是原問題的效小模式，這為使用遞歸技術(shù)提供了方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問題與原問題類型一致而其規(guī)模不斷縮小，最終使子問題縮小到容易求出其解，由此自然引出遞歸算法。分治和遞歸像一對(duì)孿生兄弟，經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)中，并由此產(chǎn)生許多高效算法。

遞歸的概念

直接或者間接地調(diào)用自身的算法稱為遞歸算法。 用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。在計(jì)算機(jī)算法設(shè)計(jì)和分析中，遞歸技術(shù)是十分有用的。使用遞歸技術(shù)往往使函數(shù)的定義和算法的描述簡(jiǎn)捷且易于理解。有些數(shù)據(jù)結(jié)構(gòu)，例如二叉樹等，由于本身固有的遞歸特性，特別適合用遞歸的形式來描述。有些問題，雖然其本身并沒有明顯的遞歸結(jié)構(gòu)，但用遞歸技術(shù)來求解，可以使設(shè)計(jì)出的算法簡(jiǎn)捷且易于分析。例如：

1.階乘函數(shù)。階乘函數(shù)可遞歸定義為n!=n*(n-1)!，當(dāng)n=0時(shí)n！=1。則遞歸計(jì)算如下：

2.Fibonacci數(shù)列

  F(0)=0
  F(1)=1
  F(n)=F(n?1)+F(n?2) ,(n≥2,n∈N)
  遞歸表達(dá)為：

3.漢諾塔問題

   遞歸表達(dá)為：

實(shí)現(xiàn)這種遞歸調(diào)用的關(guān)鍵是為算法建立遞歸調(diào)用工作棧。通常，在一個(gè)算法中調(diào)用另外一個(gè)算法時(shí)，系統(tǒng)需在運(yùn)行被調(diào)用算法之前先完成三件事：

（1）將所有實(shí)參指針、返回地址等信息傳遞給被調(diào)用算法；

（2）為被調(diào)用算法的局部變量分配存儲(chǔ)區(qū)；

（3）將控制轉(zhuǎn)移到被調(diào)用算法的人口。

在從被調(diào)用算法返回調(diào)用算法時(shí)，系統(tǒng)相應(yīng)地要完成三件事：

（1）保存被調(diào)用算法的計(jì)算結(jié)果；

（2）釋放分配給被調(diào)用算法的數(shù)據(jù)區(qū)；

（3）依照被調(diào)用算法保存的返回地址將控制轉(zhuǎn)移到調(diào)用算法。

當(dāng)有多個(gè)算法構(gòu)成嵌套調(diào)用時(shí)，按照“后調(diào)用先返回”的原則進(jìn)行。上述算法之間的信息傳遞和控制轉(zhuǎn)移必須通過棧來實(shí)現(xiàn)，即系統(tǒng)將整個(gè)程序運(yùn)行時(shí)所需的數(shù)據(jù)空間安排在一個(gè)棧中，每調(diào)用一個(gè)算法，就為它在棧頂分配一個(gè)存儲(chǔ)區(qū)，每退出一個(gè)算法，就釋放它在棧頂?shù)拇鎯?chǔ)區(qū)。當(dāng)前正在運(yùn)行的算法的數(shù)據(jù)一定在棧頂。

遞歸算法的實(shí)現(xiàn)類似于多個(gè)算法的嵌套調(diào)用，只是調(diào)用算法和被調(diào)用算法是同一個(gè)算法。因此，與每次調(diào)用相關(guān)的一個(gè)重要概念是遞歸算法的調(diào)用層次。企業(yè)網(wǎng)站設(shè)計(jì)，若調(diào)用一個(gè)遞歸算法的主算法為第0層算法，則從主算法調(diào)用遞歸算法為進(jìn)入第1層調(diào)用；從第i層遞歸調(diào)用本算法為進(jìn)入第i+1層調(diào)用。反之，退出第i層遞歸調(diào)用，則返回至第i-1層調(diào)用。為了保證遞歸調(diào)用正確執(zhí)行，系統(tǒng)需要建立一個(gè)遞歸調(diào)用工作棧，為各層次的調(diào)用分配數(shù)據(jù)存儲(chǔ)區(qū)。每層遞歸調(diào)用所需的信息構(gòu)成一個(gè)工作記錄，其中包括所有實(shí)參指針、所有局部變量以及返回上一層的地址。每進(jìn)入一層遞歸調(diào)用，就產(chǎn)生一個(gè)新的工作記錄壓入棧頂。每退出一層遞歸調(diào)用，就從棧頂彈出一個(gè)工作記錄。

由于遞歸算法結(jié)構(gòu)清晰，可讀性強(qiáng)，且容易用數(shù)學(xué)歸納法證明算法的正確性，因此它為設(shè)計(jì)算法、調(diào)試程序帶來很大方便。然而，遞歸算法的運(yùn)行效率較低，無論是耗費(fèi)的計(jì)算時(shí)間還是占用的存儲(chǔ)空間都比非遞歸算法要多。對(duì)于網(wǎng)站建設(shè)公司來說，若在程序中消除算法的遞歸調(diào)用，則其運(yùn)行時(shí)間可大為節(jié)省。因此，有時(shí)希望在遞歸算法中消除遞歸調(diào)用，使其轉(zhuǎn)化為一個(gè)非遞歸算法。通常，消除遞歸采用一個(gè)用戶定義的棧來模擬系統(tǒng)的遞歸調(diào)用工作棧，從而達(dá)到將遞歸算法改為非遞歸算法的目的。還可以用遞推實(shí)現(xiàn)遞歸函數(shù)以及通過變換能將一些遞歸轉(zhuǎn)化為尾遞歸，從而迭代求出結(jié)果。 僅僅是機(jī)械地模擬還不能達(dá)到縮短計(jì)算時(shí)間和減少存儲(chǔ)空間的目的，還需要根據(jù)具體程序的特點(diǎn)對(duì)遞歸調(diào)用工作棧進(jìn)行簡(jiǎn)化，盡量減少棧操作，壓縮棧存儲(chǔ)空間以達(dá)到節(jié)省計(jì)算時(shí)間和存儲(chǔ)空間的目的。

分治法的基本思想

分治法的基本思想是將一個(gè)規(guī)模為n的問題分解為k個(gè)規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題相同。遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解。它的一般算法設(shè)計(jì)模式如下：

其中，|p|表示問題P的規(guī)模，n0為以閾值，表示當(dāng)問題P的規(guī)模不超過n0時(shí)，問題容易解出，不必要再繼續(xù)分解。adhoc（p）是該分治法中的基本子算法，用于直接解小規(guī)模的問題P。當(dāng)P的規(guī)模不超過n0時(shí)，直接用算法adhoc（p）求解。算法merge（y1，y2，…，yk）是該分治法中的合并子算法，用于將P的子問題P1，P2,…,PK的解y1，y2，…，yk合并為P的解。

根據(jù)分治法的分割原則，應(yīng)把原問題分為多少個(gè)子問題才較適宜？每個(gè)子問題是否規(guī)模相同或者咋樣才為適當(dāng)？這些問題很難一概而論。但從大量實(shí)踐中發(fā)現(xiàn)，在用分治法設(shè)計(jì)算法時(shí)，最好使子問題的規(guī)模大致相同，即將一個(gè)問題分為大小相等的k個(gè)子問題的處理方法是行之有效的。許多問題可以取k=2.這種使子問題規(guī)模大致相等的做法出自一種平衡子問題的思想，幾乎總是比子問題規(guī)模不等的做法要好。

從分治法的一般設(shè)計(jì)模式可以看出，用它設(shè)計(jì)出的程序一般是遞歸算法，因此分治法的計(jì)算效率通?？梢?用遞歸方程來進(jìn)行分析。一個(gè)分治法將規(guī)模為n的問題分為k個(gè)規(guī)模為n/m的子問題去解。將原問題分解為k個(gè)子問題及用merge將k個(gè)子問題的解合并為原問題的解需用f（n）單位時(shí)間。如果T（n）表示該分治法divide-and-conquer（p）解規(guī)模為|P|=n的問題所需要的計(jì)算時(shí)間，則