1、二、遞歸與遞歸式1.1 遞歸與遞歸程序設(shè)計(jì)1. 什么是遞歸？遞歸是一個過程或函數(shù)在其定義或說明中又直接或間接調(diào)用自身的一種方法。1）遞歸的本質(zhì)遞歸把一個大型、復(fù)雜的問題層層轉(zhuǎn)化為一個與原問題相似、但規(guī)模較小的問題來求解，只需少量的程序就可描述出解題過程所需要的多次重復(fù)計(jì)算，大大地減少了程序的代碼量。遞歸的能力在于用有限的語句來定義對象的無限集合。2）遞歸的結(jié)構(gòu)一般來說，遞歸由邊界條件、遞歸計(jì)算和遞歸返回組成。當(dāng)邊界條件不滿足時，遞歸向前推進(jìn)計(jì)算過程；當(dāng)邊界條件滿足時，遞歸返回。 2. 遞歸程序設(shè)計(jì)程序調(diào)用自身的編程技巧稱為遞歸程序設(shè)計(jì)。是遞歸算法的直接描述。關(guān)于遞歸，注意兩點(diǎn)： (1) 遞歸就

2、是在過程或函數(shù)里直接或簡接地調(diào)用自身; (2) 在使用遞歸策略時，必須有一個明確的遞歸結(jié)束條件，稱為遞歸出口，否則會產(chǎn)生死循環(huán)而出錯。 遞歸是一種強(qiáng)有力的設(shè)計(jì)方法 與數(shù)學(xué)模型一致 表述簡單、清晰、代碼量少 可讀性強(qiáng)、容易證明正確性 遞歸的問題：執(zhí)行時間長、運(yùn)行效率低，特別是占用空間多，容易造成系統(tǒng)棧的溢出。主要原因：遞歸調(diào)用時有大量的現(xiàn)場保護(hù)與恢復(fù)操作，在遞歸調(diào)用的過程當(dāng)中系統(tǒng)為每一層的返回點(diǎn)、局部量等開辟了棧來存儲，遞歸層次數(shù)過多容易造成棧溢出等。 例2.1 斐波那契(Fibonacci)序列： F0 = F1 = 1 Fi = Fi-1 + Fi-2 （i1)算法2.1 求斐波那契數(shù)： p

