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

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

遞歸的概念

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

1.階乘函數(shù)。階乘函數(shù)可遞歸定義為n!=n*(n-1)!，當(dāng)n=0時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)用工作棧。通常，在一個算法中調(diào)用另外一個算法時，系統(tǒng)需在運(yùn)行被調(diào)用算法之前先完成三件事：

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

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

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

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

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

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

分治法的基本思想

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

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

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

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