04.遞歸算法講解

1、1.用遞歸法計(jì)算n!【講解講解】遞歸是算法設(shè)計(jì)中的一種基本而重要的算法。遞歸方法即通過函數(shù)或過程調(diào)用自身將問題轉(zhuǎn)化為本質(zhì)相同但規(guī)模較小的子問題，是分治策略的具體體現(xiàn)。遞歸方法具有易于描述、證明簡(jiǎn)單等優(yōu)點(diǎn)，在動(dòng)態(tài)規(guī)劃、貪心算法、回溯法等諸多算法中都有著極為廣泛的應(yīng)用，是許多復(fù)雜算法的基礎(chǔ)。遞歸概述遞歸概述一個(gè)函數(shù)在它的函數(shù)體內(nèi)調(diào)用它自身稱為遞歸（recursion）調(diào)用。是一個(gè)過程或函數(shù)在其定義或說明中直接或間接調(diào)用自身的一種方法，通常把

2、一個(gè)大型復(fù)雜的問題層層轉(zhuǎn)化為一個(gè)與原問題相似的規(guī)模較小的問題來求解。遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復(fù)計(jì)算，大大地減少了程序的代碼量。遞歸的能力在于用有限的語句來定義對(duì)象的無限集合。用遞歸思想寫出的程序往往十分簡(jiǎn)潔易懂。一般來說，遞歸需要有邊界條件、遞歸前進(jìn)段和遞歸返回段。當(dāng)邊界條件不滿足時(shí)，遞歸前進(jìn)；當(dāng)邊界條件滿足時(shí)，遞歸返回。使用遞歸要注意以下幾點(diǎn)：（1）遞歸就是在過程或函數(shù)里調(diào)用自身；（2）在使用遞增歸策略時(shí)

3、，必須有一個(gè)明確的遞歸結(jié)束條件，稱為遞歸出口。例如有函數(shù)r如下：intr(inta)b=r(a?1)returnb這個(gè)函數(shù)是一個(gè)遞歸函數(shù)，但是運(yùn)行該函數(shù)將無休止地調(diào)用其自身，這顯然是不正確的。為了防止遞歸調(diào)用無終止地進(jìn)行，必須在函數(shù)內(nèi)有終止遞歸調(diào)用的手段。常用的辦法是加條件判斷，滿足某種條件后就不再作遞歸調(diào)用，然后逐層返回。構(gòu)造遞歸方法的關(guān)鍵在于建立遞歸關(guān)系。這里的遞歸關(guān)系可以是遞歸描述的，也可以是遞推描述的。例4141用遞歸法計(jì)算用遞

4、歸法計(jì)算n!n!。n!的計(jì)算是一個(gè)典型的遞歸問題。使用遞歸方法來描述程序，十分簡(jiǎn)單且易于理解。（1）描述遞歸關(guān)系遞歸關(guān)系是這樣的一種關(guān)系。設(shè)U1U2U3…Un…是一個(gè)序列，如果從某一項(xiàng)k開始，Un和它之前的若干項(xiàng)之間存在一種只與n有關(guān)的關(guān)系，這便稱為遞歸關(guān)系。注意到，當(dāng)n≥1時(shí)，n!=n(n?1)!（n=0時(shí)，0!=1），這就是一種遞歸關(guān)系。對(duì)于特定的k!，它只與k與(k?1)!有關(guān)。（2）確定遞歸邊界在步驟1的遞歸關(guān)系中，對(duì)大于k的U

5、n的求解將最終歸結(jié)為對(duì)Uk的求解。這里的Uk稱為遞歸邊界（或遞歸出口）。在本例中，遞歸邊界為k=0，即0!=1。對(duì)于任意給定的N!，程序?qū)⒆罱K求解到0!。確定遞歸邊界十分重要，如果沒有確定遞歸邊界，將導(dǎo)致程序無限遞歸而引起死循環(huán)。例如以下程序：#includeintf(intx)return(f(x?1))2.漢諾塔（Hanoi），又稱河內(nèi)塔問題，是印度的一個(gè)古老傳說。開天辟地的神勃拉瑪在一個(gè)廟里留下了三根金剛石的棒，第一根上面套著64

6、個(gè)圓的金片，最大的一個(gè)在底下，其余一個(gè)比一個(gè)小，依次疊上去。廟里的眾僧不倦地把它們一個(gè)個(gè)地從這根棒搬到另一根棒上，規(guī)定可利用中間的一根棒作為幫助，但每次只能搬一個(gè)，而且大的不能放在小的上面。后來，這個(gè)傳說就演變?yōu)闈h諾塔游戲：木樁A木樁B木樁C木樁A木樁B木樁C123N123N圖1圖351漢諾塔游戲示意圖（1）有三根樁子A、B、C。A樁上有n個(gè)碟子，最大的一個(gè)在底下，其余一個(gè)比一個(gè)小，依次疊上去。（2）每次移動(dòng)一塊碟子，小的只能疊在大的上

7、面。（3）把所有碟子從A樁全部移到C樁上，如圖351所示。試求解n個(gè)圓盤A樁全部移到C樁上的移動(dòng)次數(shù)，并求出n個(gè)圓盤的移動(dòng)過程?！局v解講解】1.1.遞歸關(guān)系遞歸關(guān)系當(dāng)n=1時(shí)，只一個(gè)盤，移動(dòng)一次即完成。當(dāng)n=2時(shí)，由于條件是一次只能移動(dòng)一個(gè)盤，且不允許大盤放在小盤上面，首先把小盤從A樁移到B樁；然后把大盤從A樁移到C樁；最后把小盤從B樁移到C樁，移動(dòng)3次完成。設(shè)移動(dòng)n個(gè)盤的漢諾塔需g(n)次完成。分以下三個(gè)步驟：(1)首先將n個(gè)盤上面的