04.遞歸算法講解

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

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

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

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

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

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

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