3、rocedure F(n) /返回第n個斐波那契數(shù)/ integer n if n 1 then return(1) else return(F(n-1) + F(n-2) endif end F思考：上述算法的效率非常低下，為什么？上述過程的效率很差，存在大量的重復(fù)計(jì)算：改進(jìn)：保存中間結(jié)果（遞推模型） 其它遞歸模型F(n)F(n-1)F(n-2)F(n-2)F(n-3)F(n-3)F(n-4)分析：F(n-2)被算了兩次，F(xiàn)(n-3)被算了三次，F(xiàn)(n-4)被算了五次，.，總的運(yùn)算量為這些運(yùn)算之和，所以，事實(shí)上，這樣的計(jì)算過程，運(yùn)算次數(shù)本身也是一個斐波那契數(shù)列。整個計(jì)算的時間復(fù)雜度約為O(1

4、.618n)。非常之大！例2.2 歐幾里得算法 已知兩個非負(fù)整數(shù)a和b，且ab0，求這兩個數(shù)的最大公因數(shù)。 輾轉(zhuǎn)相除法：若b=0，則a和b的最大公因數(shù)等于a；若b0，則a和b的最大公因數(shù)等于b和用b除a的余數(shù)的最大公因數(shù)。 算法2.2 求最大公因數(shù) procedure GCD(a,b) / 約定ab / if b=0 then return(a) else return (GCD(b,a mod b) endif end GCD 例： GCD(22,8) = GCD(8,6) = GCD(6,2) = GCD(2,0) = 2例2.3 用遞歸策略設(shè)計(jì)的檢索算法 已知元素x和元素表A（1：n），

5、判斷x是否等于A中某元素的值。 算法2.3 在A（1：n）中檢索x procedure SEARCH(i) /如果在A（1：n）中有一元素A(k)=x，則將其第一次出現(xiàn)的下標(biāo)k返回，否則返回0/ global n,x,A(1:n) case :in: return(0) :A(i) = x; return(i) :else: return(SEARCH(i+1) endcase end SEARCH3. 怎么克服遞歸的效率問題？化遞歸為遞推遞歸：遞歸是一種從上至下的“分解求解“的過程，即不斷地把大問題分解為小問題，直到小問題規(guī)模足夠小，然后求解并進(jìn)行遞歸返回和結(jié)果合并。效率差！遞推：遞推是一種

6、從下往上的“合并求解“過程，即從解決小問題出發(fā)，記錄小問題的答案，并根據(jù)已有的小問題的答案，把問題往大里擴(kuò)展，“滾雪球”，直到達(dá)到大問題的規(guī)模為止。并通常用迭代（循環(huán)）的方式實(shí)現(xiàn)，而不是遞歸調(diào)用，一般認(rèn)為效率上比遞歸好。遞歸和遞推的聯(lián)系：都存在重復(fù)計(jì)算，是解決較大規(guī)模問題的有效方法；遞歸和遞推的區(qū)別：求解思路不同，實(shí)現(xiàn)技術(shù)上也不一樣2.2 遞歸式及其求解1. 遞歸式遞歸式是一組等式或不等式，它所描述的函數(shù)是用在更小的輸入下該函數(shù)的值來定義的。遞歸算法（或具有遞歸性質(zhì)的迭代算法）的運(yùn)行時間通常用遞歸式表示。如：歸并排序（MERGESORT）的運(yùn)行時間T(n)表示如下：1 )(1 )()2/(2)

7、( nngnnfnTnT遞歸式和遞推式1) 遞推式 Recurrence數(shù)列：按一定次序排列的一列數(shù)稱為數(shù)列（sequence of number）。數(shù)列中的每一個數(shù)都叫做這個數(shù)列的項(xiàng)。排在第一位的數(shù)稱為這個數(shù)列的第1項(xiàng)，排在第二位的數(shù)稱為這個數(shù)列的第2項(xiàng)排在第n位的數(shù)稱為這個數(shù)列的第n項(xiàng)，數(shù)列的一般形式可以寫成a1，a2，a3，an，簡記為an。遞推公式：通過給出數(shù)列的第1項(xiàng)（或前若干項(xiàng)），并給出數(shù)列的某一項(xiàng)與它的前一項(xiàng)（或前若干項(xiàng)）的關(guān)系式來表示數(shù)列，這種表示數(shù)列的式子叫做這個數(shù)列的遞推公式。遞推公式是數(shù)列所特有的表示法，它包含兩個部分：（1）初始條件邊界值；（2）遞推關(guān)系an與其他一項(xiàng)或

8、多項(xiàng)之間的構(gòu)造規(guī)律。二者缺一不可。例如：斐波納契數(shù)列的遞推公式為fn=fn-1+fn-2 等差數(shù)列遞推公式：an=an-1+d 等比數(shù)列遞推公式：bn=bn-1q2) 遞歸式 Recursion遞歸公式：當(dāng)遞推式中只含數(shù)列中的項(xiàng)，而無常數(shù)項(xiàng)或其它項(xiàng)時，就叫做遞歸公式。所以，遞歸公式屬于遞推公式的一個特例。例如，自然數(shù)列 用通項(xiàng)公式表示為：an=n 用遞推公式表示為：an+1=an+1 初始條件：a1=1 用遞歸公式表示為：an+2=2an+1-an， 初始條件：a1=1，a2=2 這里，沒有過于細(xì)致地區(qū)分遞歸式與遞推式，我們視為一致。2. 遞歸式的求解求解遞歸式就是化簡遞歸式，以得到形式簡單的

9、限界函數(shù)表示（即O、的表示）。三種常用方法：l代換法l遞歸樹法l主方法對表達(dá)式細(xì)節(jié)的簡化 為便于處理，通常做如下假設(shè)和簡化處理(1) 運(yùn)行時間函數(shù)T(n)的定義中，一般假定自變量為整數(shù)。(2) 忽略遞歸式的邊界條件，即n較小時函數(shù)值的表示。原因在于，雖然遞歸式的解會隨著T(1)值的改變而改變，但此改變不會超過常數(shù)因子，對函數(shù)的階沒有根本影響。(3) 對上取整、下取整運(yùn)算做合理簡化，如 通常忽略上、下取整函數(shù)，直接寫作：)()2/()2/()(nfnTnTnT)()2/(2)(nfnTnT注：被簡化的細(xì)節(jié)并不是不重要，只是這些細(xì)節(jié)處理不影響算法分析的漸近界，是“無限大”分析中的合理假設(shè)和簡化。在

10、細(xì)節(jié)被簡化處理的同時，也要知道它們在什么情況下是“實(shí)際”重要的。這樣就可以了解算法在各種情況的具體執(zhí)行情況。1) 代換法用代換法解遞歸式基本思想：先猜測一個界，然后用數(shù)學(xué)歸納法證明該猜測的正確性，亦即，用該猜測作為歸納假設(shè)，當(dāng)推論證明時作為較小值代替函數(shù)的解，然后證明推論的正確性。用代換法解遞歸式的步驟：(1) 猜測漸近界的形式(2) 用數(shù)學(xué)歸納法證明猜測的正確性例：用代換法確定下式的上界分析：該式與 類似，故猜測其解為O(nlogn)?，F(xiàn)在想法證明T(n)cnlogn，并確定常數(shù)c的存在。假設(shè)該界對 成立，即 ，然后在數(shù)學(xué)歸納法推論證明階段對遞歸式做替換，有：故，要使T(n)cnlogn成立

11、，只要c1就可以，這樣的c是存在的、合理的。nnTnT)2/(2)(nnTnT)2/(2)(2/n)2/log(2/)2/(nncnTncncnncnncnnncnnnncnT) 1(log 2loglog )2/log( )2/log(2/(2)(上面的證明過程，證明了當(dāng)n足夠大時猜測的正確性。但邊界值呢？即： T(n)cnlogn的結(jié)論對于小n成立嗎？分析：事實(shí)上，對n=1，上述結(jié)論存在問題：作為邊界條件，我們有理由假設(shè)T(1)=1，但對n=1，T(1)c1log1=0，與T(1)=1不相符。也即， T(n)cnlogn對于歸納證明的基本情況不成立。怎么處理？從O的定義出發(fā)： 只需要存在常

12、數(shù)n0，使得nn0時結(jié)論成立即可n0不一定取1。所以，這里，我們不取n0=1，而取n0=2，并將T(2)、T(3)作為歸納證明中的邊界條件代替T(1)（但依舊假設(shè)T(1) =1）使得T(2)、T(3) 滿足T(n)cnlogn。而n3時，遞歸計(jì)算不再直接依賴T(1)，使用T(2)、T(3)即可完成。帶入T(1)=1，通過遞歸式有，T(2) = 4，T(3)=5，如何使T(2)、T(3)滿足T(n)cnlogn？只要c取足夠大的常數(shù)使得T(2)c2log2和T(3)c3log3成立即可。這樣的c是什么？答案：只要c2即可。綜上所述，取常數(shù)c2，最終的結(jié)論T(n)cnlogn就成立。命題得證。如何

13、猜測遞歸式的漸近界呢？1）主要靠經(jīng)驗(yàn)u嘗試1：看有沒有形式上類似的表達(dá)式，以此推測新遞歸式的漸近界。u嘗試2：先猜測一個較寬的界，然后再縮小不確定區(qū)間，收縮到精確的漸近界。2）避免盲目推測 如： 原因：沒有證明一般形式T(n)cn。（cn+ncn）)()2/(2)(nncnnncnT必要的時候要做一些技術(shù)處理1）去掉一個低階項(xiàng)（略,算法導(dǎo)論P(yáng)39）2）變量代換對陌生的遞歸式做些簡單的代數(shù)變換，使之變成較熟悉的形式。例：化簡 分析：原始形態(tài)比較復(fù)雜 做代數(shù)代換：令 同時，為簡單起見，忽略下取整細(xì)節(jié) ，直接使用 ，得：nnTnTlog)(2)(nnmlognmTTmm)2(2)2(2/再設(shè)S(m)

14、 = T(2m)，得以下形式遞歸式：從而獲得形式上熟悉的遞歸式.而新的遞歸式的上界是：再將S(m)帶回T(n)，有，mTTmm)2(2)2(2/mmSmS)2/(2)(nmnnOmmOmSTnTmlog)loglog(log )log()( )2()(這里，)log(mmO2）遞歸樹法遞歸樹：用來描述遞歸調(diào)用過程的樹。根節(jié)點(diǎn)代表原始問題，根節(jié)點(diǎn)的子節(jié)點(diǎn)代表第一次分割劃分出來的子問題，依次類推。葉子節(jié)點(diǎn)代表可以直接求解的最小子問題。如：好處：很直觀、清晰地描述出遞歸的執(zhí)行過程，而且可以用我們已經(jīng)了解到的樹方面的性質(zhì)做一些深入的分析。F(n)F(n-1)F(n-2)F(n-2)F(n-3)F(n-

15、3)F(n-4)F(0)F(1)F(0)F(1)F(0)F(1).基于遞歸樹的時間分析節(jié)點(diǎn)代價(jià)：在遞歸樹中，每個節(jié)點(diǎn)有求解相應(yīng)（子）問題的代價(jià)。層代價(jià)：每一層各節(jié)點(diǎn)代價(jià)之和。總代價(jià)：整棵樹的各層代價(jià)之和目 標(biāo)：利用樹的性質(zhì)，獲取對遞歸式解的猜測，然后用代換法或其它方法加以驗(yàn)證。例2.4 ：已知遞歸式 ，求其上界準(zhǔn)備性工作：為簡單起見，對一些細(xì)節(jié)做必要、合理的簡化和假設(shè)，這里為：（1）去掉底函數(shù)的表示 理由：底函數(shù)和頂函數(shù)對求解遞歸式問題并不重要。（2）假設(shè)n是4的冪，即n=4k，k=log4n。 一般，當(dāng)證明n=4k成立后，再加以適當(dāng)推廣，就可以把結(jié)論推廣到n不是4的冪的一般情況了。（3）對

16、，假設(shè)其常系數(shù)為c，c0，從而可以去掉 符號表示。最終得以下形式的遞歸式：)()4/(3)(2nnTnT)(2n用遞歸樹描述T(n)的演化過程:2)4/(3)(cnnTnT2cn)(nT2cn)4(nT)4(nT)4(nT2)4(nc)16(nT)16(nT)16(nT2)4(nc2)4(nc)16(nT)16(nT)16(nT)16(nT)16(nT)16(nTa)b)c)a) 原始問題的T(n)描述。b) 第一層遞歸調(diào)用的分解情況，cn2是頂層計(jì)算除遞歸以外的代價(jià)，T(n/4)是分解出來的規(guī)模為n/4的子問題的代價(jià)，總代價(jià)T(n)=3T(n/4)+cn2。c) 第二層遞歸調(diào)用的分解情況。c

17、(n/4)2是三棵子樹除遞歸以外的代價(jià)。繼續(xù)擴(kuò)展下去，直到遞歸的最底層，得到如下形式的遞歸樹：d) 完全擴(kuò)展的遞歸樹，遞歸樹深度為log4n(共有l(wèi)og4n+1層)2cn2)4(nc2)16(nC2)4(nc2)4(nc)1 (T)1 (T)1 (T)1 (T)1 (T)1 (T)1 (T)1 (T)1 (T)1 (T)1 (T)1 (T)1 (T)1 (T)1 (T)1 (T)1 (T)1 (T1log4n3log4n2cn2163cn22)163(cn)(3log4n)(:2nOTotal2)16(nC2)16(nC2)16(nC2)16(nC2)16(nC2)16(nC2)16(nC2)

18、16(nC樹的深度：子問題的規(guī)模按1/4方式減小，在遞歸樹中，深度為i的節(jié)點(diǎn)，子問題的大小為n/4i。 當(dāng)n/4i=1時，子問題規(guī)模僅為1，達(dá)到邊界值。 所以，p節(jié)點(diǎn)高度：0log4np樹共有l(wèi)og4n+1層p從第2層起，每一層上的節(jié)點(diǎn)數(shù)為上層節(jié)點(diǎn)數(shù)的3倍p深度為i的層節(jié)點(diǎn)數(shù)為3i。代價(jià)計(jì)算（1）內(nèi)部節(jié)點(diǎn)：位于0 層 深度為i的節(jié)點(diǎn)的代價(jià)為 ， i層節(jié)點(diǎn)的總代價(jià)為： 。（2）葉子節(jié)點(diǎn)：位于 層，共有 個節(jié) 點(diǎn)，每個節(jié)點(diǎn)的代價(jià)為T(1), 總代價(jià)為3loglog443nn1log4n2)4/(inc22)16/3()4/(3cnnciiin4log)() 1 (3log3log44nTn（3）樹

19、的總代價(jià) 整棵樹的總代價(jià)為各層代價(jià)之和，則有)(1)16/3(1)16/3( )()163( )()163(.)163(163)(3log2log3log1log0i23log21log2222444444ncnncnncncncncnnTnnin利用等比數(shù)列化簡上式。對于實(shí)數(shù)x1，和式 是一個幾何級數(shù)（等比數(shù)列），其值為 當(dāng)和是無窮的且|x|1；f(n)是一個漸近正的函數(shù)。含義：規(guī)模為n的原問題被分為a個子問題，每個子問題的規(guī)模是n/b，a和b是正常數(shù)。子問題被遞歸地求解，T(n)是原始問題的時間，每個子問題的時間為T(n/b)；劃分出來的子問題的答案合并及其它有關(guān)運(yùn)算的代價(jià)由函數(shù)f(n)描

20、述。上式給出了算法總代價(jià)與子問題代價(jià)的關(guān)系。)()/()(nfbnaTnT注：這里采用了細(xì)節(jié)的簡化，沒有考慮n/b的取整問題，省略了下取整、上取整，但本質(zhì)上不影響對遞歸式漸近行為的分析。對上述形式的遞歸式漸近界的求解是依賴稱之為“主定理”的結(jié)論給出的。定理2.1 主定理設(shè)a1和b1為常數(shù)，設(shè)f(n)為一函數(shù)，T(n)由以下遞歸式給出對于非負(fù)整數(shù)定義，其中n/b指 或 。則T(n)可能有如下的漸近界：1）若對于某常數(shù)0，有 ，則2）若 ，則3）若對某常數(shù)0，有 ，且對常數(shù)c0，f(n)必須漸近地小于 ，兩者相差了一個 因子。abnlogabnlog)()(log abnnT)()(nfnT)log()(lognnnTababnlogabnlogabnlogn3) 在第三種情況中，f(n)不僅要大于 ，而且要多項(xiàng)式地大于 ，還要滿足一個“規(guī)則性”條件 。4) 若遞歸式中的f(n)與 的關(guān)系不滿足上述性質(zhì)：u f(n)小于 ，但不是多項(xiàng)式地小于，中間差了u f(n)大于 ，但不是多項(xiàng)式地大于，中間差了 則不能用主方法求解